[백준] 4179 불! (python 파이썬)

4179번: 불!

---

 
반나절 삽질한 BFS문제. 문제가 어렵게 느껴지진 않았는데 시간초과, 메모리초과 등등 오답파티가 됐다.

---

아이디어

- 문제에서 탈출 조건이 가장자리에 접한 공간에서 탈출할 수 있다고 한다.
이 말은 지훈이가 가장자리에 도착만 하면 자동으로 탈출 가능하다.
 
- 순서는 지훈이가 한번 이동하고 나서 불이 확산되고 1초가 지난다.
 
- 만약 지훈이가 이동한 후 위치에 불이 번진다면 그곳은 못 가는 위치이다.
 
- 이 문제를 해결하려면 지훈과 불 각각의 큐를 만들어서 BFS를 하는 방법과 아니면 큐 하나만 사용해서 BFS를 하는 방법이 있다. 나는 내가 이해하기 쉬웠던 전자의 방법으로 문제를 해결했다.

---

전체 코드

from collections import deque
import sys

input = sys.stdin.readline

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

R, C = map(int, input().rstrip().split())

maze = []
cutTime = 0
fireList = deque()
startPos = deque()

for i in range(R):
    maze.append(list(input().rstrip()))
    for j in range(C):
        if maze[i][j] == 'J':
            startPos.append((i, j, 0))

        elif maze[i][j] == 'F':
            fireList.append((i, j, 0))

while startPos:
    cutTime += 1

    while startPos and startPos[0][2] < cutTime:
        x, y, answer = startPos.popleft()

        if (x == 0 or x == R - 1 or y == 0 or y == C - 1) and maze[x][y] == 'J':
            print(answer + 1)
            exit()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if maze[nx][ny] == '.':
                    maze[nx][ny] = 'J'
                    startPos.append((nx, ny, answer + 1))

    while fireList and fireList[0][2] < cutTime:

        x, y, t = fireList.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if maze[nx][ny] == '.' or maze[nx][ny] == 'J':
                    maze[nx][ny] = 'F'
                    fireList.append((nx, ny, t + 1))

print("IMPOSSIBLE")

---

코드 설명

for i in range(R):
    maze.append(list(input().rstrip()))
    for j in range(C):
        if maze[i][j] == 'J':
            startPos.append((i, j, 0))

        elif maze[i][j] == 'F':
            fireList.append((i, j, 0))

 
지훈의 좌표와 불의 좌표들을 시간과 함께 큐에 따로따로 넣어 준다.
 

while startPos:
    cutTime += 1

    while startPos and startPos[0][2] < cutTime:
        x, y, answer = startPos.popleft()

        if (x == 0 or x == R - 1 or y == 0 or y == C - 1) and maze[x][y] == 'J':
            print(answer + 1)
            exit()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if maze[nx][ny] == '.':
                    maze[nx][ny] = 'J'
                    startPos.append((nx, ny, answer + 1))

    while fireList and fireList[0][2] < cutTime:

        x, y, t = fireList.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if maze[nx][ny] == '.' or maze[nx][ny] == 'J':
                    maze[nx][ny] = 'F'
                    fireList.append((nx, ny, t + 1))

 
그리고 각 1초를 기준으로 동작하게끔 작성했다.
먼저 지훈이를 이동시킨다. 만약 위치가 모퉁이라면 정답을 출력하고 종료한다.
아니라면 빈곳을 찾아 이동시켜 주고 좌표와 시간을 넣어준다. 
 
여기서 while문에 무한반복 하지 않도록 startPos [0][2] < cutTime 조건을 추가해 준다.
이렇게 하면 다음 시간으로 넘어간 것들은 반복하지 않는다. 
 
지훈이가 이동이 끝나면, 불을 확산시켜 준다. 방법은 지훈이를 이동시킨 방법과 유사하다.
 
startPos가 빌 때까지 1초씩 증가시키며 반복한다.
 
startPos가 빈 채로 while문이 종료했다면, 탈출 불가라는 의미이므로 "IMPOSSIBLE"을 출력해 준다.