나 잡아 봐라 [2019 LINE 인턴채용]

델리만쥬 디퓨저·2025년 2월 15일

알고리즘

목록 보기

16/17

잡히면 죽는다💙🚓

문제

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

조건은 다음과 같다.

코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다.

즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.

브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다.

코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다.

브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다

c = 11 # 코니의 처음 위치
b = 2 # 브라운의 처음 위치

문제 분석

코니의 이동 경로

1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매초마다 이동 거리 +1만큼 움직인다.
그렇다면 1, 1+2=3, 1+2+3=6, 1+2+3+4=10, 1+2+3+4+5=15과 같이 현재 코니의 위치를 예측할 수 있다.
코니의 현재 위치를 계산하는 코드를 한번 간단하게 작성해 보자.

c = 11	// 코니의 초기 위치
c_v = 0	// 코니의 가속도

c_v = c_v + 1	// 가속도에 1을 더한다
c = c + c_v	// 현재 코니의 거리에 가속도를 더한 값을 더한다

이렇게 코니의 이동 거리는 다음과 같이 계산할 수 있을 것이다.

브라운의 이동 경로

브라운은 3가지 이동 경로를 고려해야 한다.
2*B, B+2, B-1 중 택1이 가능하다.
아직은 아이디어가 잘 떠오르지 않으므로, 우선은 임의로 그리디 알고리즘을 작성하고 효율성을 분석해서 더 나은 방법을 떠올리기로 하겠다.

    if b < c:
        if abs(2 * b - c) < abs(b + 2 - c):
            b = b * 2
        else:
            b = b + 2
    elif b > c:
        b = b - 1

브라운이 코니보다 뒤에 있을 경우, 2*B와 B+2와 C의 거리에 대한 절대값을 비교해 브라운의 위치를 변경한다.
브라운이 코니보다 앞에 있을 경우 B-1를 선택한다.

구현 코드

def catch_me(c, b):
    ans = 0
    c_v = 0

    while True:
        if b == c or not 0 <= b <= 200000 or not 0 <= c <= 200000:
            return ans

        ans = ans + 1

        c_v = c_v + 1
        c = c + c_v

        if b < c:
            if abs(2 * b - c) < abs(b + 2 - c):
                b = b * 2
            else:
                b = b + 1
        elif b > c:
            b = b - 1

        # print("b, c, c_v, c_tot:", b, c, c_v, c_tot)


print("정답 = 3 / 현재 풀이 값 = ", catch_me(10, 3))
print("정답 = 8 / 현재 풀이 값 = ", catch_me(51, 50))
print("정답 = 28 / 현재 풀이 값 = ", catch_me(550, 500))

브라운과 코니가 만나는 경우와 범위를 벗어나는 경우를 탈출 조건으로 지정해 코드를 작성하였다.

결과 확인

아

문제 분석

코니의 위치는 계속해서 변화한다.
따라서 매 순간 단순히 코니와의 거리를 좁히기 위해 그리디로 접근하면, 이후의 상황 변화를 고려하지 못해 최적해를 계산해낼 수 없다.
브라운이 이동할 수 있는 모든 경로를 파악해 코니와 함께 이동하면서 최적해를 계산해야 한다.

그렇다면...?

BFS로 접근

브라운의 이동 경로를 계산하는 알고리즘 설계

초 단위로 반복문을 돌린다.
코니가 다음 방문한 곳의 시간이 브라운이 방문한 시간과 같으면 시간을 리턴하고 종료한다.
브라운은 다음 초의 모든 경우의 수를 계산해서 방문 테이블에 저장한다.
반복

여기에서 중요한 포인트는 다음과 같다.

코니는 0초부터 시작해 방문 테이블을 검사한다.
브라운은 코니보다 1초 후의 위치의 모든 경우의 수를 검사해 방문 테이블에 추가한다.
이 때, 브라운이 동일 노드에 중복 도착하는 경우가 발생하므로, 리스트에 딕셔너리를 추가해 각각의 시간을 저장할 수 있도록 한다.
또한 1초 후의 위치만 검사할 수 있도록 반복문 범위를 queue의 길이로 제한한다.

정답 코드

from collections import deque


def catch_me(c, b):
    time = 0
    queue = deque()
    queue.append((b, 0))
    visited = [{} for _ in range(200001)]

    while c < 200000:
        c += time
        if time in visited[c]:
            return time

        for i in range(0, len(queue)):
            cur_pos, cur_time = queue.popleft()

            new_time = cur_time + 1

            new_pos = cur_pos * 2
            if new_pos < 200001 and new_time not in visited[new_pos]:
                visited[new_pos][new_time] = True
                queue.append((new_pos, new_time))

            new_pos = cur_pos + 1
            if new_pos < 200001 and new_time not in visited[new_pos]:
                visited[new_pos][new_time] = True
                queue.append((new_pos, new_time))

            new_pos = cur_pos - 1
            if new_pos >= 0 and new_time not in visited[new_pos]:
                visited[new_pos][new_time] = True
                queue.append((new_pos, new_time))

        time += 1


print("정답 = 3 / 현재 풀이 값 = ", catch_me(10, 3))
print("정답 = 8 / 현재 풀이 값 = ", catch_me(51, 50))
print("정답 = 28 / 현재 풀이 값 = ", catch_me(550, 500))

결론

처음에는 그리디 방식으로 매 순간 코니의 위치를 따라가려 했으나, 이는 이후의 변화를 계산하지 못해 최적해를 보장하지 않으므로 실패하였다.
두 번째는 BFS를 사용하여 브라운이 방문하는 모든 경우의 수를 계산한 뒤, 코니의 경로를 따라가면서 검사하는 방식을 시도했다.
그러나 동일 위치의 중복 시간 부분에서 딕셔너리를 떠올리지 못 했으며, 중복 시간을 표현하기 위한 구현을 하다보니 BFS가 아니라 브루트 포스가 되어버려서 수행 시간이 기하급수적으로 증가하여 실패하였다.
이는 매 초마다 필요한 부분만 계산하는 것이 아니라, 브라운의 모든 경로를 미리 계산하고 나중에 코니의 경로를 따라가며 검증하려 했기 때문이다.
어떤 알고리즘을 사용할 지 알더라도, 무작정 적용하기보다는 해당 문제에 어떻게 적용해야 최적의 해를 보장할지에 대한 충분한 고민이 필요하다는 것을 알게 되었다.