PS/SWEA

[SWEA] 1953. νƒˆμ£Όλ²” κ²€κ±° (Python)

gimewn 2022. 4. 5. 23:59

link πŸ”— https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq 

 

SW Expert Academy

SW ν”„λ‘œκ·Έλž˜λ° μ—­λŸ‰ 강화에 도움이 λ˜λŠ” λ‹€μ–‘ν•œ ν•™μŠ΅ 컨텐츠λ₯Ό ν™•μΈν•˜μ„Έμš”!

swexpertacademy.com

 

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}')