백준 1697번 <숨바꼭질>

백준 알고리즘 1697번

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

1697번: 숨바꼭질

---

1697번

동생과 숨바꼭질을 하는 언니가 동생을 잡는데 몇 초가 걸리는지 구해라.

언니의 위치가 x일 때, 1초 후에 언니는 x-1, x+1, 2x 중 하나로 이동한다.

 

입력은 첫 줄에 언니의 위치 N과 동생의 위치 K가 주어진다.

 

출력으로는 언니가 동생을 찾는 가장 빠른 시간을 출력한다.

---

문제 해결

이 문제는 bfs를 이용하여 풀 수 있다.

이 문제에서는 x-1, x+1, 2x를 인접노드라고 생각한다.

 

visit 배열은 그 위치로 가는데 걸린 시간을 저장하고 있는 배열이다. 

가장 빠른 시간을 구하는 것이기 때문에 visit 배열을 update할 때는 min값으로 하기 때문에 초기 값은 INF로 한다,

visit 배열의 크기는 언니와 동생의 위치의 최대 값인 100000 인덱스까지 갖도록 한다.

 

1) 언니의 위치를 큐에 넣는다. 언니의 위치에 해당하는 visit의 배열 값을 0으로 한다.

2) 큐에서 위치를 뺀다. 그 위치에 대한 minus, plus, twice를 구한다.

minus	0보다 크거나 같고 visit[minus]의 값이 visit[위치]+1보다 크면 update. queue에 minus를 넣는다.
plus	100000보다 작거나 같고 visit[plus]의 값이 visit[위치]+1보다 크면 update, queue에 plus를 넣는다.
twice	100000보다 작거나 같고 visit[twice]의 값이 visit[위치]+1보다 크면 update, queue에 twice를 넣는다.

3) queue가 빌 때까지 2)를 반복한다.

3) visit[k]를 출력한다.

---

코드

from collections import deque
INF = int(1e9)
n, k = map(int, input().split())


def bfs(start):
    visit = [INF for i in range(100001)]
    visit[start] = 0
    queue = deque()
    queue.append(start)
    while queue:
        temp = queue.popleft()
        for next in (temp-1, temp +1, temp*2):
            if 0 <= next <= 100000 and visit[next] > visit[temp]+1:
                visit[next] = visit[temp]+1
                queue.append(next)
        
    print(visit[k])
bfs(n)

from collections import deque
INF = int(1e9)
n, k = map(int, input().split())


def bfs(start):
    visit = [INF for i in range(100001)]
    visit[start] = 0
    queue = deque()
    queue.append(start)
    while queue:
        temp = queue.popleft()
        minus = temp - 1
        plus = temp + 1
        twice = temp * 2

        if minus >= 0:
            if visit[minus] > visit[temp] + 1:
                visit[minus] = visit[temp]+1
                queue.append(minus)
        if plus <= 100000:
            if visit[plus] > visit[temp] + 1:
                visit[plus] = visit[temp] + 1
                queue.append(plus)
        if twice <= 100000:
            if visit[twice] > visit[temp] + 1:
                visit[twice] = visit[temp] + 1
                queue.append(twice)
    print(visit[k])
bfs(n)

두 개는 같은 코드인데 위의 코드가 더 간결한 것을 볼 수 있다.

---

결과

---