[Java] 백준 BOJ / 2206번: 벽 부수고 이동하기

벽 부수고 이동하기

문제

---

문제 설명

문제를 읽으면서 그래프 탐색이라는 것은 바로 알 수 있을 거고 이 문제가 가지는 특징은 한 개의 벽을 부수고 이동하는 것이 가능하다는 점이다.

벽을 부수고 이동한다는 것을 코드 내에서 구현하기 위해서는 방문 배열인 visited 배열을 기존 그래프처럼 2차원 배열로 구현하는 것이 아닌 아래와 같은 3차원 배열로 구현하여 벽을 부쉈는지 아닌지 판단하는 것이 중요하다.

boolean visited = new boolean[2][n][m];

다음 칸으로 이동할 때의 벽 여부에 따라 처리하는 과정은 다음과 같다.

1. 다음 칸에 벽이 있을 경우

   • 벽을 부순적이 없는지 확인
   • 해당 벽을 이전에 부수고 방문한 적이 있는지 확인
   • 만약에 이전에 부수고 방문한 적이 있다면 갈 수 없다는 뜻

2. 다음 칸에 벽이 없을 경우

   • 벽을 부순 여부에 따라 다음 칸을 방문했는지 확인

위 설명에 대한 코드는 아래와 같다.

if (map[nx][ny] == 1) {
//벽을 부순적이 있는지, 방문했는지 확인
	if (cur.crashed == 0 && !visited[1][nx][ny]) {
		visited[cur.crashed][nx][ny] = true;
		dist[nx][ny] = dist[cur.x][cur.y] + 1;
		queue.offer(new Point(nx, ny, 1));
	}
}

/**
* 벽이 없으면 벽을 부순 여부에 따라 방문 여부를 체크
*/
else {
	if (!visited[cur.crashed][nx][ny]) {
		visited[cur.crashed][nx][ny] = true;
		dist[nx][ny] = dist[cur.x][cur.y] + 1;
		queue.offer(new Point(nx, ny, cur.crashed));
	}
}

따라서 아래와 같이 코드를 작성해서 이 문제를 풀었다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_2206 {
    static int n, m;
    static int[][] map;
    static int[][] dist;
    static boolean[][][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static Queue<Point> queue = new LinkedList<Point>();

    static class Point {
        int x;
        int y;
        int crashed;

        public Point(int x, int y, int crashed) {
            this.x = x;
            this.y = y;
            this.crashed = crashed;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        if (n - 1 == 0 && m - 1 == 0) {
            System.out.println(1);
            return;
        }

        map = new int[n][m];
        dist = new int[n][m];
        visited = new boolean[2][n][m];

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
            }
        }

        queue.offer(new Point(0, 0, 0));

        while (!queue.isEmpty()) {
            Point cur = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue;
                }

                /**
                 * 만약 다음 칸에 벽이 있다면
                 * 1. 벽을 부순적이 없는지 체크하고
                 * 2. 이전의 해당 벽을 부수고 방문한적이 없는지
                 */
                if (map[nx][ny] == 1) {
                    //벽을 부순적이 있는지, 방문했는지 확인
                    if (cur.crashed == 0 && !visited[1][nx][ny]) {
                        visited[cur.crashed][nx][ny] = true;
                        dist[nx][ny] = dist[cur.x][cur.y] + 1;
                        queue.offer(new Point(nx, ny, 1));
                    }
                }

                /**
                 * 벽이 없으면 벽을 부순 여부에 따라 방문 여부를 체크
                 */
                else {
                    if (!visited[cur.crashed][nx][ny]) {
                        visited[cur.crashed][nx][ny] = true;
                        dist[nx][ny] = dist[cur.x][cur.y] + 1;
                        queue.offer(new Point(nx, ny, cur.crashed));
                    }
                }

                if (nx == n - 1 && ny == m - 1) {
                    System.out.println(dist[nx][ny] + 1);
                    return;
                }
            }
        }
        System.out.println(-1);
    }
}

---

정리

벽을 부수는 것을 어떻게 해야하나 고민을 했었는데 3차원 배열을 사용해서 풀 수 있다는 점을 알아서 나중에도 이런 문제가 있으면 새로운 방식을 떠올릴 수 있을 것 같고 생각하지 못했던 반례가 있었는데 만약에 예제 입력으로

1 1
0

이 들어오면 답은 0 인데 이 부분은 처음에 입력 받을 때 처리를 해줘야한다.