[백준] 4179번 : 불! - Python(파이썬)

문제

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

4179번: 불!

포인트

1. 미로의 다양한 모양에 따른 탈출 여부

꼭 미로의 밑바닥 도달이 탈출하는 것이 아님!

상하좌우로 움직이다가 해당 좌표가 미로 밖에 도달한 경우 탈출 성공

좌표에 따라 여러 공간 타입(. J F #)가 있는데 #는 벽으로 해당 좌표로 이동 불가능

2. 시작점 여러개 & 타이밍에 따른 방문 가능 여부

불과 지훈으로 시작점이 2개

지훈이가 불보다 먼저 방문하거나 불이 접근하지 않는 곳인 경우에만 방문 가능

⭐ (1st) 불 BFS (2nd) 지훈 BFS ⭐

불 BFS를 먼저 돌려서 해당 좌표가 도달 가능한 유효한 곳인지 & 불이 도달하는 시간 기록

그 다음 지훈 BFS를 돌리는데 해당 좌표가 도달 가능한 유효한 곳인지 & 불이 도달하기 전에 지훈이가 먼저 도달하는지

 

전체코드

from collections import deque
import sys
input=sys.stdin.readline

N,M=map(int,input().split())
graph=[list(input().strip()) for _ in range(N)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
F_que, J_que=deque(),deque()
F_visited,J_visited=[[0]*M for _ in range(N)],[[0]*M for _ in range(N)]
#print(N,M,graph,F_visited,J_visited)


def bfs():
    while F_que:
        x,y=F_que.popleft()
        for k in range(4):
            nx,ny=x+dx[k], y+dy[k]
            if 0<=nx<N and 0<ny<M:
                if graph[nx][ny]!="#" and not F_visited[nx][ny]:
                    F_visited[nx][ny]=F_visited[x][y]+1
                    F_que.append((nx,ny))
    while J_que:
        x,y=J_que.popleft()
        for k in range(4):
            nx,ny=x+dx[k], y+dy[k]
            if 0 <= nx < N and 0 <= ny < M:
            # if 0<=nx<N and 0<ny<M:
                 if not J_visited[nx][ny] and graph[nx][ny] != '#':
                  if not F_visited[nx][ny] or F_visited[nx][ny] > J_visited[x][y] + 1:   
                        J_visited[nx][ny] = J_visited[x][y] + 1
                        J_que.append((nx, ny))
            else:
                return J_visited[x][y]+1
    return "IMPOSSIBLE"

for i in range(N):
    for j in range(M):
        if graph[i][j]=="J":
            J_que.append((i,j))
        elif graph[i][j]=="F":
            F_que.append((i,j))

print(bfs())

#print(F_visited)
#print (J_visited)