[Python] SW Expert Academy #1953 탈주범 검거

📚문제: #1953 탈주범 검거(모의 SW 역량테스트)

전체 코드

# 1953. 탈주범 검거

from collections import deque

# 탈주범이 위치할 수 있는 장소의 개수를 구하는 함수 : bFS 구현
def loc(G, s, l, t):
    
    # 시작지점(맨홀 뚜껑의 위치)
    cur_r, cur_c = s
    
    # 큐 선언
    q = deque()
    
    # 시작지점 추가 (파이프의 종류, 현재 위치, 시간)
    init = (G[cur_r][cur_c], [cur_r, cur_c], 1)
    
    # 큐에 추가
    q.append(init)
    
    # 시작 지점 방문처리
    G[cur_r][cur_c] = 'v'
    
    # 시간 내 방문 가능한 지역
    cnt = 0
    
    # 큐가 빌 때까지 반복
    while q:
        
        pipe, cur, time = q.popleft()
        
        # 현재 위치
        cur_r, cur_c = cur
        
        # 시간이 L초 이하일 때 가능한 지역에 추가
        if time <= l:
            
            cnt += 1
            
        if pipe == 1:
            
            dr = [-1, 1, 0, 0]
            dc = [0, 0, -1, 1]
            
            for i in range(4):
                
                move_r, move_c = cur_r + dr[i], cur_c + dc[i]
                
                # 영역을 벗어나지 않으면서
                if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:
                    
                    # 이미 방문하지 않은 지역, 터널을 구성하는 파이프가 있는 곳 일 때
                    if G[move_r][move_c] != 'v' and G[move_r][move_c] > 0:
                        
                        if i == 0:
                            
                            if G[move_r][move_c] in [1, 2, 5, 6]:

                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                                
                        elif i == 1:
                            
                            if G[move_r][move_c] in [1, 2, 4, 7]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                                
                        elif i == 2:
                            
                            if G[move_r][move_c] in [1, 3, 4, 5]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                                
                        elif i == 3:
                            
                            if G[move_r][move_c] in [1, 3, 6, 7]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                        
        elif pipe == 2:
            
            dr = [-1, 1]
            dc = [0, 0]
            
            for i in range(2):
                
                move_r, move_c = cur_r + dr[i], cur_c + dc[i]
                
                if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:
                    
                    if G[move_r][move_c] != 'v' and G[move_r][move_c] > 0:
                        
                        if i == 0:

                            if G[move_r][move_c] in [1, 2, 5, 6]:

                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                                
                        elif i == 1:
                            
                            if G[move_r][move_c] in [1, 2, 4, 7]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
            
        elif pipe == 3:
            
            dr = [0, 0]
            dc = [-1, 1]

            for i in range(2):
                
                move_r, move_c = cur_r + dr[i], cur_c + dc[i]
                
                if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:
                    
                    if G[move_r][move_c] != 'v' and G[move_r][move_c] > 0:
                        
                        if i == 0:    
                            
                            if G[move_r][move_c] in [1, 3, 4, 5]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'

                        elif i == 1:
                            
                            if G[move_r][move_c] in [1, 3, 6, 7]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                            
        elif pipe == 4:
            
            dr = [-1, 0]
            dc = [0, 1]

            for i in range(2):
                
                move_r, move_c = cur_r + dr[i], cur_c + dc[i]
                
                if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:
                    
                    if G[move_r][move_c] != 'v' and G[move_r][move_c] > 0:
                        
                        if i == 0:

                            if G[move_r][move_c] in [1, 2, 5, 6]:

                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                        
                        elif i == 1:
                            
                            if G[move_r][move_c] in [1, 3, 6, 7]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
            
        elif pipe == 5:
            
            dr = [0, 1]
            dc = [1, 0]

            for i in range(2):
                
                move_r, move_c = cur_r + dr[i], cur_c + dc[i]
                
                if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:
                    
                    if G[move_r][move_c] != 'v' and G[move_r][move_c] > 0:
                        
                        if i == 0:    
                            
                            if G[move_r][move_c] in [1, 3, 6, 7]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                        
                        elif i == 1:
                            
                            if G[move_r][move_c] in [1, 2, 4, 7]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
            
        elif pipe == 6:
            
            dr = [0, 1]
            dc = [-1, 0]

            for i in range(2):
                
                move_r, move_c = cur_r + dr[i], cur_c + dc[i]
                
                if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:
                    
                    if G[move_r][move_c] != 'v' and G[move_r][move_c] > 0:
                        
                        if i == 0:    
                            
                            if G[move_r][move_c] in [1, 3, 4, 5]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                        
                        elif i == 1:
                            
                            if G[move_r][move_c] in [1, 2, 4, 7]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'

        elif pipe == 7:
            
            dr = [-1, 0]
            dc = [0, -1]

            for i in range(2):
                
                move_r, move_c = cur_r + dr[i], cur_c + dc[i]
                
                if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:
                    
                    if G[move_r][move_c] != 'v' and G[move_r][move_c] > 0:
                        
                        if i == 0:    
                            
                            if G[move_r][move_c] in [1, 2, 5, 6]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                        
                        elif i == 1:
                            
                            if G[move_r][move_c] in [1, 3, 4, 5]:
                                
                                # 큐에 추가
                                q.append((G[move_r][move_c], [move_r, move_c], time + 1))

                                # 방문처리
                                G[move_r][move_c] = 'v'
                  
    # 답안 출력
    print("#{} {}".format(t, cnt))
    
# 테스트 케이스의 개수 T
T = int(input())

# T개의 테스트 케이스
for t in range(1, T+1):
    
    # N, M, R, C, L이 주어진다.
    N, M, R, C, L = map(int, input().split())
    
    # 지하 터널
    graph = []
    
    # N 줄에 걸쳐 지하터널 지도정보가 주어진다.
    for _ in range(N):
        
        # 1 ~ 7은 터널 구조물 타입, 0은 터널이 없는 장소
        graph.append(list(map(int, input().split())))
    
    # 맨홀 뚜껑의 위치
    hole = [R, C]
    
    # 함수 실행
    loc(graph, hole, L, t)

아이디어

BFS + Simulation 문제, 이웃 파이프를 탐색할 때 현재 파이프의 모양과 맞물려서 이동가능한지 따져본다. 현재 파이프에서 이동방향(상, 하, 좌, 우 등)에 따라 맞물릴 수 있는 파이프가 달라진다.