[SWEA] D4 : 자기방으로 돌아가기(4408) Python

 이 문제는 수업과정에서 한번 풀어봤던 문제였지만, 그 이후로 그래프나 완전 탐색 문제 위주로 풀다가 오랜만에 마주하니 어떻게 풀어야 할지 감이 잡히지 않았다.

 

 문제는 음주가무를 즐기다가 조교들의 눈을 피해 일사천리로 자신의 방으로 돌아가야하는 고등학생들의 자기 방으로 돌아가는 최단 시간을 구하는 문제이다.(경로가 겹치는 경우 한 명씩 지나갈 수 있으므로 한 단위 시간이 증가한다)

 

 문제만 읽었을 때는 막막했지만, 교수님께서 알려주신 필살기인 손으로 문제 상황을 적으면서 생각을 해보았다. 이 문제는 친절하게 그림으로도 설명을 해주었기 때문에 쉽게 이해할 수 있었다.

 

 

 손코딩을 하면서 내가 생각해낸 해법은 통로를 하나의 배열로 생각하여 그 통로를 지나는 경우 방문 체크를 하는 것이다.

즉, 위 그림에서 1번 방에서 4번 방으로 간다면 통로의 0번, 1번 위치를 지나기 때문에 통로에 0번과 1번에 방문 체크를 한다. 3번에서 6번으로 가는 경우에도 통로의 1번과 2번에 방문체크를 한다.

 가장 많이 겹친 횟수가 최단 필요 시간이기 때문에 통로 1번 위치의 겹친 횟수 2가 정답이 된다.

 

이를 코드로 한다면,

T = int(input()) + 1

for tc in range(1,T):
    N = int(input())
    # 통로에 겹치는 횟수가 필요 시간이므로 통로의 방문횟수를 기록
    ans_lst = [0] * 200

    for _ in range(N):
        sr, er = map(int,input().split())
        # 방번호가 1~2 번방인경우 ans_list[0] 에 방문 체크가 되도록 조정
        sr = (sr-1) // 2
        er = (er-1) // 2

        # 시작방에서 목표방으로 가는 통로에 방문체크
        for i in range(min(sr,er),max(sr,er)+1):
            ans_lst[i] += 1
    # 방문이 가장 많이 겹친 횟수가 최소 시간이 된다
    print(f'#{tc} {max(ans_lst)}')

이렇게 된다.

 

방 번호와 통로 번호 인덱스를 맞추는 것 그리고 시작 방 번호가 도착 방 번호보다 클 수도 있다는 함정 요소가 있지만, 푸는 아이디어만 생각해 낸다면, D4 문제 치고는 할 만했던 것 같다.

 

ps. 문제 풀 때는 꼭 손 코딩으로 문제 검증을 해보자!