[BOJ] 2206. 벽 부수고 이동하기

문제 원본 : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n, m;

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        char[][] map = new char[n][m];
        for (int i = 0; i < n; ++i) {
            map[i] = br.readLine().toCharArray();
        }

        boolean[][][] v = new boolean[n][m][2];
        int[][] dist = new int[n][m];
        int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(0, 0, 0));

        dist[0][0] = 1;
        while (!q.isEmpty()) {
            Pos p = q.poll();
            for (int i = 0; i < 4; ++i) {
                int ny = p.y + dir[i][0];
                int nx = p.x + dir[i][1];

                if (ny >= 0 && nx >= 0 && ny < n && nx < m) {
                    if (map[ny][nx] == '0' && !v[ny][nx][p.wall]) {
                        q.add(new Pos(ny, nx, p.wall));
                        dist[ny][nx] = dist[p.y][p.x] + 1;
                        v[ny][nx][p.wall] = true;
                    } else if (map[ny][nx] == '1' && p.wall == 0 && !v[ny][nx][1]) {
                        q.add(new Pos(ny, nx, 1));
                        dist[ny][nx] = dist[p.y][p.x] + 1;
                        v[ny][nx][1] = true;
                    }

                    if (ny == n - 1 && nx == m - 1) {
                        bw.write(Integer.toString(dist[ny][nx]));
                        bw.close();
                        br.close();
                        return;
                    }
                }
            }
        }

        if (dist[n - 1][m - 1] == 0) {
            bw.write("-1");
        } else {
            bw.write("1");
        }

        bw.close();
        br.close();
    }

    public static class Pos {
        public int y;
        public int x;
        public int wall;

        public Pos(int y, int x, int wall) {
            this.y = y;
            this.x = x;
            this.wall = wall;
        }
    }
}

• 일반적인 BFS 풀이법으로는 풀 수 없는 문제였다.
• 벽을 한 번 부술 수 있기 때문에 전 단계에서 벽을 부순 상태도 같이 저장하고 있어야 했다.
• 이 문제도 아이디어를 다른 블로그에서 참고했다.
• 골드 4 티어인데 풀이법을 모른다면 체감 난이도는 골드 1쯤 되는 것 같다.