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

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE

문제

교도소로 이송 중이던 흉악범이 탈출하는 사건이 발생하여 수색에 나섰다.

탈주범은 탈출한 지 한 시간 뒤, 맨홀 뚜껑을 통해 지하터널의 어느 한 지점으로 들어갔으며,

지하 터널 어딘가에서 은신 중인 것으로 추정된다.

터널끼리 연결이 되어 있는 경우 이동이 가능하므로 탈주범이 있을 수 있는 위치의 개수를 계산하여야 한다.

탈주범은 시간당 1의 거리를 움직일 수 있다.

지하 터널은 총 7 종류의 터널 구조물로 구성되어 있으며 각 구조물 별 설명은 [표 1]과 같다.

 

[그림 1-1] 은 지하 터널 지도의 한 예를 나타낸다.

이 경우 지도의 세로 크기는 5, 가로 크기는 6 이다.

맨홀 뚜껑의 위치가 ( 2, 1 ) 으로 주어질 경우, 이는 세로 위치 2, 가로 위치 1을 의미하며 [그림 1-2] 에서 붉은 색으로 표기된 구역이다.

탈주범이 탈출 한 시간 뒤 도달할 수 있는 지점은 한 곳이다.

탈주범이 2시간 후 도달할 수 있는 지점은, [그림 1-3] 과 같이 맨홀 뚜껑이 위치한 붉은 색으로 표시된 지하도 와 파란색으로 표기된 지하도까지 총 3개의 장소에 있을 수 있다.

3시간 후에는 [그림 1-4] 과 같이 총 5개의 지점에 있을 수 있다.

 

[그림 2-1] 에서 맨홀뚜껑이 위치한 지점이 ( 2, 2 ) 이고 경과한 시간이 6 으로 주어질 경우,

[그림 2-2] 에서 맨홀뚜껑이 위치한 지점은 붉은 색, 탈주범이 있을 수 있는 장소가 푸른색으로 표기되어 있다.

탈주범이 있을 수 있는 장소는, 맨홀뚜껑이 위치한 지점을 포함하여 총 15 개 이다.

 

지하 터널 지도와 맨홀 뚜껑의 위치, 경과된 시간이 주어질 때 탈주범이 위치할 수 있는 장소의 개수를 계산하는 프로그램을 작성하라.


[제약 사항]

1. 시간 제한 : 최대 50개 테이트 케이스를 모두 통과하는데, C/C++/Java 모두 1초

2. 지하 터널 지도의 세로 크기 N, 가로 크기 M은 각각 5 이상 50 이하이다. (5 ≤ N, M ≤ 50)

3. 맨홀 뚜껑의 세로 위치 R 은 0 이상 N-1이하이고 가로 위치 C 는 0 이상 M-1이하이다. (0 ≤ R ≤ N-1, 0 ≤ C ≤ M-1)

4. 탈출 후 소요된 시간 L은 1 이상 20 이하이다. (1 ≤ L ≤ 20)

5. 지하 터널 지도에는 반드시 1개 이상의 터널이 있음이 보장된다.

6. 맨홀 뚜껑은 항상 터널이 있는 위치에 존재한다.

[입력]

첫 줄에 총 테스트 케이스의 개수 T가 주어진다.

두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다.

각 테스트 케이스의 첫 줄에는 지하 터널 지도의 세로 크기 N, 가로 크기 M, 맨홀 뚜껑이 위치한장소의 세로 위치 R, 가로 위치 C, 그리고 탈출 후 소요된 시간 L 이 주어진다.

그 다음 N 줄에는 지하 터널 지도 정보가 주어지는데, 각 줄마다 M 개의 숫자가 주어진다.

숫자 1 ~ 7은 해당 위치의 터널 구조물 타입을 의미하며 숫자 0 은 터널이 없는 장소를 의미한다.

[출력]

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 기록한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 탈주범이 위치할 수 있는 장소의 개수이다.

 

5              // 총 테스트 케이스 개수 T = 5 5 6 2 1 3      // [그림1-1]과 동일 0 0 5 3 6 0 0 0 2 0 2 0 3 3 1 3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 5 6 2 2 6      // [그림2-1]과 동일 3 0 0 0 0 3 2 0 0 0 0 6 1 3 1 1 3 1 2 0 2 0 0 2 0 0 4 3 1 1 ...            //나머지는 sample_input.txt 참조

