[알고리즘] 백준4179 불! - 파이썬

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

4179번: 불!

 

 

[풀이 코드]

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

R, C = map(int, input().split())
graph = []
for _ in range(R):
    graph.append(list(input().strip()))

visited = [[0] * C for _ in range(R)]
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'J':
            visited[i][j] = 7
        if graph[i][j] == 'F':
            visited[i][j] = 1

q = deque()
y, x = 0, 0
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'F':
            q.append((i, j, 'F', 0))
        if graph[i][j] == 'J':
            y, x = i, j
q.appendleft((y, x, 'J', 1))

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def bfs():
    while q:
        y, x, z, cnt = q.popleft()
        if visited[y][x] == 7:
            if not (1 <= y < R-1 and 1 <= x < C-1):
                print(cnt)
                exit()

        for l in range(4):
            yy = dy[l] + y
            xx = dx[l] + x
            if 0 <= yy < R and 0 <= xx < C:
                if z == 'J': # 지훈이라면
                    if graph[yy][xx] == '.' and not visited[yy][xx]:
                        visited[yy][xx] = 7
                        q.append((yy, xx, 'J', cnt+1))
                        # print("지호 : ", (yy, xx))

                if z == 'F': # 불이라면
                    if graph[yy][xx] == '.' and visited[yy][xx] in (0, 7):
                        visited[yy][xx] = -1
                        q.append((yy, xx, 'F', 0))

    print("IMPOSSIBLE")
    return

bfs()

• 내가 생각해도 정말 비효율적으로 잘했다. 누군가 혹시나 본다면 다른 사람 블로그를 참고하길..!
  
  
• 먼저, vistied 방문 배열을 만들고 J는 7, F는 1로 초기화했다.
  
  
• 그리고 시간을 조금이나마 줄여주기 위해서 미리 큐에 지훈이와 불을 담았고 지호를 담는 과정에서 무조건 지훈이가 큐의 맨 앞에 오게끔 했다. 
  
  
• bfs안에서는 지훈이가 먼저 이동을 한 뒤 방문 배열 visited를 처리했고, 바로 다음에 불이 퍼지는 경로를 처리해주었다.  불일 경우에 if문은 이동할 수 있는 '.'이고 방문 배열이 지훈이가 움직였던 위치 거나 애초에 이동하지 않았더라면 처리해주는 부분이다.

'''
추가예제입력 

5 5
....F
...J#
....#
....#
...#.
 
출력: 4


3 4
###F
.J#.
###.

출력 : 2

'''

• 구글링을 통해 추가 예제 입력을 더 입력해봤고 뭐가 부족했는지 알 수 있었다.