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

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

최단경로 찾기 문제이며, 특이한 점은 한번 벽을 뚫을 수 있다는 것이다.

처음에는 부르트 포스로 접근하여, 한 벽 씩 뚫고 다시 메우면서 bfs를 돌리는 방법을 해보았다.

while(!queue.isEmpty()) {
    int drillIdx[] = queue.poll();
    map[drillIdx[0]][drillIdx[1]] = 0; //뚫고,
    bq.offer(new int[]{0, 0, 1});
    bfs();
    map[drillIdx[0]][drillIdx[1]] = 1; //매꿔주고,
    isVisit = new boolean[n][m]; // 초기화.
}

결과는 당연히 시간초과. (지금 생각하니 정말 비효율적..)

 

그래서 변화를 준 것이, 방문 여부 boolean 배열로 만들어서, 벽을 뚫을 때와, 벽을 뚫지 않았을 때 총 2가지 경우를 한번에 생각해줄 수 있도록 boolean 배열을 3차원 배열로 만들어주었다.

isVisit[r][c][0] = true;
isVisit[r][c][1] = true;

마지막 행의 인덱스가 0일 때는, 벽을 한 번도 뚫지 않았을 경우를, 1일 때는 벽을 한 번 뚫었을 경우를 처리해주는 식으로 문제를 풀 수 있었다.

아래는 최종 코드이다.

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

public class Main {
    static int shortestPath = -1; //최단 경로 값.
    static int[][] map;
    static boolean[][][] isVisit;
    static int n;
    static int m;
    static Queue<int[]> bq = new LinkedList<>(); //bfs 사용을 위한 큐.
    public static void main(String[] args) throws IOException {
        //Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        isVisit = new boolean[n][m][2];
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
        //Processing
        bq.offer(new int[]{0, 0, 1, 0});//행, 열, 이동 수, 벽뚫 여부
        bfs();
        //Output
        System.out.println(shortestPath);
    }

    private static void bfs() {
        isVisit[0][0][0] = true;
        isVisit[0][0][1] = true;
        while(!bq.isEmpty()) {
            int[] nowIdx = bq.poll();
            if(nowIdx[0] == n - 1 && nowIdx[1] == m - 1) { // 끝 지점 도달 시.
                if (shortestPath == -1 || nowIdx[2] < shortestPath) {
                    shortestPath = nowIdx[2];
                    continue;
                }
            }
            int dx[] = {1,0,-1,0};
            int dy[] = {0,1,0,-1};
            for (int i = 0; i < 4; i++) {
                int nx = nowIdx[1] + dx[i];
                int ny = nowIdx[0] + dy[i];
                if(!(nx >= 0 && nx < m && ny >= 0 && ny < n)) continue;
                if(map[ny][nx] == 1 && !isVisit[ny][nx][1] && nowIdx[3] == 0) { //길을 뚫어야 할 때.
                    isVisit[ny][nx][1] = true;
                    bq.offer(new int[] {ny, nx, nowIdx[2] + 1, nowIdx[3] + 1});
                }
                else if(map[ny][nx] == 0 && !isVisit[ny][nx][nowIdx[3]]) { //정상적인 경로.
                    isVisit[ny][nx][nowIdx[3]] = true;
                    bq.offer(new int[] {ny, nx, nowIdx[2] + 1, nowIdx[3]});
                }
            }
        }
    }
}

코드 지적은 항상 환영입니다 :)