[백준 13549] 숨바꼭질 3 - python / if else

문제.

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

수직선을 탐색하는 문제다.

N에 위치한 수빈이가 K에 위치한 동생을 찾는데 걸리는 시간을 출력

이동방법은 3가지가 있다.

1. X+1의 위치로 이동한다. 1의 시간이 걸린다.
2. X-1의 위치로 이동한다. 1의 시간이 걸린다.
3. 2*X의 위치로 이동한다. 0의 시간이 걸린다.

가장빨리 N에서 K에 도달할 수 있는 시간을 출력하는 문제이다.

입출력 예시.

<입력 예시>
5 17

<출력 예시>
2
# 5 - 4 - 8 - 16 - 17로 2의 시간에 도달할 수 있다.

조건.

0 <= N <= 10^5
0 <= K <= 10^5
시간제한 2초

 

---

풀이.

수직선 그래프를 탐색하는 그래프탐색 알고리즘을 묻는 문제이다.

다익스트라 이론이나 약간 다른 조건이 있는 bfs탐색으로 해결할 수 있다.
구현이 쉽다고 생각되는 bfs로 풀이하였다.
+ 최단시간 결과를 보니 조건문 3개로도 간단하게 정답에 도달할 수 있었다.
   한 줄로 표현한 if - else 문법은 처음에 보면 이해하기가 어려울 수 있는데 아래 글에서 따로 설명해 두었다.

파이썬 변수 if else로 만들기/ 한 줄 if else

다음 탐색위치를 큐에 저장하고 먼저 입력된 값을 먼저 탐색하는(선입 선출) 방식을 너비우선 탐색 bfs라고 한다.

문제에서는 추가로 2*X로 가는데 걸리는 시간이 0이라는 가중치 그래프이기 때문에 우선순위를 따로 주어야한다.
X에서 0초만에 도달할 수 있는 2X의 위치는 appendleft로 바로 다음번에 검사할 수 있게 한다.
X+1, X-1의 경우는 큐의 뒤쪽에 추가하여 popleft로 항상 큐에서 가장 경과 시간이 작은 위치를 우선적으로 탐색할 수 있다.

이때 X-1의 탐색을 X+1보다 먼저 추가해 주어야 한다.
다음번에 2(X-1)을 X+2보다 우선적으로 확인하기 위함
> 2(X-1)은 1의 시간, X+2는 2의 시간이 소요된다. X가 4일 때 두 값은 같다.

시간 복잡도는 전부 걸어가는 경우 최대 K-N만큼의 시간이 걸릴 것
최대 범위 밖으로 순간이동 하는 경우가 필요한지 명시되어있지 않아서 탐색범위는 2*10^5까지로 설정했다.

제출 코드

import sys;input=sys.stdin.readline
from collections import deque

N,K=map(int,input().split())
visit = [-1]*(2*(10**5)+1)

queue = deque([N])
visit[N] = 0

while queue:
  if N >= K: ans = N-K; break #음의 방향으로는 순간이동할 수 없다.

  V = queue.popleft()

  if V == K: ans=visit[V]; break #K에 도달한 경우 최소시간에 도착했음이 보장된다.

  if 0 <= 2*V <= 200_000 and visit[2*V] == -1:
    visit[2*V] = visit[V]
    queue.appendleft(2*V)
    
  if 0 <= V-1 <= 200_000 and visit[V-1] == -1:
    visit[V-1] = visit[V]+1
    queue.append(V-1)
  
  if 0 <= V+1 <= 200_000 and visit[V+1] == -1:
    visit[V+1] = visit[V]+1
    que.append(V+1)

print(ans)

---

 

f=lambda n,k:n-k if n>=k else 1 if k==1 else 1+min(f(n,k+1),f(n,k-1))if k%2 else min(k-n,f(n,k//2))
n,k=map(int,input().split())
print(f(n,k))

ID: joonion님의 제출 코드이다.
한 줄로 풀이한 최단시간 코드가 인상깊었다. if문 3개만으로 단순하게 계산할 수 있는 문제였던 것
k를 k/2의 위치로 데려온다는 느낌의 풀이로 보인다.

풀어서 쓰면 다음과 같다.

def f(n,k):
	if k%2:
    	if k==1:
        	if n>=k: 
            	return n-k
            else: 
            	return 1
        else: 
        	return 1 + min(f(n,k+1),f(n,k-1)
    else: 
    	return min(k-n,f(n,k//2))