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

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

SW Expert Academy

5번째 풀어보는 문제라 거의 외우다시피 한 문제다.

풀 때마다 조금씩 아이디어가 달라지긴 하지만 큰 틀은 바뀌지 않는다.

 

깔끔한 BFS 문제로 pass까지 42분 소요했다.

• 터널 1~7가지 종류를 각각 상하좌우로 뚫려있는지 여부를 0, 1로 미리 마스킹해두어 현 위치에서 나갈 수 있고, 이동할 위치에서 들어올 수 있는지 확인하며 bfs를 탈주범이 갈 수 있는 위치를 확장했다.
• 고려해야 할 부분이라면, bfs 함수 안에서 탈주범은 한 번에 1씩 이동하는데, 같은 시간대에 큐에 담긴 위치들을 확인해줘서 퍼트려야하기 때문에 while문 안에서 큐의 길이만큼 for문을 돌려야 정상적으로 시간 단위로 갈 수 있는 확장된 위치를 반영한다.
  • 이 때 visited에 이동 거리를 표시했고, 거리가 L이상이 되는 순간 그 동안 갈 수 있는 위치의 갯수를 리턴한다.

 

파이썬 코드는 다음과 같다.

---

from collections import deque

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)
rev = (1, 0, 3, 2)

tunnel = [[],
          [1, 1, 1, 1],
          [1, 1, 0, 0],
          [0, 0, 1, 1],
          [1, 0, 0, 1],
          [0, 1, 0, 1],
          [0, 1, 1, 0],
          [1, 0, 1, 0]]

def bfs(sr, sc):
    visited = [[0] * M for _ in range(N)]
    visited[sr][sc] = 1
    Q = deque([(sr, sc)])
    result = 1
    while Q:
        qlen = len(Q)
        for _ in range(qlen):
            r, c = Q.popleft()
            for d in range(4):
                if not tunnel[A[r][c]][d]:
                    continue
                nr = r + dr[d]
                nc = c + dc[d]
                if not (0 <= nr < N and 0 <= nc < M):
                    continue
                if not A[nr][nc] or visited[nr][nc]:
                    continue
                if tunnel[A[nr][nc]][rev[d]]:
                    if visited[r][c] + 1 > L:
                        return result
                    visited[nr][nc] = visited[r][c] + 1
                    Q.append((nr, nc))
                    result += 1
    return result

# main
T = int(input())
for tc in range(T):
    N, M, R, C, L = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    print("#{} {}".format(tc+1, bfs(R, C)))

---

* 고찰 : Masking하는 방식이 생각보다 코드를 많이 줄일 수 있고, 실수를 찾기에도 쉽다. 비교적 간단한 BFS 문제였다. Keep Going!