문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.
매웠다ㅜㅜ..
🤔 생각
-
한마디로 특정한 정점을 찾는게 아니라, 움직이는걸 추격한다는 소리.
-
이러면 방문한 노드는 다시 방문하지 않는다는 룰이 무너진다.
-
방문처리를 안 하면 그래프의 가지가 많아지긴 하겠지만.. 동일 레벨 노드만 다시 안 담도록 구분해주면 답은 나오겠다. 그런데...
-
멋진 시간 제한을 가진 문제다.
-
불길하지만 일단 당장 떠오르는건 위 아이디어 뿐이었다. 생각한대로 한번 짜보자...
📌 1차 풀이
import sys
input = sys.stdin.readline
def main():
def bfs(n,k):
q = [n]
cache = [-1]*500001
cache[n] = 0
level = 0
while q:
tmp = []
for x in q:
if x == k: return level
for i in (x-1, x+1, x*2):
if 0 <= i <= 500000 and cache[i] != level:
cache[x] = level
tmp.append(i)
q = tmp
level += 1
k += level
return -1
n,k = map(int, input().split())
print(bfs(n,k))
if __name__ == "__main__":
sys.exit(main())사실 시간 초과 날거 알고 있었다. ㅎㅎ
시간 제한이 타이트한걸 보면 돌파구가 있다는 뜻이고, 뭔가 발상의 전환이 필요한데... 잘 떠오르지 않아 검색해서 조금 힌트를 얻었다.
내 머리만으로 풀어야 시원한데 그러지 못해서 아쉽다. 😢
재방문이 가능하고, x+1와 x-1 노드 방문을 반복하는 그래프라면
같은 노드가 레벨마다 일정한 패턴으로 재방문 된다. +1과 -1을 더하면 0이니 당연하다!
손으로 큐를 그려보면, 홀수 번째 레벨에서 큐잉된 노드들은 그 다다음 레벨에서도 또 큐잉된다. (레벨 3에 있는 노드들은 5에서도 큐잉된다.)
짝수도 마찬가지다!
그렇다면, 굳이 모든 노드를 큐에 넣지 않아도 레벨의 홀짝 여부만 안다면, 어떤 노드들이 재방문할지 이미 알 수 있다.
그리고 앞서 방문된 노드들은 이미 탐색이 되고 있다. 또 큐잉하지 않아도 경우의 수가 생략될 염려는 없다.
이걸 필터링하지 않는다면 중복 순회를 한없이 하게 된다..
그렇다면 이걸 어떻게 처리할 것이냐
- 홀짝 구분 방문 리스트!
- 한 레벨마다 방문 리스트의 타겟 인덱스가 채워져있는지 확인하고, 채워져있다면 해당 레벨(문제로 치면 초수)에서 동생이 발견되었다는 뜻이므로 레벨을 리턴하면 된다.
📌 최종 풀이
import sys
input = sys.stdin.readline
def main():
def bfs(n,k):
q = [n]
cache = [[False]*500001 for _ in range(2)]
cache[0][n] = True
flag = 0
level = 0
while q:
if k > 500000: break
if cache[flag][k]: return level
tmp = []
flag = 1 - flag
for x in q:
for i in (x-1, x+1, x*2):
if 0 <= i <= 500000 and not cache[flag][i]:
cache[flag][i] = True
tmp.append(i)
level += 1
k += level
q = tmp
return -1
n,k = map(int, input().split())
print(bfs(n,k))
if __name__ == "__main__":
sys.exit(main())✔ 회고
- 맵지만 신박한 bfs 문제였다!
- 재방문이 허용된 +1, -1 이동의 반복은 이전 노드가 홀짝별로 누적되어 큐잉되는 방식이다.
- 다시 큐에 넣을 필요 없이, 홀짝 방문 리스트로 체크만 해주고 정해진 시간 안에 타겟 노드를 찾는데에만 집중하게 만든다.
