탈주범 검거 [SWEA 모의 역량 테스트]

1. 문제 접근 방법

- 이 문제 같은 경우는 bfs를 통해 board를 탐색하되,

  board에 있는 파이프의 종류에 따라서,

  현재 지점으로부터 다음 지점이 방문 가능한지를 판단하는 것이 중요한 문제이다. 

-> 이 문제에서 중요한 포인트는, 현재 지점에서 다음 지점으로 방문가능한지 판단할 때,

     현재 지점의 파이프 모양과 다음 지점의 파이프 모양을 같이 고려해야 한다는 점이다.

->  이 때 파이썬의 배열의 in을 잘 활용해주면 좋다. 

 

2. 코드

from collections import deque

T = int(input())

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def findAble(type):
    
    if type == 1:
        return [0, 1, 2, 3]
    elif type == 2:
        return [0, 2]
    elif type == 3:
        return [1, 3]
    elif type == 4:
        return [0, 1]
    elif type == 5:
        return [1, 2]
    elif type == 6:
        return [2, 3]
    
    
    return [0, 3]
    
    
    


def bfs(N, M, R, C, L, board, visited):
    
    cnt = 0 
    
    visited[R][C] = True
    cnt += 1 
    q = deque()
    q.append([R, C, 1])
    
    
    while q:
        
        x, y, time = q.popleft()
        
        if time == L:
            continue 
        
        
        type = board[x][y]
        
        able = findAble(type)
        
        for i in range(4):
            if i in able:
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0<=nx and nx<N and 0<=ny and ny<M and board[nx][ny] != 0 and visited[nx][ny] == False:
                    if i == 0 and board[nx][ny] in [1,2,5,6]:
                        visited[nx][ny] = True
                        cnt += 1 
                        q.append([nx, ny, time+1])
                    elif i == 1 and board[nx][ny] in [1,3,6,7]:
                        visited[nx][ny] = True
                        cnt += 1 
                        q.append([nx, ny, time+1])
                    elif i == 2 and board[nx][ny] in [1,2,4,7]:
                        visited[nx][ny] = True
                        cnt += 1 
                        q.append([nx, ny, time+1])
                    elif i == 3 and board[nx][ny] in [1,3,4,5]:
                        visited[nx][ny] = True
                        cnt += 1 
                        q.append([nx, ny, time+1])
    
        
        
        
    return cnt 
    

for i in range(T):
    
    N, M, R, C, L = map(int, input().split())
    
    visited = [[False]*M for _ in range(N)]
    
    board = [] 
    
    for j in range(N):
        row = list(map(int, input().split()))
        board.append(row)
        

    ans = bfs(N, M, R, C, L, board, visited)

    print("#" + str(i+1) + " " + str(ans))