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

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

• 조건
  • 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.
  • 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다.
  • 코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다.
  • 브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다.
• 출력 형식
  • 브라운이 코니를 잡을 수 있는 최소시간 N초를 표준 출력한다. 단 브라운이 코니를 잡지 못한 경우에는 -1을 출력한다.
• 예제 입력
  C = 11, B = 2, Result = 5

• 예제 설명
  • 코니의 위치: 11 → 12 → 14 → 17 → 21 → 26
  • 브라운의 위치: 2 → 3 → 6 → 12 → 13 → 26
  • 브라운은 코니를 5초 만에 잡을 수 있다

 

처음 접근을 재귀 문제로 접근했었다. 

def calc(a, b) :
	pass
    
calc(a, b-1)
calc(a, b+1)
calc(a, b*2)

이런 식으로 접근했었는데 도저히 계산이 끝날 기미가 보이지 않았다.

이때 재귀를 빼고 메모이제이션을 사용해야 겠다는 생각이 들었다.

블로그를  찾아보다 알게된 중요한 내용을 첨부하겠다.

 

너무 경우의 수가 많고 쉽게 일반화 할 수 없다고 판단된다면 '모든 경우의 수'를 다 나열해야함 -> 이때 bfs, dfs 사용해야함

bfs를 사용할때 규칙적으로 변화하는 값은 배열!!, 불규칙적으로 변화하는 값은 딕셔너리!!!!

 

딕셔너리는 항상 선택에서 배제했었던것 같다. 좀 더 친해져야 겠다.

이제까지 명확한 규칙 없이 감으로 bfs, dfs 때려 맞췄던게 반성된다.

bfs: 모든 경우를 살펴봐야 할 경우, dfs에 비해 접근해야하는 경우의 수가 훨씬 많아 dfs를 선호했었다. 큐를 이용한다

dfs: 하나씩 잡고 끝까지 들어간다, 스택을 이용한다.

 

이제 재귀는 빼고 bfs와 dict를 이용해서 접근해보자

 

코드를 살펴보자

 

from collections import deque


def solution(C, B):
  time = 0
  queue = deque()
  queue.append((B, time))
  visited = [{} for _ in range(200001)]

  while C <= 200000:
    C += time
    # 방문할 곳의 같은 시간대에 브라운이 방문했었던 적이 있으면 둘은 만난것이다
    if time in visited[C]:
      return time

    for _ in range(0, len(queue)):
      current_position, current_time = queue.popleft()
      next_time = current_time + 1

      next_position = current_position + 1
      if 0 <= next_position <= 200000:
        visited[next_position][next_time] = True
        queue.append((next_position, next_time))

      next_position = current_position - 1
      if 0 <= next_position <= 200000:
        visited[next_position][next_time] = True
        queue.append((next_position, next_time))

      next_position = current_position * 2
      if 0 <= next_position <= 200000:
        visited[next_position][next_time] = True
        queue.append((next_position, next_time))

    time += 1

  return -1


print(solution(11, 2))  # 5

 

이제 핵심을 파헤칠 차례이다.

 

접근방법 :

* 코니는 코니대로 놀게 내비둔다(코니는 아직 어리다)

* 브라운이 매 초마다 방문하는 지점을 시간 정보와 함께 담아놓자

* 코니가 방문하는 곳에 이미 브라운이 같은 시간대에 방문한 흔적이 있다면 코니와 브라운은 만나게 된것이다.

 

 

 

 

 

출처: https://wooogy-egg.tistory.com/33