[알고리즘] 백준 5427번 Python

 

분류

BFS

혼자 힘으로 해결 했는가?

O

느낀 점

BFS를 진행할 때, 독립된 그래프의 순회를 해도 되는 상황이다.

 

우선 BFS 특성 상  동시에 두개의 이동이 가능한 주체에 대한 BFS는 불가능하다.

 

그러나 이 문제는 이동이 가능한 대상이 둘이다.

 

따라서 각각 진행을 하되 앞서서 BFS를 진행한 주체의 타임 스탬프와 비교하는 과정이 필요하다.

---

 

내가 작성한 코드

from collections import deque

# 입력 받기
TC = int(input())
for _ in range(TC):
    bY, bX = map(int, input().split())
    board = [[0 for _ in range(bY)] for _ in range(bX)]
    visF = [[0 for _ in range(bY)] for _ in range(bX)]
    visS = [[0 for _ in range(bY)] for _ in range(bX)]
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    Qf = deque()  # 불의 위치를 저장하는 큐
    Qs = deque()  # 시작 위치를 저장하는 큐

    # 보드 상태 입력 받기
    for i in range(bX):
        row = input()
        for j, c in enumerate(row):
            if c == '#':
                board[i][j] = -1
            else:
                board[i][j] = 0
                if c == '@':
                    Qs.append((i, j))
                    visS[i][j] = 1
                elif c == '*':
                    Qf.append((i, j))
                    visF[i][j] = 1

    # 불에 대한 BFS 수행
    while Qf:
        x, y = Qf.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if nx < 0 or nx >= bX or ny < 0 or ny >= bY or board[nx][ny] == -1 or visF[nx][ny]:
                continue
            visF[nx][ny] = visF[x][y] + 1
            Qf.append((nx, ny))

    # 시작 위치에 대한 BFS 수행
    escape = False
    while Qs and not escape:
        x, y = Qs.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if nx < 0 or nx >= bX or ny < 0 or ny >= bY:
                print(visS[x][y])
                escape = True
                break
            if board[nx][ny] == -1 or visS[nx][ny] or (visF[nx][ny] != 0 and visF[nx][ny] <= visS[x][y] + 1):
                continue
            visS[nx][ny] = visS[x][y] + 1
            Qs.append((nx, ny))
    if not escape:
        print("IMPOSSIBLE")

 

 

 

---

비슷한 문제들

 

4179번

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

4179번: 불!