#1 5 #2 15 #3 29 #4 67 #5 71

풀이

단계별로 한 칸씩 갈 수 있는 영역을 넓혀가는 문제형식이라고 판단하였고 BFS로 풀면 되겠다는 생각을 제일 처음 가지고 문제를 접근하였다. 

터널 배치 구현의 경우에는 딕셔너리 형태로 만들었으며 왼/오/상/하 순으로 영역을 나누고 각 방향일 때 터널끼리 붙을 수 있는 경우를 다 적어주었다. 이 부분 구현하는 게 가장 어려웠다.

대략적인 알고리즘으로는 첫번째 테스트 케이스를 보자. BFS 탐색을 통해 queue에 들어가고 탐색 되는 순서는 아래와 같으며 시간 3초가 흘렀을 때 탈주범이 위치할 수 있는 영역은 queue에 들어갔던 영역의 숫자인 5개가 된다.

유의할점은 아래와 같은 경우가 발생하는 경우다 빨간 테두리 부분의 위치가 중복으로 queue에 잡히게 되는 것인데 이를 해결하기 위해 코드에 중복요소를 방지하는 조건문을 추가로 적게 되었다. 코드 부분의 주석(queue에 중복요소 들어옴 방지)을 참조바람.

코드

T = int(input())
for t in range(T):
 
    tunnel = { # 왼 오 상 하 순으로 나열 / 각각 붙을 수 있는 터널의 번호를 딕셔너리의 요소로서 받음
        1:[[1,3,4,5],[1,3,6,7],[1,2,5,6],[1,2,4,7]],
        2:[[],[],[1,2,5,6],[1,2,4,7]],
        3:[[1,3,4,5],[1,3,6,7],[],[]],
        4:[[],[1,3,6,7],[1,2,5,6],[]],
        5:[[],[1,3,6,7],[],[1,2,4,7]],
        6:[[1,3,4,5],[],[],[1,2,4,7]],
        7:[[1,3,4,5],[],[1,2,5,6],[]]
        }    
    
    N, M, R, C, L = map(int,input().split()) # N:세로길이 M:가로길이 R: 맨홀위치 행 C: 맨홀위치 열 L: 소요시간
    mapp = []
    for _ in range(N):
        mapp.append(list(map(int,input().split())))
 
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    time = 1
    cnt = 1
 
    qq = [(R,C)]
    while 1:
        if time == L: #소요시간이 되었다면 break
            break
        for _ in range(len(qq)): # queue에 존재하는 요소를 모두 탐색해야 한 타임이 끝남!
            q = qq.pop(0)
            for i in range(4):
                if tunnel[mapp[q[0]][q[1]]][i]: # (상 하 좌 우) 중 갈 수 있는 곳이 있다면
                    if 0 <= q[0]+dx[i] < N and 0 <= q[1]+dy[i] < M and mapp[q[0]+dx[i]][q[1]+dy[i]] != 0: # 벽이 아니고 터널이 존재한다면
                        if mapp[q[0]+dx[i]][q[1]+dy[i]] in tunnel[mapp[q[0]][q[1]]][i]: # 그 터널이 갈 수 있는 터널이라면
                            if (q[0]+dx[i],q[1]+dy[i]) not in qq: # queue에 중복요소 들어옴 방지
                                qq.append((q[0]+dx[i],q[1]+dy[i]))
                                cnt += 1
            mapp[q[0]][q[1]] = 0 # 상하좌우 체크가 끝나면 0으로 방문 처리함으로써 벽으로 만들어줌
                        
        time += 1
 
    print('#{} {}'.format(t+1,cnt))

 

아쉬운점

일단 상당히 마음에 들지 않는다. if를 통해 계속 조건확인을 해야한다는 점에서 마음에 들지 않는다. 분명히 조건을 줄일 수 있을텐데 1시간가량 생각해도 어떻게 손을 대서 개선할지 감이 안온다.  좀더 실력이 쌓여서 이렇게 조건 줄줄 안달아도 풀 수 있어지길...