[SWEA] 1249 보급로 - JAVA

1. 문제

SW Expert Academy

---

2. 풀이

입력

테스트케이스와 무관하게 항상 필요한 변수들이다. 메인 안에 만들었다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(in.readLine());
PriorityQueue<int[]> pQueue = new PriorityQueue<>((o1,o2)->o1[2]-o2[2]);
int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1}};

테스트케이스마다 만들어준 변수들이다. map을 입력받으면서 뒤에서 쓸 distance를 MAX_VALUE로 채웠다.

int N = Integer.parseInt(in.readLine());
int[][] map = new int[N][N];
int[][] distance = new int[N][N];

for(int i=0;i<N;i++){
   String line = in.readLine();
   for(int j=0;j<N;j++){
      map[i][j] = line.charAt(j)-'0';
   }
   Arrays.fill(distance[i],Integer.MAX_VALUE);
}

boolean[][] visited = new boolean[N][N];

 

다익스트라 탐색

1.  처음 위치를 pos에 저장하고 그 위치의 distance를 0으로 만들었다. pQueue에도 넣었다.

2.  pQueue가 빌 때까지 반복한다.(true로 해도 상관없다. 어차피 빠져나가는 조건문이 있다.)

3.  큐에서 맨 처음 값을 뽑아서 그 다음 위치가 범위에 벗어나지 않고 그 위치에 저장된 값이 새로 저장할 값보다 클 때만 갱신한다. 큐에도 같이 넣는다.

4.  마지막으로 도착지 distance[N-1][N-1]을 출력하면 된다.

int[] pos = {0,0,0};
pQueue.offer(pos);
distance[0][0] = 0;

while(!pQueue.isEmpty()){
   pos = pQueue.poll();
   int r = pos[0];
   int c = pos[1];
   int len = pos[2];
   if(r==N-1 && c==N-1) break;
   if(visited[r][c]) continue;
   visited[r][c] = true;

   for(int d=0;d<4;d++){
      int nr = r+deltas[d][0];
      int nc = c+deltas[d][1];
      if(nr>=0 && nr<N && nc>=0 && nc<N && distance[nr][nc]>len+map[nr][nc]){
         distance[nr][nc] = len+map[nr][nc];
         pQueue.offer(new int[]{nr,nc,distance[nr][nc]});
      }
   }
}

sb.append('#').append(tc).append(' ').append(distance[N-1][N-1]).append('\n');

---

3. 결과