백준 5427번: 불 (Python/Java)

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

5427번: 불

 

 

 

접근

---

너비 우선 탐색을 통해 빠른 경로를 탐색할 때는 보통 배열을 비롯한 각자만의 방식으로 자신이 갔던 경로를 체크하고 넘어가는 방식을 쓴다. 여기서 키포인트는 내가 한번 접근했던 경로, 즉 체크된 경로는 다시 접근하지 않는다는 점이다. 이미 접근했던 곳이라면 지금 방법보다 더 빠르게 접근할 수 있는 방법이 있다는 뜻이니 과감하게 넘어가도 된다.

 

이 문제의 키포인트는 총 두 가지로, 이 두 가지만 염두에 두면 어렵지 않게 풀 수 있다. 첫 번째는 평범한 너비 우선 탐색과는 다르게 내가 접근했던 곳이더라도 한번 더 탐색해야 한다는 점이다. 그 이유는 여기서 경로를 탐색하는 주체가 상근이와 불, 이렇게 둘이기 때문이다. 문제 조건상, 상근이는 불이 탐색했던 곳에 접근하지 못하지만 불은 상근이가 탐색한 곳에도 접근할 수 있다. 지금 탐색한 곳이 체크가 되어 있더라도 먼저 체크한 주체가 상근이고 지금 접근한 주체가 불이라면 한번 더 탐색해주자.

 

두 번째 키포인트는 상근이는 '불이 붙으려는 칸'으로 이동할 수 없다는 점이다. 즉, 경로를 탐색할 때 상근이보다 불이 먼저 경로를 탐색해야 한다. 상근이가 접근하려는 구역이 '불이 붙으려는 칸'임을 확인할 수 있는 방법은 불이 상근이보다 먼저 경로를 탐색해 해당 구역을 체크하는 것이다. 물론 불은 상근이가 있었던 곳도 접근할 수 있다. 상근이가 죽어봤자 "'IMPOSSIBLE'을 출력해야 한다" 그 이상, 그 이하의 의미도 없다. 잔혹한 알고리즘의 세계.

 

 

 

풀이

---

Python

from collections import deque

roundNum = int(input())

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

result = ""
for i in range(roundNum):
    width, height = map(int, (input()).split())
    board = [["" for i in range(width)] for i in range(height)]
    visitList = [[[-1, -1] for i in range(width)] for i in range(height)]

    person = []
    bfsDeque = deque()
    for j in range(height):
        widthList = input()
        for k in range(width):
            board[j][k] = widthList[k]

            if board[j][k] == "@":
                person = [j, k]
                visitList[j][k][0] = 0
                visitList[j][k][1] = 0
            elif board[j][k] == "*":
                bfsDeque.append([1, j, k, 0])
                visitList[j][k][0] = 1
                visitList[j][k][1] = 0

    bfsDeque.append([0, person[0], person[1], 0])

    resultCheck = False
    while bfsDeque:
        thisDeque = bfsDeque.popleft()

        for j in range(4):
            thisHeight = (thisDeque[1] + upDown[j])
            thisWidth = (thisDeque[2] + leftRight[j])

            if 0 <= thisHeight < height and 0 <= thisWidth < width:
                if visitList[thisHeight][thisWidth][0] == -1 and board[thisHeight][thisWidth] != "#":
                    if thisDeque[0] == 0:
                        visitList[thisHeight][thisWidth][0] = 0
                        visitList[thisHeight][thisWidth][1] = (thisDeque[3]+1)
                        bfsDeque.append([thisDeque[0], thisHeight, thisWidth, (thisDeque[3]+1)])

                    elif thisDeque[0] == 1:
                        visitList[thisHeight][thisWidth][0] = 1
                        visitList[thisHeight][thisWidth][1] = (thisDeque[3]+1)
                        bfsDeque.append([thisDeque[0], thisHeight, thisWidth, (thisDeque[3]+1)])

                elif visitList[thisHeight][thisWidth][0] == 0:
                    if thisDeque[0] == 1:
                        visitList[thisHeight][thisWidth][0] = 1
                        visitList[thisHeight][thisWidth][1] = (thisDeque[3]+1)
                        bfsDeque.append([thisDeque[0], thisHeight, thisWidth, (thisDeque[3]+1)])
            else:
                if thisDeque[0] == 0:
                    result += str((thisDeque[3] + 1)) + "\n"
                    resultCheck = True
                    break

        if resultCheck:
            break

    if not resultCheck:
        result += "IMPOSSIBLE\n"

