백준 3055번: 탈출 (Python/Java)

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

3055번: 탈출

 

 

 

접근

---

문제 설정이나 출력 예시만 조금 다를 뿐, 백준 5427번 불(https://www.acmicpc.net/problem/5427)과 아예 똑같은 문제다. 백준 5427번 풀이를 작성한 적이 있으니(https://codestation.tistory.com/14) 참고하면 될 것이다.

 

 

 

풀이

---

Python

from collections import deque

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

height, width = map(int, (input()).split())
board = [["" for i in range(width)] for i in range(height)]
visitList = [[False for i in range(width)] for i in range(height)]

bfsDeque = deque()
hedgehog = []
for i in range(height):
    firstLine = input()
    for j in range(width):
        board[i][j] = firstLine[j]

        if board[i][j] == "*":
            bfsDeque.append([i, j, 0, 0])
        elif board[i][j] == "S":
            hedgehog = [i, j]

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

result = -1
while bfsDeque:
    thisDeque = bfsDeque.popleft()

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

        if 0 <= subHeight < height and 0 <= subWidth < width:
            if not visitList[subHeight][subWidth]:
                if thisDeque[2] == 0:
                    if board[subHeight][subWidth] == ".":
                        board[subHeight][subWidth] = "*"
                        visitList[subHeight][subWidth] = True
                        bfsDeque.append([subHeight, subWidth, 0, (thisDeque[3] + 1)])

                elif thisDeque[2] == 1:
                    if board[subHeight][subWidth] == ".":
                        visitList[subHeight][subWidth] = True
                        bfsDeque.append([subHeight, subWidth, 1, (thisDeque[3] + 1)])
                    elif board[subHeight][subWidth] == "D":
                        result = (thisDeque[3] + 1)
                        break
    
    if result != -1:
        break

if result == -1:
    print("KAKTUS")
else:
    print(result)

 

Java

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

public class Main {
    
    static int[] upDown = {-1, 1, 0, 0}, leftRight = {0, 0, -1, 1};

    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
        
        String[] firstLine = (scan.nextLine()).split(" ");
        int height = Integer.parseInt(firstLine[0]), width = Integer.parseInt(firstLine[1]);
        
        String[][] board = new String[height][width];
        boolean[][] visitList = new boolean[height][width];

        Queue<int[]> bfsQueue = new LinkedList<>();
        int[] hedgehog = new int[2];
        for(int i = 0 ; i < height ; i++){
            String[] secondLine = (scan.nextLine()).split("");
            for(int j = 0 ; j < width ; j++){
                board[i][j] = secondLine[j];

                if(board[i][j].equals("*")){
                    bfsQueue.add(new int[] {i, j, 0, 0});
                }else if(board[i][j].equals("S")){
                    hedgehog = new int[] {i, j};
                }
            }
        }
        bfsQueue.add(new int[] {hedgehog[0], hedgehog[1], 1, 0});

        int result = -1;
        loop:
        while(!bfsQueue.isEmpty()){
            int[] thisQueue = bfsQueue.poll();

            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(!visitList[subHeight][subWidth]){
                        if(thisQueue[2] == 0){
                            if(board[subHeight][subWidth].equals(".")){
                                board[subHeight][subWidth] = "*";
                                visitList[subHeight][subWidth] = true;
                                bfsQueue.add(new int[] {subHeight, subWidth, 0, (thisQueue[3] + 1)});
                            }

                        }else if(thisQueue[2] == 1){
                            if(board[subHeight][subWidth].equals(".")){
                                visitList[subHeight][subWidth] = true;
                                bfsQueue.add(new int[] {subHeight, subWidth, 1, (thisQueue[3] + 1)});
                            
                            }else if(board[subHeight][subWidth].equals("D")){
                                result = (thisQueue[3] + 1);
                                break loop;
                            }

                        }
                    }
                }

            }
        }

        if(result == -1){
            System.out.println("KAKTUS");
        }else{
            System.out.println(result);
        }
    }

}

 

 

 

후기

---

후기라고 할 게 필요한가 싶을 정도로 백준 5427번과 똑같은 문제다. 가끔 백준에서 문제를 풀다 보면 이런 경우가 있는데, 이번 문제는 아니지만 어떤 문제는 코드를 그대로 복사 붙여 넣기 했는데도 정답이 뜬 경우가 있었다.

 

어쨌든 이렇게 빠르게 같은 류의 문제를 다시 만나게 될 줄을 몰랐다. 비슷한 문제를 만나더라도 풀이 방법은 생각날지언정 정확히 언제 풀었던 몇번 문제인지 생각나는 경우는 없었는데 이번에는 그게 생각날 정도였다. 읽자마자 '이거 그 문제인데...?' 싶었지만 어쨌든 이왕 들어가서 확인한 거 다시 한번 풀어보자는 생각으로 풀어본 문제.