벽 부수고 이동하고 - 2206번

---

풀이 방법

처음에는 그냥 bfs로 풀이했다가 고생했다. 이 문제는 벽을 부수고 이동할때와 그냥 이동했을 경우 따로 visited를 구분해줘야 한다.

부수고 이동했을때 이전 이동한 경로를 다시 가면 안되지만 부수지 않았으면 부수고 이동했을때 갔던 노드를 가도 된다.

방문체크를 구분해서 해주는 것만 생각해주면 되는 문제이다.

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
    int x, y, distance;
    boolean check;

    Node(int x, int y, int distance, boolean check) {
        this.x = x;
        this.y = y;
        this.distance = distance;
        this.check = check;
    }

    @Override
    public int compareTo(Node other) {
        if (this.distance > other.distance)
            return -1;
        return 1;
    }
}

public class Main {
    static int[][] array;
    static boolean[][][] visited;
    static int[][] way = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int N, M;

    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());

        array = new int[N + 1][M + 1];
        visited = new boolean[2][N + 2][M + 2];

        for (int i = 0; i < visited[0].length; i++) {
            Arrays.fill(visited[0][i], true);
            Arrays.fill(visited[1][i], true);
        }

        for (int i = 1; i < N + 1; i++) {
            String str = br.readLine();
            for (int j = 1; j < M + 1; j++) {
                array[i][j] = str.charAt(j - 1) - '0';
                visited[0][i][j] = false;
                visited[1][i][j] = false;
            }
        }

        System.out.print(bfs());

    }

    static int bfs() {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(1, 1, 1, false));

        while (!q.isEmpty()) {
            Node node = q.poll();
            if (node.x == N && node.y == M)
                return node.distance;

            for (int i = 0; i < way.length; i++) {
                if (!node.check) {
                    if (!visited[0][node.x + way[i][0]][node.y + way[i][1]]) {
                        visited[0][node.x + way[i][0]][node.y + way[i][1]] = true;
                        visited[1][node.x + way[i][0]][node.y + way[i][1]] = true;
                        if (array[node.x + way[i][0]][node.y + way[i][1]] == 0) {
                            q.offer(new Node(node.x + way[i][0], node.y + way[i][1], node.distance + 1, node.check));
                        } else if (array[node.x + way[i][0]][node.y + way[i][1]] == 1) {
                            q.offer(new Node(node.x + way[i][0], node.y + way[i][1], node.distance + 1, true));
                        }
                    }
                } else {
                    if (!visited[0][node.x + way[i][0]][node.y + way[i][1]] && !visited[1][node.x + way[i][0]][node.y + way[i][1]]) {
                        visited[1][node.x + way[i][0]][node.y + way[i][1]] = true;
                        if (array[node.x + way[i][0]][node.y + way[i][1]] == 0) {
                            q.offer(new Node(node.x + way[i][0], node.y + way[i][1], node.distance + 1, node.check));
                        }
                    }
                }

            }
        }
        return -1;
    }
}