print(result)

 

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] upDown = {-1, 1, 0, 0}, leftRight = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException{
        
        int roundNum = Integer.parseInt(br.readLine());

        String result = "";
        for(int i = 0 ; i < roundNum ; i++){
            String[] firstLine = (br.readLine()).split(" ");
            int width = Integer.parseInt(firstLine[0]), height = Integer.parseInt(firstLine[1]);
            String[][] board = new String[height][width];
            int[][][] visitList = new int[height][width][2];

            int[] person = new int[2];
            Queue<int[]> bfsQueue = new LinkedList<>();
            for(int j = 0 ; j < height ; j++){
                String[] secondLine = (br.readLine()).split("");

                for(int k = 0 ; k < width ; k++){
                    board[j][k] = secondLine[k];

                    if(board[j][k].equals("@")){
                        person = new int[] {j, k};
                        visitList[j][k][0] = -1;
                        visitList[j][k][1] = 0;
                    }else if(board[j][k].equals("*")){
                        bfsQueue.add(new int[] {1, j, k, 0});
                        visitList[j][k][0] = 1;
                        visitList[j][k][1] = 0;
                    }
                }
            }   
            bfsQueue.add(new int[] {-1, person[0], person[1], 0});

            boolean resultCheck = false;
            loop:
            while(!bfsQueue.isEmpty()){
                int[] thisQueue = bfsQueue.poll();

                for(int j = 0 ; j < 4 ; j++){
                    int thisHeight = (thisQueue[1] + upDown[j]);
                    int thisWidth = (thisQueue[2] + leftRight[j]);

                    if(thisHeight >= 0 && thisHeight < height && thisWidth >= 0 && thisWidth < width){
                        if(visitList[thisHeight][thisWidth][0] == 0 && !board[thisHeight][thisWidth].equals("#")){
                            if(thisQueue[0] == -1){
                                visitList[thisHeight][thisWidth][0] = -1;
                                visitList[thisHeight][thisWidth][1] = (thisQueue[3]+1);
                                bfsQueue.add(new int[] {thisQueue[0], thisHeight, thisWidth, (thisQueue[3]+1)});
                            
                            }else if(thisQueue[0] == 1){
                                visitList[thisHeight][thisWidth][0] = 1;
                                visitList[thisHeight][thisWidth][1] = (thisQueue[3]+1);
                                bfsQueue.add(new int[] {thisQueue[0], thisHeight, thisWidth, (thisQueue[3]+1)});
                            }

                        }else if(visitList[thisHeight][thisWidth][0] == -1){
                            if(thisQueue[0] == 1){
                                visitList[thisHeight][thisWidth][0] = 1;
                                visitList[thisHeight][thisWidth][1] = (thisQueue[3]+1);
                                bfsQueue.add(new int[] {thisQueue[0], thisHeight, thisWidth, (thisQueue[3]+1)});
                            }
                        }
                    
                    }else{
                        if(thisQueue[0] == -1){
                            result += Integer.toString((thisQueue[3] + 1)) + "\n";
                            resultCheck = true;
                            break loop;
                        }
                    }
                }
            }
            
            if(!resultCheck){
                result += "IMPOSSIBLE\n";
            }
        }

        System.out.println(result);

    }

}

 

 

후기

---

풀다 보니 놀랐다. 왜 이렇게 코드가 길지? 좋은 습관이라고는 생각하지 않지만, 채점을 한 뒤에는 다른 사람들의 코드 길이를 보는 습관이 있다. 대략 1.5배에서 많으면 2배 정도까지 길이 차이가 났다. 내가 뭔가를 놓치고 꾸질 꾸질 코드로 박아놨다는 뜻이겠지. 내가 작성하면서도 이것저것 조건문이나 변수 선언과 같은 것들이 많다고는 생각했다. 오늘도 역시 반성하고 간다.