(백준 4179 불!

• tags : (algorithm

  No matching post could be found

  - (BFS
• 문제 링크 : https://www.acmicpc.net/problem/4179
• 풀이 링크
  • Python

• 불이 번지는 것, 지훈이가 이동하는 것을 동시에 처리하는 조금 번거로운 BFS문제
• 여기서, 불이 번지는 것을 먼저 처리하고, 지훈이의 이동은 불과 벽에 따라 정해지므로 이 순서만 생각하면 조금 쉽게 해결할 수 있다.

while fires:
    time, x, y = fires.popleft()
    if fire_time[x][y] >= 0:
        continue
    fire_time[x][y] = time
    for d in range(4):
        nx, ny = x + dx[d], y + dy[d]
        if 0 <= nx < R and 0 <= ny < C:
            if maze[nx][ny] != "#":
                fires.append((time + 1, nx, ny))

• 우선 불이 번지는 과정을 먼저 진행했다. 물론 불이 번지는것과 지훈이의 이동을 동시에 진행해도 좋지만, 이 방식이 조금은 편할 것 같아서 선택했다.
• 불은 각 위치별 어느 시간에 도착하는지 표시했다.

while queue:
    time, x, y = queue.popleft()
    if x < 0 or x >= R or y < 0 or y >= C:
        ans = time
        break
    if -1 != fire_time[x][y] <= time or visited[x][y]:
        continue
    visited[x][y] = True
    for d in range(4):
        nx, ny = x + dx[d], y + dy[d]
        if 0 <= nx < R and 0 <= ny < C:
            if not visited[nx][ny] and maze[nx][ny] != "#":
                queue.append((time + 1, nx, ny))
        else:
            queue.append((time + 1, nx, ny))

• 지훈이의 이동은 세가지 조건을 확인하며 진행한다.
  • 첫 번째는 벽으로 이동할 수 없다.
  • 두 번째는 각 위치별 이동시간이 불이 번지기 전이여야 한다.
  • 세 번째는 범위를 벗어난 경우 탈출 성공으로 확인한다.
• 물론, 각 위치에서 방문확인을 해야 시간초과를 피할 수 있다.