[백준] 2206 벽 부수고 이동하기 (Java)

 

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

 

최단 경로를 찾는 문제이다.

 

모든 점과 점 사이 거리는 1로 동일하기 때문에, BFS로 탐색하면 각 점까지 이동한 거리가 모두 최단경로가 될 것이다.

 

한 가지 조건만 고려하면 되는데, 벽을 딱 한 번 부술 수 있다는 점이다.

 

상태를 나타내는 변수에 broken = 0을 해두고 BFS를 돌리면서 각 벽을 만나면 Broken = 0일때 1로 바꾸고 다시 그 벽을 시작점으로 BFS를 돌리는 방법을 처음에 생각해봤었는데, 이럼 호출횟수가 너무 지나치게 많아질 것 같았다.

 

 보통 이런 탐색을 할 때, 각 점을 방문했는지 안했는지 여부를 나타내는 방문배열을 만들어 사용할 것이다. 이 문제의 경우 공간이 2차원이므로 2차원 형태로 방문배열을 구성했을텐데, 

 

방문배열을 3차원으로 구성해 [x][y][broken 여부] 이렇게 표시한다면, BFS로 쭉 탐색을 하다가 만약 벽을 만났을 때, 이 벽이 이미 부서진 적 있는 점인지 아닌지 visited 배열의 broken가 1인지 아닌지를 확인하면 알 수 있다. 즉 broken이 0이라면 벽을 부순적이 없다는 뜻이기에 큐에 해당 정점과 broken = 1로 전달해 넣어 탐색을 하면 조건을 만족할 수 있을 것이다.

 

import java.io.*;
import java.util.*;

class Node {
    int x, y, dist, broken;

    Node(int x, int y, int dist, int broken) {
        this.x = x;
        this.y = y;
        this.dist = dist;
        this.broken = broken; // 0: 안 부숨, 1: 이미 부숨
    }
}
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());


        int[] dx = {-1, 1, 0, 0}; // 상 하 좌 우
        int[] dy = {0, 0, 1, -1}; // 상 하 좌 우
        int[][] arr = new int[n][m];
        boolean[][][] visited = new boolean[n][m][2];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); j++) {
                int val = line.charAt(j) - '0';
                arr[i][j] = val;
            }
        }

        // bfs
        // List<Integer> result = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0, 1, 0));
        visited[0][0][0] = true;
        int answer = -1;
        while (!queue.isEmpty()) {
            Node current = queue.poll();

            if (current.x == n - 1 && current.y == m - 1) {
                answer = current.dist;
                break;
            }
            for (int i = 0; i < 4; i++) {
            	// 이동
                int curr_x = current.x + dx[i];
                int curr_y = current.y + dy[i];
				
                // 이동할 수 없는 경우
                if (curr_x < 0 || curr_x >= n || curr_y < 0 || curr_y >= m)
                    continue;
				
                // 갈 수 있는 공간(0)을 탐색한 경우
                if (arr[curr_x][curr_y] == 0) {
                    if (!visited[curr_x][curr_y][current.broken]) {
                        visited[curr_x][curr_y][current.broken] = true;
                        queue.add(new Node(curr_x, curr_y, current.dist + 1, current.broken));
                    }
                } else { // 벽을 만난 경우
                    if (current.broken == 0 && !visited[curr_x][curr_y][1]) {
                        visited[curr_x][curr_y][1] = true;
                        queue.add(new Node(curr_x, curr_y, current.dist + 1, 1));
                    }
                }

            }

        }

        System.out.print(answer);
    }
}

 

Java를 오래 놓고 살아서 감각을 거의 잊다보니,, 이번엔 Java로 한번 풀어보았다. 입출력할 때 특히 이런 문제는 0000, 0100 이런 문자열을 각각 쪼개서 int로 바꿔야 하다보니 이걸 조금 헤맸다. (사실 다양한 언어로 풀어보려 하면 항상 입출력에서 제일 고전하는 것 같다)

 

아무튼 문제에서 제시한 공간이 2차원이라고 무조건 visited를 2차원으로 구성할 필요는 없다는 걸 배운 문제였다.