프로그래머스 배달

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달 | 프로그래머스

 

[주의할 조건]

마을의 개수 N은 1 이상 50 이하의 자연수입니다.

두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.

a, b(1 ≤ a, b ≤ N, a != b)

 

[구하는 값]

1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

 

[생각의 흐름]

1번 지역에서 인접한 곳으로 이동하며 지나온 거리를 증가시키다가, K를 넘으면 이동을 하지 않는 방법으로 푼다.

dfs,bfs 무엇을 써도 무방하다.

dfs로 하면 한 마을에 인접한 마을의 최대 수가 50인데 한번 방문한 곳은 방문하지 않기 때문에

시간복잡도는 50x49x48...=250만.

백트래킹시에 방문체크 해제를 하지 않아야 재방문을 피한다.

 

인접마을을 표현할 땐 인접배열과 인접리스트 중에서 인접리스트를 썼다.

a->b로 가는 경로가 여러개가 있을 수도 있기 때문이다. 인접배열을 쓴다면

[a][b]에는 가중치가 하나만 저장된다. (->사실 최소로 갱신하면 되는데 이땐 몰랐다)
그래서 인접리스트로 표현을 했고, dfs 탐색시에 방문했던 마을이라고 무조건 안가는 것이 아니라

그 방문체크값을 확인해서 이전보다 빠른 경로로 왔다고 판단될 때에만 그곳을 가도록 만든다.
그렇기때문에 탐색이 진행되기 위해선 방문체크값의 초기값은 큰 수이어야 하며

이러한 탐색 방식을 다익스트라라고 한다.

 

그렇게 기존에 방문한 비용에 비해 절약된 비용으로 다른 노드를 갈 수 있다는 것에 의미가 있다.

 

 

[코드]

import java.util.ArrayList; 
import java.util.Arrays; 

class Solution {  //프로그래머스는 static으로 모두 선언해서 하지 않고 인스턴스 solution으로 돌리므로 다 인스턴스 변수여야 한다.   
   int ans=1;    //즉 메인 만들어서 돌려볼때 인스턴스로 접근해야 한다는 뜻. 대신 메인에서 무슨 기능 넣으면 안됨,,초기지역도 포함해야되서 1로 시작 
   int visit[]=new int[51];  //전역변수 할거는 전역변수로! 
   int K,N; 
   ArrayList<ArrayList<int[]>> adj=new ArrayList<ArrayList<int[]>>(); 
   public static void main(String[] args) { 
      int[][] arr= { 
            {1,2,1},{2,3,3},{5,2,2},{1,4,2},{5,3,1},{5,4,2} 
      }; 
      Solution m=new Solution(); 
      System.out.print(m.solution(5,arr,3)); 
   } 

    public int solution(int N, int[][] road, int K) {   
       Arrays.fill(visit,Integer.MAX_VALUE);  //수에 관한건 Integer에서, 배열 관련한 함수는 Arrays에! 
       this.N=N; 
       this.K=K; 
        for(int i=0;i<51;i++)  
           adj.add(new ArrayList<int[]>());  //이중어레 초기화 필요 
         
       for(int i=0;i<road.length;i++) { 
           adj.get(road[i][0]).add(new int[]{road[i][1],road[i][2]});  //int[]는 Integer처럼 쓰인다  
           adj.get(road[i][1]).add(new int[]{road[i][0],road[i][2]}); 
        } 
         
        dfs(1,0); 
        return ans; 
    } 
     
    public void dfs(int cur,int len) { 
       visit[cur]=len; 
        
       for(int[] nx:adj.get(cur)) { 
          if(nx[1]+len>K||visit[nx[0]]<nx[1]+len)  //다익스트라. 같은 지점 간다면 더 짧을때만 갈 수 있다. 
             continue;   //왜냐?a~b사이 가중치 여러개 있을 수 있어서 가봤다고 아예 안가면 안됨 
          if(visit[nx[0]]==Integer.MAX_VALUE)  //0이 안갔단 표시가 아님 
             ans++; 
          dfs(nx[0],nx[1]+len); 
       }    
    } 
}