[SWEA] 1953. 탈주범 검거 (python)

문제 바로가기 : [모의 SW 역량 테스트] 탈주범 검거

SW Expert Academy

문제 요약

• 지하 터널에서 탈주범이 L시간 후에 있을 수 있는 위치를 모두 구하는 문제
• 탈주범의 초기 위치가 주어지고 1시간에 1칸 이동할 수 있으며 파이프의 모양에 따라 이동할 수 있는 곳이 제한된다.

접근 방법

• BFS를 활용한다.
• 리스트를 활용하여 파이프 모양에 따라 이동할 수 있는 방향을 정해줬다.

내가 푼 코드

def bfs(y, x):
    global cnt
    Q.append([y, x])
    visited[y][x] = 1
    while Q:
        t = Q.pop(0)
        a = arr[t[0]][t[1]] - 1
        for i in di[a]:
            if i[0] == 0:
                nx = t[1] + i[1]
                ny = t[0]
                if 0 <= nx < M and 0 <= ny < N and visited[ny][nx] == 0 and arr[ny][nx] != 0:
                    if [0, -i[1]] in di[arr[ny][nx]-1]:
                        visited[ny][nx] = visited[t[0]][t[1]] + 1
                        if visited[ny][nx] > L:
                            return
                        Q.append([ny, nx])
                        cnt += 1
            elif i[1] == 0:
                nx = t[1]
                ny = t[0] + i[0]
                if 0 <= nx < M and 0 <= ny < N and visited[ny][nx] == 0 and arr[ny][nx] != 0:
                    if [-i[0], 0] in di[arr[ny][nx]-1]:
                        visited[ny][nx] = visited[t[0]][t[1]] + 1
                        if visited[ny][nx] > L:
                            return
                        Q.append([ny, nx])
                        cnt += 1


T = int(input())
for tc in range(1, T+1):
    N, M, R, C, L = map(int, input().split())
    # N : 가로 크기, M : 세로 크기, R : 맨홀 뚜껑의 세로 위치
    # C : 맨홀 뚜껑의 가로 위치 L : 탈출 후 소요된 시간

    arr = [list(map(int, input().split())) for _ in range(N)]  # 지하 터널 지도

    Q = [] # Queue를 사용
    visited = [[0] * M for _ in range(N)] # visited 값 초기화

    cnt = 1 # 탈주범이 있을 수 있는 곳의 갯수 : 초기값 1

    # 리스트를 만들어 파이프 모양에 따라 (1 ~ 7) 움직일 수 있는 방향 설정 
    di = [
            [[-1, 0], [1, 0], [0, -1], [0, 1]],
            [[-1, 0], [1, 0]],
            [[0, -1], [0, 1]],
            [[-1, 0], [0, 1]],
            [[1, 0], [0, 1]],
            [[1, 0], [0, -1]],
            [[-1, 0], [0, -1]],
         ]
    bfs(R, C)


    # for i in range(N):
    #     for j in range(M):
    #         print(visited[i][j], end=" ")
    #     print()
    # print()

    print('#{} {}'.format(tc, cnt))

문제 총평

• 모의 A형 치고는 어려운 편은 아니었다. BFS를 잘 이해해서 조금 응용할 수 있으면 무난하게 풀 수 있을 정도의 난이도라고 생각됨
• SWEA 모의 A형 문제는 BFS, DFS를 응용하는 문제가 많이 나오는데 이 문제를 풀어보면 많은 도움이 될 것 같다.