[백준] 13549번 숨바꼭질 3 풀이 파이썬(python)

13549번: 숨바꼭질 3

---

[문제]

---

[코드]

from collections import deque

n , k = map(int, input().split())
visited = [0] * 100001

def bfs():
    q = deque()
    q.append(n)
    while q:
        now = q.popleft()
        if now == k:
            return visited[now]
        for next_to in [now*2, now-1, now+1]:
            if 0 <= next_to <= 100000 and not visited[next_to]:
                q.append(next_to)
                if next_to == now*2:
                    visited[next_to] = visited[now]
                else:
                    visited[next_to] = visited[now] +1

print(bfs())

---

[해설]

전형적인 bfs 문제이다

 

문제의 핵심은 아래와 같다

1. BFS를 어떠한 조건을 걸어서 구현할 것인가

2. 그리고 내가 움직일 수 있는 위치가 3개인데 이중 2배로 가는 것은 초가 증가하지 않는다는 조건을 어떻게 이용할까

 

코드를 보면서 자세히 살펴보자

 

from collections import deque

n , k = map(int, input().split())
visited = [0] * 100001

우선 deque를 활용해서 bfs를 할 것이기 때문에 import 해준다

그리고 n, k 변수의 현재 나의 위치와 우리가 원하는 목표점을 변수로 지정해준다

그리고 bfs 필요한 방문표를 100001개 0으로 채워서 만들어 준다

여기서 만들어지는 visited list는 이동한 숫자도 함께 기록할 것이다

 

def bfs():
    q = deque()
    q.append(n)
    while q:
        now = q.popleft()
        if now == k:
            return visited[now]
        for next_to in [now*2, now-1, now+1]:
            if 0 <= next_to <= 100000 and not visited[next_to]:
                q.append(next_to)
                if next_to == now*2:
                    visited[next_to] = visited[now]
                else:
                    visited[next_to] = visited[now] +1

그리고 문제의 핵심인 bfs를 함수로 정의해준다

우선 q에 deque를 지정해주고 우리의 위치를 추가해준다

그리고 q가 빌때까지 while문을 실행주는데 

여기서 while문을 돌면서 방문 위치에 걸리는 시간을 갱신할 것이다

자세 살펴보면 우선 q의 가장 왼쪽 값을 pop해주고 

만약 이 지점이 - now 우리의 목표지점 k와 같다면 함수를 멈추고 visited에 저장되어 있는 now까지 걸린 시간을 return 해준다

그리고 아니라면 아래의 for문을 도는데 여기서 중요한 점이 있다

 

now*2의 경우 0초가 걸리기 때문에 최소시간을 구할 때 우선순위를 주어야한다

하지만 now-1 , now+1로 now * 2가 갈 수 있는 위치에 먼저 간다면 이는 시간적으로 분명 손해가 생길 것이다

그래서 for문에서 now*2가 먼저 갈 수 있도록 for문이 도는 list에 처음에 위치 시켜준다

사실 이부분 때문에 한번 문제를 틀렸다 

 

그리고 이렇게 갱신된 다음으로 갈 수 있는 위치가 최소 최대 범위 안에 위치하고 아직 방문을 하지 않았을 경우 

q에 추가해준다

 

그리고 여기서 핵심인 것이 만약 우리가 갈 수 있는 위치가 now *2이면 0초가 걸리니까 visited에 시간을 그래도 전달해주고 만약 다른 경우 - x-1, x+1라면 현재위치까지 걸린 시간에 + 1을 해서 다음 위치까지 걸리는 시간을 갱신해준다

 

print(bfs())

그리고 bfs의 리턴값을 주었기 때문에

print를 찍으면 우리가 원하는 최소 소요시간이 출력되게 된다