[딩코딩코 2025 코딩테스트 필수 알고리즘] - 20. LINE 인턴 채용 코딩테스트 - 나 잡아 봐라

문제

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  # 브라운의 처음 위치

코드 스니펫

from collections import deque

c = 11
b = 2

def catch_me(cony_loc, brown_loc):
    # 구현해보세요!
    return

print(catch_me(c, b))  # 5가 나와야 합니다!

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

풀이 과정

조건 살펴보기

1. 코니의 위치
   • 처음 위치에서 1초 후 1만큼, 매 초마다 이전 이동 거리 +1 만큼 움직인다.
   • 즉, 증가하는 속도가 1초마다 1씩 늘어난다.
   • 예시
     • 증가 : 1 2 3 4
     • 위치 : 1 → 2→ 4→ 7→ 11 …
2. 브라운의 위치
   • B-1, B+1, 2*B 중 하나
   • 예시 : 기존 위치 = 2
     1. 2-1 =1
        1. 1-1=0
        2. 1-1=2
        3. 1*2=2
     2. 2+1=3
        1. 3-1=2
        2. 3+1=4
        3. 3*2=6
     3. 2*2=4
   • 위 내용을 보는 순간 모든 경우의 수를 다 나열해야겠구나 생각해야 한다.
   • BFS 를 사용해야 한다.
3. 잡았다는 의미는 똑같은 시간에 똑같은 위치에 있어야만 한다.
   • 시간과 위치를 저장해놓는 자료구조가 필요하다.
   • 시간은 규칙적으로 증가하지만 위치는 자유자재로 변화한다.
   • 배열안에 딕셔너리 : 각 시간마다 위치를 저장하기 위한 저장 공간

구현

코니의 위치

from collections import deque

c = 11
b = 2

def catch_me(cony_loc, brown_loc):
    time = 0

    while 1:
        cony_loc += time

        time += 1

print(catch_me(c, b))

브라운의 위치

1. 모든 경우의 수를 구하기 위해 BFS 사용
2. 경우의 수를 쌓아 놓기 위해 queue 사용
   • 위치와 시간을 담아둬야 함

from collections import deque

c = 11
b = 2

def catch_me(cony_loc, brown_loc):
    time = 0
    queue = deque()
    queue.append((brown_loc, 0))  

    while 1:
        cony_loc += time

        for i in range(0, len(queue)):  
            current_position, current_time = queue.popleft()

            new_time = current_time + 1
            new_position = current_position - 1
            queue.append((new_position, new_time))

            new_position = current_position + 1
            queue.append((new_position, new_time))

            new_position = current_position * 2
            queue.append((new_position, new_time))

        time += 1

print(catch_me(c, b))

1. 탈출 조건(실패 조건)
   1. 코니와 브라운의 위치 p는 조건 0≤ x ≤ 200,000 을 만족한다
      • while 문에 cony_loc 의 조건을 추가해준다.
   2. 브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다.
      • 브라운의 new_position 에 조건을 추가한다.
2. 성공 조건
   1. 코니와 브라운의 위치와 시간이 동일해야 한다.
   2. 방문한 시간과 위치를 저장하기 위해 visited 배열을 만든다.
   3. 위치마다 브라운이 방문한 시간을 적기 위해 배열 안에 딕셔너리를 넣는다.
      • 5 in visited[3] : 5초에 위치3을 방문했는지 여부 저장
   4. visited[cony 위치] 에 현재 시간이 있다.
      • 즉, 브라운이 현재 코니가 방문한 위치에 현재 시간에 들를 수 있다.
      • 그러면 True 반환

from collections import deque

c = 11
b = 2

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

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

        for i in range(0, len(queue)):  
            current_position, current_time = queue.popleft()

            new_position = current_position - 1
            new_time = current_time + 1
            if new_position >= 0 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

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

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

        time += 1

print(catch_me(c, b))

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