[파이썬] 백준 13549 : 숨바꼭질 3 (골드5)

[파이썬] 백준 13549 : 숨바꼭질 3 (골드5)

 

13549번: 숨바꼭질 3

---

문제

---

풀이

0. 방향성 생각

최단거리 문제라서 BFS로 푼다.

리스트를 받아서 탐색한 경우에는 큐에 넣어주지 않는다.

또한 순간이동에 0초가 걸리므로 한 번 큐에 들어가면 그 배수들은 모두 그 시간대로 탐색된다.

이 때 엣지케이스 0을 고려하지 않으면 0의 2배인 0을 큐에 계속 추가하여 무한루프에 빠질 수 있다.

1. 입력 받기

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

a,b = map(int,input().split())
limit = 100001
time = [0]*limit

 

2. BFS 함수 정의

def bfs(x,y):
    q = deque()
    if x == 0 :
        q.append(1)
    else :
        q.append(x)
    
    while q:
        x = q.popleft()
        if y == x :
            return time[x]
        
        for nx in (x-1,x+1,x*2):
            if 0 <= nx < limit and time[nx]==0:
                if nx == 2*x :
                    time[nx] = time[x]
                    q.appendleft(nx)
                else : 
                    time[nx] = time[x] + 1
                    q.append(nx)

입력이 0으로 들어왔을 때 1부터 시작하는 것으로 변경한다.

범위 내에 있고 탐색하지 않았을 때 2x를 먼저 탐색해야하니 큐에 맨 앞에 넣어준다.

그렇지 않은 경우에는 이전 시간에 +1을 해주고 큐 뒤에 넣어준다.

 

3. 출력

if a==0:
    if b==0:
        print(0)
    else:
        print(bfs(a,b)+1)
else :
    print(bfs(a,b))

a가 0인 경우에는 0에서 1로 가는 경우를 고려해서 bfs값에 +1을 해준다

---

전체코드

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

a,b = map(int,input().split())
limit = 100001
time = [0]*limit

def bfs(x,y):
    q = deque()
    if x == 0 :
        q.append(1)
    else :
        q.append(x)
    
    while q:
        x = q.popleft()
        if y == x :
            return time[x]
        
        for nx in (x-1,x+1,x*2):
            if 0 <= nx < limit and time[nx]==0:
                if nx == 2*x :
                    time[nx] = time[x]
                    q.appendleft(nx)
                else : 
                    time[nx] = time[x] + 1
                    q.append(nx)

if a==0:
    if b==0:
        print(0)
    else:
        print(bfs(a,b)+1)
else :
    print(bfs(a,b))

---

SET, BFS를 쓴 풀이

from collections import deque

s,e = map(int,input().split())

t = 0
if s==e:
    print(t)
else:
    Q = deque()
    V = set()
    
    if s==0:
        s = 1
        t = 1
        V.update([0,1])
        
    Q.append((s,t))
    V.add(s)
    
    while Q:
        x,t = Q.popleft()
        
        if x==e:
            break
        
        for nx in (2*x,x-1,x+1):
            
            if 0<=nx<=100000:
                if nx not in V:
                    V.add(nx)
                    if nx == 2*x:
                        Q.appendleft((nx,t))
                    else:
                        Q.append((nx,t+1))
    print(t)

• set과 BFS를 사용해서 푼 풀이.
• 0인 경우에는 도착점이 0이 아닌 이상 항상 1로 이동해야한다.
• 시작 정점을 추가해주고, 큐에 위치와 시간을 같이 넣는다. (딕셔너리 사용하면 시간을 같이 기록해도 된다)
• 마찬가지로 2배수인 점은 같은 정점이므로, appendleft로 순위 높여주기.

dict, 다익스트라를 쓴 풀이

import heapq as hq

s,e = map(int, input().split())

t = 0
if s == e:
    print(t)
else:
    heap = []
    V = {}
    
    if s == 0:
        s += 1
        t += 1
        V[0] = 0
    V[s] = t
    
    hq.heappush(heap,(t,s))
    while heap:
        t,x = hq.heappop(heap)

        if x == e:
            print(t)
            break

        for nx in (x+1,x-1,2*x):
            if 0 <= nx <= 100000:
                nt = t + (nx!=2*x)

                if nx not in V or nt<V[nx]:
                    V[nx] = nt
                    hq.heappush(heap,(nt,nx))

• 결은 비슷한데, 힙에 추가하는 과정에서 알아서 최소 시간을 뺄 거라 appendleft같은 메서드를 사용할 필요가 없다.

---

코멘트

• a=0,1일 때가 엣지케이스인데 0일 때 무한루프를 못잡아서 삽질했음..
• 다른 숨바꼭질 문제도 그렇고 0,1이 시간적으로 많이 소모된다.
• 0에서 무한루프 일어난다든가, 1에서 다시 0으로 가서 쓸데없는 연산을 한다든가 문제가 발생한다.
• 엣지케이스가 두개라서 따로 if문으로 처리를 하는게 이득이다.
• 그리고 전 구간에 대해서 bfs 탐색하면 시간 소요가 커서 목적지점에 도달했으면 탈출시켜주는게 시간적으로 이득이다.
• 또한 a>b같은 경우도 탐색보다 그냥 값을 빼서 구하는게 이득이다.

 

• 0-1 너비우선
• 시작점의 배수는 같은 정점으로 판단해야한다. appendleft를 통해서 우선 순위를 높여주기