백준 2206번 : 벽 부수고 이동하기 (JAVA) 문제 풀이

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

2206번: 벽 부수고 이동하기

---

 

✏️ 문제

 

🔐 문제 해결

예를들어 아래와 같은 5X5 배열이 있다고 해보자

0 0 0 0 0
1 1 1 0 1
0 0 0 0 1
0 1 1 1 1
0 0 0 1 0

 

그림으로 표시하면 아래와 같을 것이다.

화살표 방향과 같이 시작점(0,0) 에서는 두 가지 방향으로 갈 수 있을 것이다.

하지만 1번으로 벽을 뚫고 간다면, 아래의 문제점에 부딪히게 된다.

도착지점으로 가기 위해서는 벽(빨간 지점)을 부숴야 하는데, 이미 벽을 부쉈으므로 가지 못하게 되어 1번 방향은 정답이 아니게 된다. 

그럼 2번 방향으로 진행을 한다면? 가는 길에 벽이 없기 때문에 빨간 지점까지는 도달할 수 있지만, 이미 1번 케이스에서 지나간 길을 방문 표시했기 때문에 도달하지 못하게 된다.

 

그렇기 때문에, 벽을 부수고 진행하는 케이스와 부수지 않고 진행하는 케이스의 방문 처리하는 배열을 하나로 두고 쓰면 이러한 문제점이 발생한다.

 

방문 처리 배열을 아래와 같이 선언해줘야 한다.

// 3차원 배열 : [벽을 부쉈는지 0,1]
boolean[][][] visit = new boolean[2][N][M];

 

다음 칸으로 이동할 때의 벽이 있는지 없는지에 따라서 처리하는 과정이 다음과 같다.

• 다음 칸에 벽이 있을 경우
  1. 벽을 부순적이 없는지 체크
  2. 해당 벽을 이전에 부수고 방문한 적이 없는지
• 다음 칸에 벽이 없을 경우
  1. 벽을 부순 여부에 따라 다음 칸을 방문했는지 체크

정확하게 이해가 되지 않는다면 아래의 코드를 참고하면 된다.

// 다음 칸에 벽이 있을 때 -> (1) 벽을 부순적이 없는지 체크
//                        (2) 이전의 '해당 벽'을 부수고 방문한적이 없는지 체크
if (miro[nX][nY] == '1') {
    if(cur[2] == 0 && !visit[1][nX][nY]){
        visit[cur[2]][nX][nY] = true;    // 방문 처리
        dist[nX][nY] = dist[cur[0]][cur[1]] + 1; // 거리 측정
        qu.offer(new int[]{nX, nY, 1});    // 다시 큐에 넣어줘서 BFS!
    }
}


// 벽이 아닐 경우 -> 벽을 "부순 여부"에 따른 방문을 했는지 체크!
else{
    if(!visit[cur[2]][nX][nY]){
        
        // 해당 칸을 방문을 안했을 때!
        visit[cur[2]][nX][nY] = true;    // 방문 처리
        dist[nX][nY] = dist[cur[0]][cur[1]] + 1; // 거리 측정
        qu.offer(new int[]{nX, nY, cur[2]}); // 다시 큐에 넣어줘서 BFS!
    }
}

// 도착지점에 도달 했을 때 출력하고 종료!
if(nX == N-1 && nY == M-1){
    System.out.print(dist[nX][nY] + 1);
    System.exit(0);
}

 

 

🖥 전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 시작지점과 도착지점이 같을 경우!
        if(N-1 == 0 && M-1 == 0){
            System.out.print(1);
            System.exit(0);
        }
        
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        char[][] miro = new char[N][M];  // 미로 배열
        int[][] dist = new int[N][M];    // 거리 측정 배열
        boolean[][][] visit = new boolean[2][N][M];    // 벽을 부순 여부에 따라 방문 여부 기록
        Queue<int[]> qu = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            String s = bf.readLine();
            for (int j = 0; j < M; j++) {
                miro[i][j] = s.charAt(j);
            }
        }

        // 시작점 세팅 (x좌표, y좌표, crash 여부)
        qu.offer(new int[]{0, 0, 0});   

        while (!qu.isEmpty()) {
            int[] cur = qu.poll();  // 현재 위치 뽑기
            
            // 상,하,좌,우 탐색
            for(int i=0; i<4; i++){
                int nX = cur[0] + dx[i];
                int nY = cur[1] + dy[i];

                if (nX < 0 || nX >= N || nY < 0 || nY >= M) {
                    continue;
                }
                
                // 다음 칸에 벽이 있을 때 -> (1) 벽을 부순적이 있는지 체크
                //                        (2) 그 벽을 방문한적이 있는지 체크
                if (miro[nX][nY] == '1') {
                    if(cur[2] == 0 && !visit[1][nX][nY]){
                        visit[cur[2]][nX][nY] = true;    // 방문 처리
                        dist[nX][nY] = dist[cur[0]][cur[1]] + 1; // 거리 측정
                        qu.offer(new int[]{nX, nY, 1});    // 다시 큐에 넣어줘서 BFS!
                    }
                }
                // 벽이 아닐 경우 -> 벽을 "부순 여부"에 따른 방문을 했는지 체크!
                else{
                    if(!visit[cur[2]][nX][nY]){
                        // 해당 칸을 방문을 안했을 때!
                        visit[cur[2]][nX][nY] = true;    // 방문 처리
                        dist[nX][nY] = dist[cur[0]][cur[1]] + 1; // 거리 측정
                        qu.offer(new int[]{nX, nY, cur[2]}); // 다시 큐에 넣어줘서 BFS!
                    }
                }
                // 도착지점에 도달 했을 때 출력하고 종료!
                if(nX == N-1 && nY == M-1){
                    System.out.print(dist[nX][nY] + 1);
                    System.exit(0);
                }
            }
        }
        // 도달을 못했으므로 -1 출력!
        System.out.print(-1);
    }
}