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

벽 부수고 이동하기

풀이

bfs로 그래프에서 목적지에 도착하는 최단거리를 찾는 문제와 비슷하다.
하지만 이번 문제에서는 벽을 한 개까지는 부수고 이동할 수 있다는 조건이 하나 추가된다.

가장 간단하게 생각한다면

그래프에 있는 벽들을 큐에 담고 큐에서 하나씩 꺼내 벽을 이동할 수 있게 변경한 후 bfs를 진행하는 것이다.

이 방법으로 진행하면 예제 코드가 맞다고 나와 제출을 하면 메모리 초과라는 결과를 얻게 된다.

주어진 그래프에서 벽의 개수는 최대 (1,000,000 - 2)이기 때문에 관련된 답도 벽의 개수와 동일하다.

메모리가 부족할 수 밖에 없다.

다른 방법이 필요하다.

큐에 벽을 넣고 하나씩 부수고 복구하고 하는 것은 비용이 많이 든다.

결국 필요한 것은 벽들을 저장하지 않고 벽을 부수고 진행을 나타낼 수 있어야 한다.

그러기 위해 bfs에서 쓰이는 방문 배열을 기존에는 boolean을 사용했는데 이번에는 int를 사용한다.

또한 큐에 저장할 Pair 클래스에는 x,y,dist 뿐만 아니라 현재 진행하고 있는 좌표가 벽을 부수고 진행했는지를 기억할 변수 crush를 추가한다.

현재 진행하고 있는 지점의 crush값이 0이면 벽을 만나도 부수고 진행이 가능하다.

이렇게 하면 방문 배열에는 총 3가지 값이 들어가게 된다.

배열 초기값, 벽을 부수고 진행했을 때 값 1, 그리고 벽을 부수지않고 진행했을 때 값 0

이 후 bfs에서 목적지에 도착하면 도착했을 때 지점의 dist 값을 리턴해주면 정답이 나온다.

코드

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

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int n, m;
    static int[][] graph;
    static int[][] visit;
    static Queue<Pair> queue;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first = br.readLine().split(" ");
        n = Integer.parseInt(first[0]);
        m = Integer.parseInt(first[1]);

        graph = new int[n][m];
        visit = new int[n][m];
        queue = new LinkedList<>();
        ArrayList<Integer> answers = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] t = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                int value = Integer.parseInt(t[j]);
                graph[i][j] = value;
                visit[i][j] = Integer.MAX_VALUE;
            }
        }

        queue.offer(new Pair(0, 0, 1,0));
        int answer = bfs();

        bw.write(answer + "\n");
        br.close();
        bw.close();
    }

    private static int bfs() {
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            if (p.x == n - 1 && p.y == m - 1) {
                return p.dist;
            }
            visit[p.x][p.y] = p.crush;
            for (int i = 0; i < 4; i++) {
                if ((p.x + dx[i] >= 0 && p.x + dx[i] <= n - 1) && (p.y + dy[i] >= 0 && p.y + dy[i] <= m - 1)) { 
                    if(visit[p.x+dx[i]][p.y+dy[i]] > p.crush) { // 방문체크 
                        if (graph[p.x + dx[i]][p.y + dy[i]] != 1) { // 벽이 아니면
                            queue.offer(new Pair(p.x + dx[i], p.y + dy[i], p.dist + 1, p.crush));
                            visit[p.x+dx[i]][p.y+dy[i]] = p.crush;
                        }
                        else { //벽이면
                            if(p.crush == 0) {
                                queue.offer(new Pair(p.x+dx[i], p.y+dy[i], p.dist+1, p.crush+1));
                                visit[p.x+dx[i]][p.y+dy[i]] = p.crush + 1;
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
}

class Pair {
    public int x;
    public int y;
    public int dist;
    public int crush;

    public Pair(int x, int y, int dist, int crush) {
        this.x = x;
        this.y = y;
        this.dist = dist;
        this.crush = crush;
    }
}