https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
우선 이 문제는 BFS로 분류되어 있는 문제이기도 하고,
"최소"시간을 구하는 문제이니 BFS가 효율적이라 생각했다.
하지만 어떻게 BFS를 구현할까 생각했다.
from collections import deque
n, k = map(int, input().split())
visit = [-1] * 100001
visit[n] = 0
q = deque()
answer = 999999999392193921939129999
q.append(n)
while q:
idx, time = q.popleft()
if answer < time:
answer = time
elif idx % 2 != 0:
q.append((idx + 1, time + 1))
q.append((idx - 1, time + 1))
else:
q.append((idx // 2, time))
print(answer)처음 제출한 코드이다.
우선 n에서 k로 가는 것이 아닌, k에서 n으로 가는 것으로 진행했다.
n이 홀수라면 n +1, n-1을 각각 q에 담고 짝수라면 //2를 진행했다.
여기서 n이 100,000보다 작은지 0보다 크거나 같은지 체크까지 했지만 무한루프에 빠져버렸다.
고민끝에 다른 이의 정답을 보기로 결정했다
아래는 다른 이의 코드를 참조하여 다시 작성한 코드이다.
from collections import deque
n, k = map(int, input().split())
visit = [-1] * 100001
visit[n] = 0
q = deque()
q.append(n)
while q:
idx = q.popleft()
if idx == k:
print(visit[k])
break
if 0 <= idx - 1 < 100001 and visit[idx-1] == -1:
visit[idx-1] = visit[idx] + 1
q.append(idx - 1)
if 0 < idx * 2 < 100001 and visit[idx*2] == -1:
visit[idx*2] = visit[idx]
q.appendleft(idx*2)
if 0 <= idx + 1 < 100001 and visit[idx+1] == -1:
visit[idx+1] = visit[idx] + 1
q.append(idx+1)여기서 곰곰히 생각했다.
idx * 2가 100001보다 작은지 체크하는 if문 내부에서 q.append()가 아닌 q.appendleft()를 하는 이유를 생각했다.
답은 조금만 생각하면 금방 나왔다.
일일이 +1, -1을 하는 것보다 *2를 해버리는 것이 더 빨리 접근할 수 있고, 시간을 잡아먹지 않기 때문이다.
역시 정답률 23퍼센트 문제답게 어려웠다..
언제쯤이면 이것도 쉽게 풀 수가 있을까...