[BAEKJOON] 1697 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

---

 

이 문제는 어떻게 풀어야될지는 감은 잡았지만 코드로 바꾸는데에 좀 어려움을 겪은 문제...

 

일단 재 방문을 하지 않게 처리하기 위해 변수 선언

vi = [False] * 100001

s, d = map(int, sys.stdin.readline().strip().split())

100001인 이유는 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다 라고 적혀 있음.

그렇기에 방문할 수 있는 가능성은 100000까지 있는 것이다.

 

def isOkay(v):

    if(v < 0 or v > 100000 or (vi[v])):

        return False

    else:

        return True

방문 해도 되는 곳인지 처리하는 함수

함수를 만든 이유는 문제에서 이동 할 수 있는 경우의 수는 -1, +1, *2 이기에 3개를 체크해야되는데

그걸 일일히 코드 쓰기 귀찮아서 함수로 만들었다.

그리고 bfs와 dfs중 무엇을 사용할까 고민하다가 문제에서 요구하는 것이

가장 빠른 시간을 출력한다.라고 하니까 bfs를 택해서 풀었다.

그리고 사실 dfs로는 어떻게 구현해야될지 감도 안잡히기도 하고 ㅠ

 

def bfs(v):

    ret = -1

    que = deque()

    que.append((v, 0))

    vi[v]=True

    while que:

        print(que)

        _v, _d = que.popleft()

        if(_v == d):

            ret = _d

            break

        if isOkay(_v - 1):

            vi[_v - 1] = True

            que.append((_v-1, _d +1))

        if isOkay(_v + 1):

            vi[_v + 1] = True

            que.append((_v+1, _d +1))

        if isOkay(_v * 2):

            vi[_v * 1] = True

            que.append((_v*2, _d +1))

       

    return ret

구조는 해당과 같이 구현했다

아 근데 글쓰면서 깨달았는데

무언가 그 해당 위치에 저장해야되는 값이 있으면 bfs로 구현하라는 소리가 이 소리구나 싶었다.

 

import sys

from collections import deque

def isOkay(v):

    if(v < 0 or v > 100000 or (vi[v])):

        return False

    else:

        return True

def bfs(v):

    ret = -1

    que = deque()

    que.append((v, 0))

    vi[v]=True

    while que:

        print(que)

        _v, _d = que.popleft()

        if(_v == d):

            ret = _d

            break

        if isOkay(_v - 1):

            vi[_v - 1] = True

            que.append((_v-1, _d +1))

        if isOkay(_v + 1):

            vi[_v + 1] = True

            que.append((_v+1, _d +1))

        if isOkay(_v * 2):

            vi[_v * 1] = True

            que.append((_v*2, _d +1))

       

    return ret

vi = [False] * 100001

s, d = map(int, sys.stdin.readline().strip().split())

print(bfs(s))