4179

날짜 : 2023. 05. 01

사용 언어 : python

 

문제

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

 

 

코드

import sys
from collections import deque

q = deque()

def fire():
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    while q:
        x, y, cnt = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(r) and ny in range(c):
                if graph[nx][ny] == '.':  # 불이 붙을 수 있는 위치
                    graph[nx][ny] = cnt + 1  # 불이 붙는 시점 추가
                    visited[nx][ny] = True
                    q.append([nx, ny, cnt+1])  # 큐에 추가
def escape(a, b):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    q.append([a, b, 0])
    while q:
        x, y, cnt = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx not in range(r) or ny not in range(c):  # 탈출 성공
                return cnt + 1
            else:
                if visited[nx][ny] and graph[nx][ny] > (cnt+1):  # 범위체크, 미리 도착 가능
                    graph[nx][ny] = cnt + 1
                    q.append([nx, ny, cnt + 1])  # 큐에 추가
                if graph[nx][ny] == ".":
                    graph[nx][ny] = cnt + 1
                    q.append([nx, ny, cnt + 1])
    return "IMPOSSIBLE"


r, c = map(int, sys.stdin.readline().split())
graph = list()
visited = [[False] * c for _ in range(r)]
for _ in range(r): graph.append(" ".join(sys.stdin.readline().rstrip()).split())

pos = list()
for i in range(r):
    for j in range(c):
        if graph[i][j] == "F":
            q.append([i, j, 0])  # 불이 붙는 위치
        if graph[i][j] == "J":
            pos.append(i)
            pos.append(j)
fire()
"""for i in graph:
    print(i)
print(q)"""

print(escape(pos[0], pos[1]))

 

 

풀이

- 불이 붙었을 때와 지훈이가 탈출하는 경우. 즉, 두 번의 BFS를 돌린다.

- 다만 불이 여러번 붙은 케이스가 있을 수 있기 때문에 처음 이중 for문을 통해 불이 붙은 위치를 큐에 넣고, 지훈이의 위치를 저장한다.

- 그 다음 불이 붙을 때마다 visited 리스트에 불이 붙은 여부를 체크해 놓고, 지훈이가 탈출을 시작할 때 visited[nx][ny]가 True인 경우에는 해당 위치의 그래프 값이 무조건 정수이기 때문에 값을 비교한 후 큐에 삽입할 지 여부를 결정한다.

- 이후 불이 붙지 않았는데 지훈이가 이동할 수 있는 위치가 있을 수 있기 때문에 이 케이스도 체크한다.

- 마지막으로 탈출 함수의 케이스에서 큐가 전부 pop되면 탈출할 수 없는 케이스이기 때문에 "IMPOSSIBLE"을 출력한 후 끝낸다.

 

 

알게된 점

- 어제 진행된 스터디에서 풀었던 문제였고, 계속 TLE가 발생했었다.

- 테케는 계속 맞았는데 시간초과가 계속 떠서 머리를 싸맨 문제였다.

- 어제 개인적으로 공부하면서 풀었던 문제랑 비슷해서 동일한 방식으로 접근했는데 계속 TLE가 발생했고, 그 원인을 찾기 위해 고민했다.

- 맨 처음에는 visited 리스트 없이 불이 붙은 경우 그냥 숫자만 넣어서 진행했고, 지훈이가 탈출하는 경우 in range(r*c)를 통해 체크했다. 아마 이게 TLE 발생 원인이었던 것 같다.

- 그래서 시간을 줄이기 위해 visited 리스트를 만들고 True/False를 판별 후 시간을 체크하는 방식으로 바꾸었더니 바로 풀렸다. (1초에 간당간당하긴 했다.)

- 앞선 문제(https://www.acmicpc.net/problem/3055)에서는 그래프 크기가 최대 50*50이어서 시간초과에 대해 문제가 없었지만 이번문제에서는 최대 1000*1000이어서 TLE가 발생하지 않았나.... 싶다

 

 

참고 사이트

-