[파이썬] SWEA 1953 : 탈주범검거 (test)

[파이썬] SWEA 1953 : 탈주범검거 (test)

• SWEA 1953 : 탈주범검거

---

풀이

방향성 생각

• 각 노드마다 열린 방향을 딕셔너리로 기록하기
• 각 노드마다 이동 시, 둘 다 열려있어야한다.

---

전체코드

from collections import deque

dires = [(1,0),(0,1),(-1,0),(0,-1)]
inside = lambda x,y : 0<=x<W and 0<=y<H

TC = int(input())

table = {
    0 : [0,0,0,0],
    1 : [1,1,1,1],
    2 : [0,1,0,1],
    3 : [1,0,1,0],
    4 : [1,0,0,1],
    5 : [1,1,0,0],
    6 : [0,1,1,0],
    7 : [0,0,1,1]
}

for tc in range(1,TC+1):
    H,W,sy,sx,L = map(int,input().split())

    arr = [list(map(int,input().split())) for _ in range(H)]
    V = [[0]*W for _ in range(H)]
    V[sy][sx] = 1

    Q = deque([(sx,sy,1)])
    while Q:

        x,y,t = Q.popleft()

        for dire,(dx,dy) in enumerate(dires):
            nx,ny = x+dx,y+dy

            if not inside(nx,ny):
                continue

            # 둘 다 열려있는 경우 (도착지점은 반대 방향이 열려있어야한다)
            if table[arr[y][x]][dire] and table[arr[ny][nx]][(dire+2)%4] and not V[ny][nx]:
                Q.append((nx,ny,t+1))
                V[ny][nx] = t+1

    # 도착한 경우 + 유효성 검사
    answer = 0
    for y in range(H):
        for x in range(W):
            if 1<= V[y][x] <= L:
                answer += 1
    print(f"#{tc} {answer}")

---

코멘트

• .