[백준: Python] 4179 - 불!

[문제]

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

동시에 발생하는 상황을 시뮬레이션해야 하는 문제입니다.

 

동시 시뮬레이션이라고 특별한 기법이 필요한 것은 아니고 진행 상황을 처리해두기만 하면 됩니다.

 

그렇기 때문에 코드 상에서, 불이 먼저 번지든, 지훈이가 먼저 이동하든 상관없습니다.

---

[초기화]

    def __init__(self):
        self.r, self.c = map(int, input().split())
        self.grid = [list(input()) for _ in range(self.r)]

---

[풀이]

    def search_jihoon(self):
        for i in range(self.r):
            for j in range(self.c):
                if self.grid[i][j] == 'J':
                    self.grid[i][j] = '.'  # 위치를 공백으로 변경
                    return i, j

지훈이의 위치를 탐색합니다.

    def search_fires(self):
        fires = deque()
        for i in range(self.r):
            for j in range(self.c):
                if self.grid[i][j] == 'F':
                    fires.append((i, j, 0))  # 불의 위치와 시간 추가
        return fires

불의 위치를 저장합니다. 불이 여러 개 있다는 조건은 없지만, 경험 상 2개 이상의 불이 있을 것이라 생각했습니다.

 

위치의 경우 편의상 큐로 치리하였습니다.

    def solve(self):
        y, x = self.search_jihoon()
        fires = self.search_fires()
        fire_time = [[1e10] * self.c for _ in range(self.r)]  # 불 확산 시간 테이블 초기화

        while fires:  # 불 확산
            fy, fx, ft = fires.popleft()
            if fire_time[fy][fx] <= ft:  # 이미 더 빠르게 도달한 경우 스킵(갱신된 경우)
                continue
            fire_time[fy][fx] = ft
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                my, mx = fy + dy, fx + dx
                if 0 <= my < self.r and 0 <= mx < self.c and self.grid[my][mx] == '.' and fire_time[my][mx] == 1e10:
                    fires.append((my, mx, ft + 1))

        dq = deque([(y, x, 0)])  # 지훈이 이동
        visited = [[False] * self.c for _ in range(self.r)]
        visited[y][x] = True

        while dq:
            y, x, t = dq.popleft()
            if y == 0 or y == self.r - 1 or x == 0 or x == self.c - 1:  # 가장자리에 도달한 경우 탈출 성공
                print(t + 1)  # 현재 시간 + 1이 탈출 시간
                return

            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # 이동 가능한 경우 탐색
                my, mx = y + dy, x + dx
                if 0 <= my < self.r and 0 <= mx < self.c and not visited[my][mx] and self.grid[my][mx] == '.':
                    if t + 1 < fire_time[my][mx]:  # 불보다 빨리 도달 가능한지 확인
                        visited[my][mx] = True
                        dq.append((my, mx, t + 1))

        print("IMPOSSIBLE")  # 탈출 불가한 경우

fire_time은 불이 어느 시점에 퍼졌는지 저장하기 위한 자료구조입니다.

 

시점을 기록하며 일반적인 BFS를 수행하면 되겠습니다.

 

다음은 지훈이가 맵에 가장자리에 도달할 때까지 BFS를 수행합니다.

 

추가되는 조건은 방문 시점에 해당 지점에 불이 번지지 않았을 때만 이동하도록 처리합니다.

---

[전체 코드]

from collections import deque


class Main:
    def __init__(self):
        self.r, self.c = map(int, input().split())
        self.grid = [list(input()) for _ in range(self.r)]

    def search_jihoon(self):
        for i in range(self.r):
            for j in range(self.c):
                if self.grid[i][j] == 'J':
                    self.grid[i][j] = '.'  # 위치를 공백으로 변경
                    return i, j

    def search_fires(self):
        fires = deque()
        for i in range(self.r):
            for j in range(self.c):
                if self.grid[i][j] == 'F':
                    fires.append((i, j, 0))  # 불의 위치와 시간 추가
        return fires

    def solve(self):
        y, x = self.search_jihoon()
        fires = self.search_fires()
        fire_time = [[1e10] * self.c for _ in range(self.r)]  # 불 확산 시간 테이블 초기화

        while fires:  # 불 확산
            fy, fx, ft = fires.popleft()
            if fire_time[fy][fx] <= ft:  # 이미 더 빠르게 도달한 경우 스킵(갱신된 경우)
                continue
            fire_time[fy][fx] = ft
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                my, mx = fy + dy, fx + dx
                if 0 <= my < self.r and 0 <= mx < self.c and self.grid[my][mx] == '.' and fire_time[my][mx] == 1e10:
                    fires.append((my, mx, ft + 1))

        dq = deque([(y, x, 0)])  # 지훈이 이동
        visited = [[False] * self.c for _ in range(self.r)]
        visited[y][x] = True

        while dq:
            y, x, t = dq.popleft()
            if y == 0 or y == self.r - 1 or x == 0 or x == self.c - 1:  # 가장자리에 도달한 경우 탈출 성공
                print(t + 1)  # 현재 시간 + 1이 탈출 시간
                return

            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # 이동 가능한 경우 탐색
                my, mx = y + dy, x + dx
                if 0 <= my < self.r and 0 <= mx < self.c and not visited[my][mx] and self.grid[my][mx] == '.':
                    if t + 1 < fire_time[my][mx]:  # 불보다 빨리 도달 가능한지 확인
                        visited[my][mx] = True
                        dq.append((my, mx, t + 1))

        print("IMPOSSIBLE")  # 탈출 불가한 경우


problem = Main()
problem.solve()

---