[SWEA] 1953 탈주범 검거

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE&problemTitle=1953

SW Expert Academy

from collections import deque
tunnel = {
    1: [(-1, 0), (1, 0), (0, -1), (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)],   # 상좌
}
for tc in range(1, int(input()) + 1):
    N, M, R, C, L = map(int, input().split())
    _map = [list(map(int, input().split())) for _ in range(N)]
    visited = [[0] * M for _ in range(N)]
    q = deque()
    q.append((R, C))
    visited[R][C] = 1
    def bfs(L):
        result = 1
        while q:
            x, y = q.popleft()
            direction = tunnel[_map[x][y]]
            for i in range(len(direction)):
                dx = x + direction[i][0]
                dy = y + direction[i][1]
                if dx < 0 or dx >= N or dy < 0 or dy >= M: continue
                if visited[dx][dy] or _map[dx][dy] == 0: continue
                if tunnel_chk(x, y, dx, dy): continue
                q.append((dx, dy))
                visited[dx][dy] = visited[x][y] + 1
                if visited[dx][dy] > L:
                    break
                result += 1
        return result

    def tunnel_chk(x, y, dx, dy):
        temp_direction = tunnel[_map[dx][dy]]
        for i in range(len(temp_direction)):
            nx = dx + temp_direction[i][0]
            ny = dy + temp_direction[i][1]
            if x == nx and y == ny: return False
        return True

    print("#{} {}".format(tc, bfs(L)))

여러 조건들이 추가된 bfs 문제이다.

움직일수 있는 방향끼리 뚫려있는지 확인하는 tunnel_chk를 만들었다.

그리고 움직인 범위가 시간 L보다 넘게 걸리면 그 즉시 반복문을 종료시키게 만들었다.

처음에는 return result로 했는데 몇개의 값이 None 이 나와서 반복문을 종료하고 그다음 return 하는 것으로 만들었다.

나머지는 범위 내에있는지, 방문했는지 확인하는등 일반적인 BFS의 조건과 같다.