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

벽 부수고 이동하기

벽 부수기를 한번으로 제한하는 문장을 포함하여 bfs를 돌린다는 것은 쉽지만,

6 6
000000
011111
011111
010100
010110
000110

이것과 같이 벽을 뚫었던 길과 벽을 뚫지 않은 길이 붙게되면 -1이 출력되어버리는 반례가 있습니다.

그러므로 visited를 삼중배열을 만들어 구별해야 합니다. 벽이 뚫린적 없으면 visited[][][0]에 계속 저장을 하고 벽이 뚫린적 있으면 visited[][][1]로 옮겨 두 길을 분리하여 줍니다.

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 {
    public static int N;
    public static int M;
    public static String[][] map;
    public static boolean[][][] visited;
    public static Queue<Struct> queue = new LinkedList<>();
    public static int[] di = {-1, 1, 0, 0};
    public static int[] dj = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < N; i++) {
            String tmp = br.readLine();
            map[i] = tmp.split("");
        }

        queue.offer(new Struct(0, 0, 1, 0));
        visited[0][0][0] = true;
        System.out.println(bfs());
    }

    public static int bfs() {
        while (!queue.isEmpty()) {
            Struct struct = queue.poll();

            if (struct.i == N - 1 && struct.j == M - 1) {
                return struct.count;
            }

            for (int n = 0; n < 4; n++) {
                int tmpI = struct.i + di[n];
                int tmpJ = struct.j + dj[n];
                int breakCount = struct.breakCount;

                if (tmpI < 0 || tmpI >= N || tmpJ < 0 || tmpJ >= M || visited[tmpI][tmpJ][breakCount] == true) continue;
                if (map[tmpI][tmpJ].equals("1") && struct.breakCount == 1) continue;

                if (map[tmpI][tmpJ].equals("1") && struct.breakCount == 0) {
                    breakCount = 1;
                }

                visited[tmpI][tmpJ][breakCount] = true;
                queue.offer(new Struct(tmpI, tmpJ, struct.count + 1, breakCount));
            }
        }

        return -1;
    }

    static class Struct {
        int i;
        int j;
        int count;
        int breakCount;

        public Struct(int i, int j, int count, int breakCount) {
            this.i = i;
            this.j = j;
            this.count = count;
            this.breakCount = breakCount;
        }
    }
}