백준 14442번: 벽 부수고 이동하기 2 (Python/Java)

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

14442번: 벽 부수고 이동하기 2

 

 

 

접근

---

조건을 빼고 생각해보자면 간단한 너비 우선 탐색 문제다. 좌측 상단에서 우측 하단까지 경로를 찾아내는 것. 문제는 해당 경로까지 벽을 만났을 때 일정 횟수 부술 수 있다는 것이다. 이 부분을 구현해내는 것이 이 문제의 핵심 포인트다.

 

우리가 정확하게 알아야 할 것은 벽을 아예 부순 적이 없을 때, 한번 부수었을 때, 두 번 부수었을 때... N번 부수었을 때 우리가 접근할 수 있는 경로는 모두 다른 경로라는 점이다. 아래 그림을 살펴보자.

 

좌측 상단에서 우측 상단으로 이동한다고 생각해보자. 만일 1번 케이스처럼 벽을 부수지 않은 경우라면 벽 주위를 모두 돌아 길이 7 경로(문제 조건 상, 시작 지점도 길이에 포함되기 때문)를 이동하여 도착할 수 있다. 하지만 2번 케이스처럼 벽을 한번 부순다면 굳이 돌아갈 필요 없이 길이 3 경로를 통하여 도착할 수 있다.

 

이 경우, 벽을 부수지 않은 경우와 벽을 부순 경우의 탐색을 같은 조건의 탐색 경로로 볼 수 있을까? 당연하게도 그럴 수 없다. 만일 Queue에 넣고 돌린다면 2번 케이스가 우측 상단에 먼저 도착해 탐색 여부에 체크를 할 것이다. 그렇다면 뒤늦게 도착한 1번 케이스는 이미 우측 상단이 탐색 여부가 체크되어 있기 때문에 접근할 수 없다.

 

만일 위 그림과 같이 우측 상단이 아니라 전혀 다른 장소로 가야 하고, 벽들이 계속해서 나타난다면? 2번 케이스에서 부순 벽이 아니라 전혀 다른 벽을 부수어야 할 수도 있다. 그 벽까지는 1번 케이스처럼 이동 가능 공간을 통해 가야 한다. 만일 같은 탐색 경로 체크를 사용한다면 2번 케이스가 이미 벽을 부수고 넘어가 탐색 체크를 하기 때문에 1번 케이스를 통해 다른 벽으로 갈 수 없을 것이고, 이미 한번 벽을 부수었다고 체크되기 때문에 만일 다른 벽으로 도착했다고 하더라도 벽을 부술 수 있는 횟수를 초과해 벽을 부수지 못할 것이다.

 

이를 해결할 수 있는 방법은 분기를 나누는 것이다. 여기서 분기는 벽을 부순 횟수가 될 것이다. 한 번도 부수지 않았을 때 탐색 여부, 한번 부수었을 때 탐색 여부, 두 번 부수었을 때 탐색 여부... N번 부수었을 때 탐색 여부를 따로 체크해두는 것이다. 이렇게 하면 위 설명과 같은 불상사를 피할 수 있게 된다.

 

나 같은 경우는 보통 2차원 배열을 이용해 가로, 세로 좌표를 인덱스로 사용해 탐색 여부를 체크한다. 때문에 3차원 배열로 만들어 가로, 세로, 벽을 부순 횟수를 인덱스로 사용해 탐색 여부를 체크했다. 이 부분만 주의한다면 어렵지 않게 풀 수 있을 것이다.

 

 

 

풀이

---

Python

from collections import deque
import sys

upDown = [-1, 1, 0, 0]
leftRight = [0, 0, -1, 1]

height, width, wallNum = map(int, (sys.stdin.readline()).split())

board = [[0 for i in range(width)] for i in range(height)]
visitList = [[[-1 for i in range(width)] for i in range(height)] for i in range(wallNum+1)]
for i in range(height):
    firstLine = sys.stdin.readline()
    for j in range(width):
        board[i][j] = int(firstLine[j])

bfsDeque = deque()
bfsDeque.append([0, 0, 0, 1])

