[SWEA 코딩] [SW 모의역량 테스트] 탈주범 검거 - PYTHON #1953

소스 코드

def bfs():
    global cnt
    # 멘홀 위치, 현재까지 걸린 시간
    temp = [[r,c,1,board[r][c]]]

    # 주어진 시간 전에 모든 위치 방문 가능하기 때문에 조건을 len(temp)로 줌
    while len(temp):

        # 위치(i,j), 현재까지 시간, 현재위치의 터널 번호
        i,j,time,num = temp.pop(0)

        # 탈출조건
        # 시간 됐으면 탈출
        if time == l:
            break

        for q in range(4):
            ii = i+tunnel[2*num][q]
            jj = j+tunnel[2*num+1][q]

            # 0,0을 더해서 현재 위치에서 이동하지 않는 경우 배제
            if ii == i and jj == j:
                continue

            # 범위 조건
            if 0 <= ii < n and 0 <= jj < m:

                # 방문할 위치의 값이 0이 아니고
                # 방문한 적 없으면
                if board[ii][jj] != 0 and check[ii][jj] == 0:
                    temp_num = board[ii][jj]

                    # 이동할 곳의 터널이 현재의 터널과 연결 가능한지 확인
                    if tunnel[2*temp_num][(q+2)%4] != 0 or tunnel[2*temp_num+1][(q+2)%4] != 0:
                        temp.append([ii,jj,time+1,temp_num])
                        check[ii][jj] = 1
                        cnt += 1

    return

T = int(input())

# 터널 정보
# 상 좌 하 우
tunnel = [
    [0],[0],
    [-1,0,1,0],[0,-1,0,1],
    [-1,0,1,0],[0,0,0,0],
    [0,0,0,0],[0,-1,0,1],
    [-1,0,0,0],[0,0,0,1],
    [0,0,1,0],[0,0,0,1],
    [0,0,1,0],[0,-1,0,0],
    [-1,0,0,0],[0,-1,0,0]
]

for tc in range(1,1+T):

    # 세로 n 가로 m 맨홀 위치 r,c 시간 l
    n,m,r,c,l = map(int,input().split())

    # 지도
    board = [list(map(int,input().split())) for _ in range(n)]

    # 방문 확인
    check = [[0 for _ in range(m)] for t in range(n)]

    # 맨홀은 무조건 방문
    check[r][c] = 1

    # 맨홀 1
    cnt = 1

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

 

---

해결 방법

1. 내가 생각한 이 문제의 핵심은 첫째, '탈주범은 시간당 1의 거리를 움직일 수 있다.' 이 조건

1) 움직일 수 있다 != 반드시 움직인다

2) 방문한 곳들을 체크해서 다시 돌아가지 않아야 한다

 

2. 둘째, 터널 간의 관계를 정의해야 한다

ex) 2번 터널 위에 3번 터널이 있으면 위에 터널이 있음에도 이동 불가능하다

1) 내가 이동하려는 방향의 터널이 내가 이동하려는 방향의 반대 방향으로 이동할 수 있어야 한다

2) 이를 해결하기 위해 터널 정보를 '상 좌 하 우'로 순서로 만들고, (q+2)%4를 통해 해당 값을 확인

 

3. 이 외에는 일반적인 bfs를 돌리면 됨

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.