[SWEA] 1953. 탈주범 검거 (Python)

BFS! 인데 연결 상태를 확인하는 과정을 제대로 생각해야 한다.

밑으로 갈 수 있어서 갔더니 터널끼리 연결이 안 된 경우인,

+

ㅡ

이런 모양이 있을 수 있기 때문이다.

 

- 풀이 

from collections import deque

tunnel = {
    0: (),
    1: ((1, 0), (0, 1), (-1, 0), (0, -1)),
    2: ((1, 0), (-1, 0)),
    3: ((0, 1), (0, -1)),
    4: ((-1, 0), (0, 1)),
    5: ((1, 0), (0, 1)),
    6: ((1, 0), (0, -1)),
    7: ((-1, 0), (0, -1))
}

t = int(input())
for test in range(1,t+1):
    n, m, r, c, l = map(int, input().split())
    maps = [list(map(int, input().split())) for _ in range(n)]
    visited = [[0]*m for _ in range(n)]
    q = deque([(r, c)])
    visited[r][c] = 1
    cnt = 1

    while q:
        a, b = q.popleft()
        for dx, dy in tunnel[maps[a][b]]:
            nx = dx+a
            ny = dy+b
            if not 0<=nx<n or not 0<=ny<m :
                continue
            if (-dx, -dy) in tunnel[maps[nx][ny]]:
                if not visited[nx][ny]:
                    visited[nx][ny] = visited[a][b] + 1
                    q += [(nx, ny)]
                    if visited[nx][ny] <=l :
                        cnt += 1

    print('#{} {}'.format(test, cnt))