[백준] 2206번 : 벽 부수고 이동하기 - 자바[Java]⭐

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

풀이

BFS를 사용하여 최단 경로를 구하는 문제다.

 

이동하는 도중에 최대 1개까지 벽을 부수고 이동할 수 있기 때문에, 처음 풀 때는 모든 벽에 대해서 1개씩 부서졌을 때 BFS를 수행했다. 하지만 시간초과가 났다.

 

다른 사람의 풀이를 찾아본 결과 visited 배열을 3차원으로 선언하여 벽을 부쉈을 때와 부수지 않았을 때를 따로 처리하였다.

boolean[][][] visited = new boolean[n][m][2]; // [r][c][0] = 벽을 부수지 않고 이동한 경우 , [r][c][1] = 벽을 부수고 이동한 경우

 

BFS 수행 과정

1. (0, 0) 좌표에서 시작한다. 시작하는 칸도 포함해서 카운트하기 때문에 dist는 1, destroyed는 false로 설정한다.

 

2. while문을 사용하여 큐가 빈 상태가 될 때까지 다음을 반복한다.

1) 현재 (n-1, m-1) 좌표라면 dist를 반환한다.

2) 4방향에 대해 검사를 수행한다.

2-1) 인덱스 밖이면 continue

2-2) 벽을 이미 부수고 이동한 경우

해당 칸을 방문하지 않았고 벽이 없다면 (!visited[nr][nc][1] && map[nr][nc] == 0) -> visited[nr][nc][1]을 true로 변경하고 큐에 추가한다.

2-3) 벽을 아직 안 부순 경우

i) 벽 안 부수고 이동하기

!visited[nr][nc][0] && map[nr][nc] == 0 -> visited[nr][nc][0]을 true로 변경하고 큐에 추가한다.

ii) 벽 부수고 이동하기

!visited[nr][nc][1] && map[nr][nc] == 1 -> visited[nr][nc][1]을 true로 변경하고 큐에 추가한다.

 

3. while문이 종료되면, -1을 반환한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, m;
    static int[][] map;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

    static class Node {
        int r, c, dist;
        boolean destroyed;

        public Node (int r, int c, int dist, boolean destroyed) {
            this.r = r;
            this.c = c;
            this.dist = dist;
            this.destroyed = destroyed;
        }
    }

    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());
        map = new int[n][m];

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

        int minDist = bfs();
        System.out.println(minDist);
    }

    static int bfs() {
        Queue<Node> q = new ArrayDeque<>();
        boolean[][][] visited = new boolean[n][m][2]; // [r][c][0] = 벽을 부수지 않고 이동한 경우 , [r][c][1] = 벽을 부수고 이동한 경우

        q.add(new Node(0, 0, 1, false)); // r, c, dist, destroyed
        visited[0][0][0] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();

            if (cur.r == n-1 && cur.c == m-1) {
                return cur.dist;
            }

            boolean destroyed = cur.destroyed;

            for (int d = 0; d < 4; d++) {
                int nr = cur.r + dr[d];
                int nc = cur.c + dc[d];

                // 인덱스 범위 밖
                if (nr < 0 || nr >= n || nc < 0 || nc >= m) {
                    continue;
                }
                if (destroyed) { // 벽을 이미 부수고 이동한 경우
                    if (!visited[nr][nc][1] && map[nr][nc] == 0) {
                        visited[nr][nc][1] = true;
                        q.add(new Node(nr, nc, cur.dist+1, true));
                    }
                }
                else { // 벽을 아직 안 부순 경우
                    if (!visited[nr][nc][0] && map[nr][nc] == 0) { // 벽 안 부수고 이동하기
                        visited[nr][nc][0] = true;
                        q.add(new Node(nr, nc, cur.dist+1, false));
                    }
                    else if (!visited[nr][nc][1] && map[nr][nc] == 1) { // 벽 부수고 이동하기
                        visited[nr][nc][1] = true;
                        q.add(new Node(nr, nc, cur.dist+1, true));
                    }
                }
            }
        }

        return -1;
    }
}

참고

나의 풀이는 이미 벽을 부수고 이동했는지 아직 안 부순 상태인지를 기준으로 처리했다면 

참고한 풀이는 이동한 다음 칸이 벽인지 아닌지를 기준으로 처리하였다.

[백준] 2206 : 벽 부수고 이동하기 (JAVA/자바)

 

백준 2206번 : 벽 부수고 이동하기 (JAVA) 문제 풀이