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