visitList[0][0][0] = 0
result = 0
resultCheck = False
while bfsDeque:
    thisDeque = bfsDeque.popleft()

    if thisDeque[0] == height-1 and thisDeque[1] == width-1:
        result = thisDeque[3]
        resultCheck = True
        break

    for i in range(4):
        subHeight = (thisDeque[0] + upDown[i])
        subWidth = (thisDeque[1] + leftRight[i])

        if 0 <= subHeight < height and 0 <= subWidth < width:
            if board[subHeight][subWidth] == 0:
                if visitList[thisDeque[2]][subHeight][subWidth] == -1:
                    visitList[thisDeque[2]][subHeight][subWidth] = 0
                    bfsDeque.append([subHeight, subWidth, thisDeque[2], (thisDeque[3]+1)])
            else:
                if thisDeque[2] < wallNum:
                    if visitList[thisDeque[2]+1][subHeight][subWidth] == -1:
                        visitList[thisDeque[2]+1][subHeight][subWidth] = 0
                        bfsDeque.append([subHeight, subWidth, (thisDeque[2]+1), (thisDeque[3]+1)])

if resultCheck:
    print(result)
else:
    print(-1)

 

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int height = Integer.parseInt(firstLine[0]);
        int width = Integer.parseInt(firstLine[1]);
        int wallNum = Integer.parseInt(firstLine[2]);

        int[][] board = new int[height][width];
        int[][][] visitList = new int[wallNum+1][height][width];
        for(int i = 0 ; i < height ; i++){
            String[] secondLine = (scan.nextLine()).split("");
            for(int j = 0 ; j < width ; j++){
                board[i][j] = Integer.parseInt(secondLine[j]);
            }
        }

        int[] upDown = {-1, 1, 0, 0};
        int[] leftRight = {0, 0, -1, 1};

        Queue<int[]> bfsQueue = new LinkedList<>();
        bfsQueue.add(new int[] {0, 0, 0, 1});

        visitList[0][0][0] = -1;
        int result = 0;
        boolean resultCheck = false;
        while(!bfsQueue.isEmpty()){
            int[] thisQueue = bfsQueue.poll();

            if(thisQueue[0] == (height-1) && thisQueue[1] == (width-1)){
                result = thisQueue[3];
                resultCheck = true;
                break;
            }

            for(int i = 0 ; i < 4 ; i++){
                int subHeight = (thisQueue[0] + upDown[i]);
                int subWidth = (thisQueue[1] + leftRight[i]);

                if(subHeight >= 0 && subHeight < height && subWidth >= 0 && subWidth < width){
                    if(board[subHeight][subWidth] == 0){
                        if(visitList[thisQueue[2]][subHeight][subWidth] == 0){
                            visitList[thisQueue[2]][subHeight][subWidth] = 1;
                            bfsQueue.add(new int[] {subHeight, subWidth, thisQueue[2], (thisQueue[3]+1)});
                        }
                    
                    }else{
                        if(thisQueue[2] < wallNum){
                            if(visitList[thisQueue[2]+1][subHeight][subWidth] == 0){
                                visitList[thisQueue[2]+1][subHeight][subWidth] = 1;
                                bfsQueue.add(new int[] {subHeight, subWidth, (thisQueue[2]+1), thisQueue[3]+1});
                            }
                        }
                    }
                }
            }
        }

        if(resultCheck){
            System.out.println(result);
        }else{
            System.out.println(-1);
        }


    }

}

 

 

 

후기

---

이번 문제와 같이 분기를 나눠 탐색 여부 체크를 하는 문제에 조금 약해 고전했던 문제. 하지만 풀이 방법을 한번 생각해내니 구현 자체는 어렵지 않았다. 여기서 한 가지 의문인 점은 python 시간 초과 부분이다. java는 위 코드를 통해 큰 문제없이 통과했는데 python3는 시간 초과가 나서 pypy3로 제출해 통과했다. 어떻게 해야 일반 python으로 통과할 수 있을지, 연산을 조금 더 줄일 수 있는 방법이 있는지 확인해봐야겠다. (해당 문제는 python3로 통과한 사람이 한 명도 없긴 하더라...)