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

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

2206번: 벽 부수고 이동하기

bfs문제이다.

 

핵심

1은 벽을 의미하고, 0은 이동할 수 있는 길이다. 만약 벽이 있더라도 1번 부수고 이동할 수 있다.

즉 한 번도 벽을 부수지 않음 -> 벽을 부수고 이동

     벽을 이미 부순 경우 -> 이동 불가

가 된다.

하지만 벽을 부수지 않고 이동한 경우가 더 빠를 수도 있다.

따라서 벽을 부수고 탐색하는 경우와 부수지 않고 탐색하는 경우를 가지고 처리해 주었다.

 

정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        char[][] map = new char[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = line.charAt(j);
            }
        }

        boolean[][][] visited = new boolean[N][M][2];

        int[] dy = {1, 0, -1, 0};
        int[] dx = {0, 1, 0, -1};

        Queue<Location> q = new LinkedList<>();
        q.offer(new Location(0, 0, 1, false));

        while (!q.isEmpty()) {

            Location poll = q.poll();

            if (poll.y == N - 1 && poll.x == M - 1) {
                System.out.println(poll.count);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int moveY = poll.y + dy[i];
                int moveX = poll.x + dx[i];

                if (0 <= moveY && moveY < N && 0 <= moveX && moveX < M) {
                    if (map[moveY][moveX] == '0' && !poll.breakWall && !visited[moveY][moveX][0]) {
                        q.offer(new Location(moveY, moveX, poll.count + 1, false));
                        visited[moveY][moveX][0] = true;
                    } else if (map[moveY][moveX] == '0' && poll.breakWall && !visited[moveY][moveX][1]) {
                        q.offer(new Location(moveY, moveX, poll.count + 1, true));
                        visited[moveY][moveX][1] = true;
                    } else if (map[moveY][moveX] == '1' && !poll.breakWall && !visited[moveY][moveX][1]) {
                        q.offer(new Location(moveY, moveX, poll.count + 1, true));
                        visited[moveY][moveX][1] = true;
                    }
                }
            }
        }
        System.out.println(-1);
    }
}

class Location {
    public int y;
    public int x;
    public int count;
    public boolean breakWall;

    public Location(int y, int x, int count, boolean breakWall) {
        this.y = y;
        this.x = x;
        this.count = count;
        this.breakWall = breakWall;
    }
}

해설

위에 말한 대로 벽을 부수고 탐색하는 경우를 visited [y][x][0]에 넣고, 

벽을 부수고 탐색하는 경우를 visited [y][x][1]에 넣으며 이동한다.

while문을 보면 아래와 같은 경우이다.

벽이 아니다

- 부신 벽이 없다 -> vistied [y][x][0]을 방문처리하고 q에 담음

- 벽을 부순 적이 있음 -> visited [y][x][1]을 방문처리하고 q에 담음

벽이다.

- 벽을 부순 적이 없음, 부순다 -> vistied [y][x][1]을 방문처리하고 q에 담음

- 벽을 부순 적이 있음 -> pass 한다.

만약 끝지점에 도달했다면 해당 count를 반환하고 종료시킨다.

q가 비었을 때까지 끝지점에 도달하지 못한다면 -1을 반환한다.

 

 

배운 점

처음에 bfs를 2번 사용하여 처음과 끝지점에서 시작하여 각 벽에서 만나는 카운트를 더하는 식으로 풀었다.

bfs를 2번 사용하다 보니 시간초과가 나오게 되었다. 위와 같은 풀이를 생각하기는 쉽지 않은 것 같다.

아직 많이 부족하다는 느낌을 받았다. 더 열심히 해야겠다.