[BOJ] 1261.알고스팟(priorityQueue).java

#. Problem

https://www.acmicpc.net/problem/1261

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

처음에 무작정 그냥 Queue로 풀었었는데..

메모리 초과s..

이 문제는 단순히 최단 경로를 구하는 것이 아니라,

최소 비용의 경로를 구하는 것이다.

비용을 가지고 경로를 찾아야가 하므로 priorityQueue를 사용해서 풀어야 한다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer;   public class BOJ1261 {       static int[] dx = {-1,1,0,0};     static int[] dy = {0,0,-1,1};     static int res = 0;     // 좌표를 저장하는 class     static class pos implements Comparable<pos>{         int x;         int y;         int dist;                  public pos(int x, int y, int dist) {             this.x = x;             this.y = y;             this.dist = dist;         }           @Override         public int compareTo(pos o) {             return Integer.compare(this.dist, o.dist);         }              }          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine(), " ");                  int M = Integer.parseInt(st.nextToken());    // 가로         int N = Integer.parseInt(st.nextToken());    // 세로         int[][] map = new int[N][M];    // 미로 정보         boolean[][] visited = new boolean[N][M];    // 부순 벽의 개수 정보                  for (int i = 0; i < N; i++) {             String input = br.readLine();             for (int j = 0; j < M; j++) {                 map[i][j] = input.charAt(j) - '0';             }         }                  // 최소 비용의 경로를 구해야 하므로 BFS 적용         PriorityQueue<pos> q = new PriorityQueue<>();         // 시작은 (1,1), 이동거리는 0         q.add(new pos(0, 0, 0));         visited[0][0] = true;         while(!q.isEmpty()) {             pos now = q.poll();             // 도착지점에 도착했을 경우 종료             if(now.x == N-1 && now.y == M-1) {                 res = now.dist;                 break;             }             // 인접한 길을 확인             for (int d = 0; d < 4; d++) {                 int xx = now.x + dx[d];                 int yy = now.y + dy[d];                 // 범위를 벗어날 경우 pass                 if(xx < 0 || yy < 0 || xx >= N || yy >= M) continue;                 // 이미 왔던 길이면 pass                 if(visited[xx][yy]) continue;                 // 처음 오는 길이면 방문처리                 visited[xx][yy] = true;                 // 인접한 길이 빈 방이라면                 if(map[xx][yy] == 0) {                     // 큐에 넣어주고                     q.add(new pos(xx, yy, now.dist));                 }                 else {                     // 빈 방이 아니라면 벽을 부수고 큐에 넣자                     q.add(new pos(xx, yy, now.dist + 1));                 }             }         }                  System.out.println(res);     }   }   Colored by Color Scripter

cs

line 14~30) 좌표와 해당 좌표까지의 비용을 저장하는 class

line 26~28) 비용 기준, 비용이 적은 순으로 priorityQueue가 만들어져야 하므로 compareTo Overriding이 필요

line 55) priorityQueue는 우리가 기준으로 잡은 비용이 가장 작은 것부터 뽑아준다.

line 62~80) 경로를 탐색하는 과정에에 범위를 벗어날 경우, 이미 왔던 길인 경우는 pass 해주고

    그렇지 않은 경우, 방문 처리를 해주고, 그 다음 조건에 맞게 Queue에 넣어준다.

    이 부분은 평범한 BFS와 동일하다. 

* 가장 중요한 포인트는 최소 비용의 경로를 구하기 위해서,

  최소 비용을 들고 경로를 찾아야가 하므로 priorityQueue를 사용해주어야 한다는 것!