SWEA 1953 탈주범 검거

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

요약: 경과된 시간이 주어질 때 탈주범이 위치할 수 있는 장소의 개수를 계산하는 프로그램을 작성하라.

복잡한 조건을 가지고 격자를 탐색할 수 있어야한다.
총 7 가지 모양의 파이프가 있고, 각 파이프마다 연결된 방향이 다르다.
따라서 이 각각의 파이프 모양과 조건을 간단하게 표현할 수 있어야 한다.

이를 pipes와 connected 두가지 변수를 이용해서 나타냈다.
pipes는 해당 파이프 모양이 어떤 방향으로 연결되어있는지 나타낸다.
connected는 탐색할 곳의 파이프와 현재 파이프가 연결될 수 있는 지를 나타낸다.

이 두 정보를 활용해서 도둑이 있을 수 있는 곳을 알아낼 수 있다.

기본적인 탐색방법은 BFS 알고리즘을 활용했다.

이것을 구현한 코드는 다음와 같다.

전체 코드

'''
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
'''
from collections import deque

# NxM 맵크기
# (R, C) 맨홀 뚜껑 위치
# L시간 후 가능한 위치
N, M, R, C, L = 0, 0, 0, 0, 0

grid = [[0] * 50 for _ in range(50)] # 맵정보
visited = [[0] * 50 for _ in range(50)] # 맵 탐색용
c = 0 # 탈주범이 있을 수 있는 곳 위치 개수

pipes = [ # 파이프별 이동 가능 방향
    [],
    [0, 1, 2, 3], # 1. 상하좌우
	[0, 1], # 2. 상하
	[2, 3], # 3. 좌우
	[0, 3], # 4. 상우
	[1, 3], # 5. 하우
	[1, 2], # 6. 하좌
	[0, 2], # 7. 상좌
]

# 0: 상, 1: 하, 2: 좌, 3: 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
connected = [
    [0, 1, 1, 0, 0, 1, 1, 0],
	[0, 1, 1, 0, 1, 0, 0, 1],
	[0, 1, 0, 1, 1, 1, 0, 0],
	[0, 1, 0, 1, 0, 0, 1, 1]    
]

def search(x, y):
    global grid, visited, pipes, connected, c, N, M, dx, dy
    q = deque()
    q.append((1, x, y))
    visited[x][y] = 1
    
    while q:
        l, cx, cy = q.popleft()
        kind = grid[cx][cy]
        visited[cx][cy] = 1
        
        if l >= L: continue # 시간 초가 지나면 못감
        
        for i in range(len(pipes[kind])):
            nx, ny = cx + dx[pipes[kind][i]], cy + dy[pipes[kind][i]]
            if nx < 0 or nx >= N or ny < 0 or ny >= M: continue # 격자 벗어난 경우
            if visited[nx][ny]: continue # 중복 방문인 경우
            if grid[nx][ny] == 0: continue # 파이프가 아닌 경우
            if connected[pipes[kind][i]][grid[nx][ny]] != 1: continue # 연결된 파이프가 아닌 경우
            
            q.append((l + 1, nx, ny))
            visited[nx][ny] = 1
            c += 1

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    
    N, M, R, C, L = list(map(int, input().split()))
    visited = [[0] * 50 for _ in range(50)] # 맵 탐색용
    for i in range(N):
        grid[i] = list(map(int, input().split()))
            
    c = 1
    search(R, C)
    
    print(f'#{test_case} {c}')