[백준/JAVA] 1261번: 알고스팟

문제 보러가기

1261번: 알고스팟

[문제 풀이]

다익스트라를 사용하여 풀었는데, 사실 풀고나서도 긴가민가하다.

좌표 이동을 (x+1, y), (x-1, y), (x, y+1), (x, y-1)로 하면서 동시에 좌표 이동했을 때에 뚫게 되는 벽의 수를 기존의 다익스트라 배열 값과 비교하여 좌표 이동했을 때가 벽의 수가 더 적다면 배열을 갱신을 하고 이동된 좌표를 큐에 넣는다. 큐에서 좌표를 꺼내 다시 좌표이동을 하고 비교를 하였다. 다익스트라 배열에는 해당 좌표로 이동하는 최소한의 뚫은 벽의 개수가 저장된다.

 

태그에 그래프가 있기에 List를 사용해야할지 고민을 해보았는데, 구현도 너무 복잡하고 어차피 좌표 이동은 제한적이기 때문에 조건을 많이 거는 것으로 선택했다.

 

[코드]

import java.io.*; import java.util.*; class Main {     static int N, M;     static int[][] maps;     static long[][] dijk;     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         StringTokenizer st = new StringTokenizer(br.readLine());         // N과 M의 순서 주의         M = Integer.parseInt(st.nextToken());          N = Integer.parseInt(st.nextToken());         maps = new int[N + 1][M + 1];         dijk = new long[N + 1][M + 1];         for (int i = 1; i <= N; i++) {             char[] chars = br.readLine().toCharArray();             Arrays.fill(dijk[i], Integer.MAX_VALUE); // 벽의 개수를 최소한으로 만들기 위한 초기화, 100001이상이면 된다.             for (int j = 1; j <= M; j++) {                 maps[i][j] = chars[j - 1] - 48;             }         }         dijk[1][1] = 0; //시작점(1, 1)은 항상 뚫려있기에 뚫은 벽은 0개이다.         dijkstra();         bw.write(dijk[N][M] + "");         bw.close();     }     public static void dijkstra() {         Queue<int[]> queue = new LinkedList<>();         queue.add(new int[]{1, 1}); //출발점(1, 1)         while (!queue.isEmpty()) {             int[] temp = queue.poll();             int x = temp[0];             int y = temp[1];             if (range(x + 1, y)) { //좌표이동 후, 값 비교                 if (dijk[x + 1][y] > dijk[x][y] + maps[x + 1][y]) {                     dijk[x + 1][y] = dijk[x][y] + maps[x + 1][y];                     queue.add(new int[]{x + 1, y});                 }             }             if (range(x, y + 1)) { //좌표이동 후, 값 비교                 if (dijk[x][y + 1] > dijk[x][y] + maps[x][y + 1]) {                     dijk[x][y + 1] = dijk[x][y] + maps[x][y + 1];                     queue.add(new int[]{x, y + 1});                 }             }             if (range(x - 1, y)) { //좌표 이동 후, 값 비교                 if (dijk[x - 1][y] > dijk[x][y] + maps[x - 1][y]) {                     dijk[x - 1][y] = dijk[x][y] + maps[x - 1][y];                     queue.add(new int[]{x - 1, y});                 }             }             if (range(x, y - 1)) { // 좌표 이동 후, 값 비교                 if (dijk[x][y - 1] > dijk[x][y] + maps[x][y - 1]) {                     dijk[x][y - 1] = dijk[x][y] + maps[x][y - 1];                     queue.add(new int[]{x, y - 1});                 }             }         }     }     public static boolean range(int x, int y) { //해당 좌표가 정상 범위에 있는지 확인         return x >= 1 && y >= 1 && x <= N && y <= M;     } }