[SWEA] [모의 SW 역량테스트] 1953 탈주범 검거 (python)

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE&problemTitle=%ED%83%88%EC%A3%BC%EB%B2%94&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

🔥 작성코드

# bfs
def sol(R, C):
    global result

    q = [[R, C]]
    while q:
        # d에 현재 위치의 모양 저장
        si, sj = q.pop(0)
        d = arr[si][sj]
        n = vst[si][sj]
        if n >= L:
            return

        # 현재 모양에서 갈 수 있는 지점 ni, nj
        # ni, nj의 모양이 현재 모양과 연결되어 있어야 이동 가능, 가능한 다음 모양의 모음 f
        di, dj, f = direction.get(str(d))
        for c in range(len(di)):
            ni = si + di[c]
            nj = sj + dj[c]
            if 0 <= ni < N and 0 <= nj < M and (arr[ni][nj] != 0 and arr[ni][nj] in f[c]) and vst[ni][nj] == 0:
                vst[ni][nj] = n+1
                result += 1
                q.append([ni, nj])
    return


T = int(input())

# 현재 위치의 모양과 이동 가능한 다음 위치의 모양 저장
direction = {
    '1': ([-1, 1, 0, 0], [0, 0, -1, 1], [[1, 2, 5, 6], [1, 2, 4, 7], [1, 3, 4, 5], [1, 3, 6, 7]]),
    '2': ([-1, 1], [0, 0], [[1, 2, 5, 6], [1, 2, 4, 7]]),
    '3': ([0, 0], [-1, 1], [[1, 3, 4, 5], [1, 3, 6, 7]]),
    '4': ([-1, 0], [0, 1], [[1, 2, 5, 6], [1, 3, 6, 7]]),
    '5': ([1, 0], [0, 1], [[1, 2, 4, 7], [1, 3, 6, 7]]),
    '6': ([1, 0], [0, -1], [[1, 2, 4, 7], [1, 3, 4, 5]]),
    '7': ([-1, 0], [0, -1], [[1, 2, 5, 6], [1, 3, 4, 5]])
}

for test_case in range(1, T+1):
    N, M, R, C, L = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    vst = [[0 for _ in range(M)] for _ in range(N)]
    vst[R][C] = 1

    result = 1
    sol(R, C)

    print(f'#{test_case} {result}')

 

⭕ 해설

1.  기본적인 bfs문제와 같은 방식으로 풀었습니다.
2.  bfs의 경로를 저장하여 재방문을 막기 위해 vst 배열을 만들었습니다.
   • arr에 직접 값을 저장하게 되면 다음 단계에서 현재 위치의 모양을 알 수 없어 vst를 이용
3.  현재 모양에서 갈 수 있는 곳을 정하고, 다음 위치의 모양이 이어진다면 진행하도록 했습니다.
   • 만약 1번 모양으로 상, 하, 좌, 우를 탐색
   • 상으로 갈 수 있는 길이 있지만 해당 위치가 3번 모양이라면 이어지지 않으므로 이동 불가
     • ex) 해당 코드에서는 c가 0 일 때 di[c] = -1, dj[c] = 0, f[c] =[1, 2, 5, 6]
     • 따라서 다음 위치의 모양이 1 2 5 6 중 하나라면 연결된 것 (arr[ni][nj] in f[c] 로 확인)
4.  vst에 이전 값보다 1씩 증가시키며 값을 저장하고 결과값을 1씩 증가시켜주었습니다.
5.  q에서 뽑아 온 vst의 값이 L이라면 L만큼 시간이 흐른 뒤 갈 수 있는 위치는 모두 vst에 저장된 경우입니다.
6.  따라서 함수를 종료해주고 결과를 출력합니다.