[백준 13549번] 파이썬 - 숨바꼭질 3

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

13549번: 숨바꼭질 3

 

 

# 조건

• 수빈이는 동생과 숨바꼭질하고 있다.
• 현재 점 N에 있고, 동생은 점 K에 있다.
• 수빈이는 걷거나 순간이동을 하는데
  • 걷는다면 1초 후에 X-1 또는 X+1로 이동
  • 순간이동을 하면 0초 후에 2 * X로 이동
• 수빈이와 동생의 위치가 주어질 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하여라

 

# 접근 방법 및 Solution

• 현재 점 N을 0으로, N-1 과 N+1은 +1을,
• N * 2의 위치는 + 0을 해준다.
• 우선 도착점이 현재 위치보다 왼쪽에 있다면 바로 print(현재 위치 - 동생위치)
• 아니라면 bfs를 활용한 우선순위를 사용해준다.
  • 비용이 0과 1로 나뉘어져 있기 때문에
  • 최단거리를 알기 위해서 순회 순서에 우선 순위 부여
  • 2로 이동하는 경우는 비용 그대로
  • 아니라면 비용만 +1하여 q에 담아준다.
  • 따라서 * 2, -1, +1의 순서로 순회해준다.
• 아래 코드의 경우 pass는 하였지만, 방문 순서 중 loca+1이 제일 마지막이 아닌 경우 틀렸습니다. 를 받았다.
• 이미 방문한 경우 -> 재방문하지 않는다.
• 순회 순서에 우선순위를 부여하였기 때문

import sys  
sys.stdin = open('input.txt')  
from collections import deque  
  
def bfs(start):  
    visited = [0] * 100001  
    visited[start] = 1  
    q = deque()  
    q.append([start, 0])  
    while q:  
        loca, dist = q.popleft()  
        if loca == K:  
            return dist  
        for i in (loca*2, loca-1, loca+1):  
            if 0<=i<100001 and visited[i] == 0:  
                if i == loca*2:  
                    q.append([i, dist])  
                else:  
                    q.append([i, dist+1])  
                visited[i] = 1  
N, K = map(int, input().split())  
  
if K <= N:  
    print(N-K)  
else:  
    print(bfs(N))
    

• 따라서, 아래와 같이 가장 최소값으로 table을 갱신해주는 작업을 추가해주니
• 순회 순서에 상관없이 통과

import sys  
sys.stdin = open('input.txt')  
from collections import deque  
  
def bfs(start):  
    visited = [float('inf')] * 100001  
    visited[start] = 0  
    q = deque()  
    q.append(start)  
    while q:  
        loca = q.popleft()  
        for i in (loca+1,loca-1, loca*2):  
            if 0<=i<100001:  
                if i == loca * 2:  
                    if visited[i] > visited[loca]:  
                        visited[i] = visited[loca]  
                        q.append(i)  
                else:  
                    if visited[i] > visited[loca] + 1:  
                        visited[i] = visited[loca] + 1  
                        q.append(i)  
    print(visited)  
    return visited[K]  
N, K = map(int, input().split())  
  
if K <= N:  
    print(N-K)  
else:  
    print(bfs(N))