‘나 잡아 봐라’ 게임 (LINE 인턴 채용 코딩테스트 문제)

해당 문제는 LINE Engineering에 게재되어 있는 문제입니다.

[문제 설명 및 파악]

문제

연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오.

조건

1. 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.
2. 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다.
3. 코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다.
4. 브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다.

입력 형식

표준 입력의 첫 줄에 코니의 위치 C와 브라운의 위치 B를 공백으로 구분하여 순서대로 읽는다.

출력 형식

브라운이 코니를 잡을 수 있는 최소 시간 N초를 표준 출력한다. 단 브라운이 코니를 잡지 못한 경우에는 -1을 출력한다.

예제 

입력: 11 2

출력: 5

코니의 위치: 11 → 12 → 14 → 17 → 21 → 26

브라운의 위치: 2 → 3 → 6 → 12 → 13 → 26

브라운은 코니를 5초 만에 잡을 수 있다.

가장 먼저 이 문제가 요구하는 것이 무엇인지, 그 요구 조건을 충족시키기 위해선 어떤 방식으로 접근해야 되는지 확인해보자. 일단 문제에서는 코니가 범위를 벗어나거나 브라운이 코니를 잡아서 게임이 끝나기까지의 최소 시간을 요구하고 있다. 그렇다면 이러한 문제는 어떻게 접근해야 될까? 최적의 방안과 수식을 찾아서 최소 시간을 구할까? 아니면 모든 경우의 수를 일일이 고려하며 최종적으로 최소 시간을 구할까? 그에 답은 코니와 브라운의 시간마다의 위치 변화량에서 얻을 수 있다. 코니는 규칙적으로 변화량을 늘려가므로, 코니의 N초 후의 위치는 우리가 예측할 수 있다. 하지만, 브라운은 코니를 따라 잡기 위한 최적의 선택을 매초마다 결정해야 한다. 즉, 브라운의 위치는 예측할 수 없다. 그러므로 우리는 최적의 경우를 따라 최소시간을 구할 수 없고 브라운이 위치할 수 있는 모든 위치의 경우의 수를 따지고 최소 시간을 선택하는 방향으로 이 문제를 접근해야한다. 그럼 이제 코드를 확인하자.

---

[풀이]

from collections import deque

c, b = map(int, input().split())  # cony(이하 c)와 brown(이하 b)의 현재 위치
t = 0
queue = deque()  # 큐를 더 효율적으로 사용하기 위해 deque() 모듈사용
queue.append(b)  # 먼저 처음시작의 위치로 시작하기 위해 b의 현재 위치를 추가
visited = [{} for _ in range(200001)]  # 방문한 위치를 방문했던 시간과 함께 저장하기 위한 List(dict)
visited[b][t] = True  # 처음 시작의 위치를 시간과 함께 저장

while 0 <= c <= 200000:  # 해당 범위를 벗어날 경우 게임 종료
    if t in visited[c]:  # 만약 해당 시간에 c와b의 위치가 동일하다면 게임 종료
        break
    t += 1  # 초(1초에 한번의 이동)
    c += t  # 코니의 위치
    len_of_temp = len(queue)  # 해당 시간대에 갈 수 있는 위치들에 대해서만 고려하기 위해서 길이로 한계 설정
    for i in range(len_of_temp):  # 해당 시간대에 갈 수 있는 위치들에 대해서만 탐색
        loc = queue.popleft()  # b의 현재 위치
        # b가 갈 수 있는 3가지의 모든 위치에 대하여 탐색
        if loc - 1 >= 0 and t not in visited[loc - 1]:  # 현재 시간에 해당 위치를 들르지 않았다면
            visited[loc - 1][t] = True  # 해당 위치에 시간과 함께 방문 여부를 저장
            queue.append(loc - 1)  # 해당 위치를 queue에 쌓아줌
        if loc + 1 <= 200000 and t not in visited[loc + 1]:  # 현재 시간에 해당 위치를 들르지 않았다면 
            visited[loc + 1][t] = True  # 해당 위치에 시간과 함께 방문 여부를 저장
            queue.append(loc + 1)  # 해당 위치를 queue에 쌓아줌
        if loc * 2 <= 200000 and t not in visited[loc * 2]:  # 현재 시간에 해당 위치를 들르지 않았다면
            visited[loc * 2][t] = True
            queue.append(loc * 2)  # 해당 위치를 queue에 쌓아줌
else:  # c가 범위를 벗어난 경우 (즉, b가 c를 잡지 못한 상황)
    print(-1)

print(t)

이 문제에서의 핵심은 visited를 통해 이미 왔던 위치라면 배제해주는 부분이다. 시간복잡도를 고려한다면 이 방법은 필수이다. 사실 이 부분까지는 쉽게 생각해낼 수도 있다. 하지만 여기서 더 중요한 점은 그저 해당 위치를 들렀다고 배제하는 것이 아닌, 그 위치를 들른 '시간'까지 고려(저장)해야한다는 것이다. 코니의 위치가 고정되어 있지 않기 때문에 시간이 지남에 따라 들렀던 위치라도 그 또한 코니를 잡기 위한 경로가 될 수 있다는 것이다. 

---

[잘못된 풀이]

나는 처음 이 문제를 모든 경우의 수를 고려하는 것이 아닌, 최적의 경우의 수를 매 순간마다 선택하여 구현하려고 생각했었다. 코니의 위치와 브라운의 위치를 수식적으로 고려해서 이진 탐색처럼 코니를 잡으려고 했었다. 그 후 결국은 모든 경우의 수를 고려해야겠다 라는 것을 깨닫고 BFS로 문제를 풀다가 visited에 시간을 추가하지 않고 위치만을 기록하는 방안을 선택했었다. 그 후 어떤 것이 잘못된 것인지 찾지 못하고 끝내버렸다. 결론적으로 문제의 접근 방식부터 잘못됐었고 깊게 생각하지 않아서 이러한 결과가 생긴 것 같다.

---

[마무리]

이 문제는 말그대로 기출이다. 사람을 뽑기 위한 일련의 평가 지표이므로 당연히 마냥 쉽지는 않았다. 또한, 이 문제를 푸냐 못 푸냐의 핵심 포인트는 위치만을 저장하는 것이 아닌 시간까지 저장하며 고려해야하는 부분인 것 같다. 앞으로 간간히 기출을 풀며 현재 나의 수준이 어느 정도인지 파악하는 것도 중요한 것 같다.

 

<문제 출처: https://engineering.linecorp.com/ko/blog/2019-firsthalf-line-internship-recruit-coding-test/>