백준 4179번: 불! (Python/Java)

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

4179번: 불!

 

 

 

접근

---

조금의 디테일만 다를 뿐 백준 5427번 불(https://www.acmicpc.net/problem/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())

bfsDeque = deque()
thisPlace = []
board = [["" for i in range(width)] for i in range(height)]
visitList = [[0 for i in range(width)] for j in range(height)]
for i in range(height):
    firstLine = input()
    for j in range(width):
        board[i][j] = firstLine[j]

        if board[i][j] == "J":
            thisPlace = [i, j]
        elif board[i][j] == "F":
            bfsDeque.append([i, j, 0, -1])

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

result = 0
resultCheck = False
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 board[subHeight][subWidth] != "#":
                if visitList[subHeight][subWidth] == 0:
                    visitList[subHeight][subWidth] = thisDeque[3]
                    bfsDeque.append([subHeight, subWidth, (thisDeque[2]+1), thisDeque[3]])
                
                elif visitList[subHeight][subWidth] == 1:
                    if thisDeque[3] == -1:
                        visitList[subHeight][subWidth] = thisDeque[3]
                        bfsDeque.append([subHeight, subWidth, (thisDeque[2]+1), thisDeque[3]])
        else:
            if thisDeque[3] == 1:
                result = (thisDeque[2] + 1)
                resultCheck = True
                break
    
    if resultCheck:
        break

if resultCheck:
    print(result)
else:
    print("IMPOSSIBLE")

 

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);

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

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

        Queue<int[]> bfsQueue = new LinkedList<>();
        int[] thisPlace = {0, 0};
        String[][] board = new String[height][width];
        int[][] visitList = new int[height][width];

        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("J")){
                    thisPlace[0] = i;
                    thisPlace[1] = j;
                }else if(board[i][j].equals("F")){
                    bfsQueue.add(new int[] {i, j, 0, -1});
                }
            }
        }
        bfsQueue.add(new int[] {thisPlace[0], thisPlace[1], 0, 1});

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

        if(resultCheck){
            System.out.println(result);
        }else{
            System.out.println("IMPOSSIBLE");
        }
    }

}