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

link 🔗 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq 

SW Expert Academy

 

1️⃣ BFS 사용

2️⃣ 상 하 좌 우 → 각 방향에서 연결 가능한 파이프 번호 하드코딩

3️⃣ 1부터 7까지, 번호에 따라 연결 가능한 방향 지정

 

from collections import deque
 
def bfs(y, x):
    q = deque()
    q.append((y, x, 1)) # y, x, time
    while q:
        nowy, nowx, time = q.popleft()
        if time == L:
            return
        directy = [-1, 1, 0, 0]  # 상 하 좌 우
        directx = [0, 0, -1, 1]
        pipe = [[1, 2, 5, 6], [1, 2, 4, 7], [1, 3, 4, 5], [1, 3, 6, 7]] # 상 하 좌 우 연결 가능한 파이프
        if arr[nowy][nowx] == 1:  # 상 하 좌 우
            temp = [x for x in range(4)]
        elif arr[nowy][nowx] == 2:  # 상 하
            temp = [0, 1]
        elif arr[nowy][nowx] == 3:  # 좌 우
            temp = [2, 3]
        elif arr[nowy][nowx] == 4:  # 상 우
            temp = [0, 3]
        elif arr[nowy][nowx] == 5:  # 하 우
            temp = [1, 3]
        elif arr[nowy][nowx] == 6:  # 하 좌
            temp = [1, 2]
        else:  # 상 좌
            temp = [0, 2]
 
        for t in temp:
            dy = directy[t] + nowy
            dx = directx[t] + nowx
            if 0 <= dy < N and 0 <= dx < M:
                if check[dy][dx] != 1 and arr[dy][dx] in pipe[t]:
                    check[dy][dx] = 1
                    q.append((dy, dx, time+1))
 
t = int(input())
 
for tc in range(1, t+1):
    N, M, R, C, L = map(int, input().split()) # 세로 크기, 가로 크기, 맨홀 x좌표, 맨홀 y좌표, 시간
    arr = [list(map(int, input().split())) for _ in range(N)]
    check = [[0]*M for _ in range(N)]
    cnt = 0
    check[R][C] = 1
    bfs(R, C)
 
    for i in range(N):
        for j in range(M):
            if check[i][j] == 1:
                cnt += 1
 
    print(f'#{tc} {cnt}')