#1697_숨바꼭질 #백준 #파이썬 #BFS

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

1697번: 숨바꼭질

 

#1697 숨바꼭질 (BFS)

import sys

from collections import deque

input = sys.stdin.readline

def bfs(n, m, v):

    q = deque([n])

    v[n] = 1

    count = 0

    if n == m:     <----문제의 코드... 이 코드를 안 넣어서.. 계속 실패가 뜸... 1시간 날림 ㅠㅠ n,m이 같아서 0이 리턴될 때를 

        return 0              생각 안함 ㅠㅠ

    while q:

        for _ in range(len(q)):

            i = q.popleft()

            for j in [-1, 1, i]:

                dx = i + j

                if 0 <= dx <= 100000 and v[dx] != 1:

                    if dx == m:

                        return count +1

                    else:

                        v[dx] = 1

                        q.append(dx)

        count += 1    

   

n, m = map(int,input().split())

v = [0] * 100001

print(bfs(n, m, v)) 

 

첫번째 코드가 처음에 접근했던 방식이고, 이 문제는 좀 많이 뼈가 아픈 문제이다... 1시간 동안 풀었다... 왜냐하면,,, n과 m이 같아서 0이 리턴될 때를 생각을 안했기 때문에 계속 실패가 떴다....결국 1시간 동안 고민하다가 알아차렸다... 그래도 풀었으니까 됐다... 이 문제는 bfs(너비 우선 탐색) Breath-First Search 을 통해 풀 수 있다. 한단계를 찾을 때 마다 count 변수를 증가 시켜주면 된다. 

예를 들면  n,m 값에 5 17를 입력하면 5라는 숫자에서 17까지 +1,-1,현재 숫자*2이 세가지 방법을 통해 접근을 해야한다. 그리고 각 방법을 쓸 때 무조건 1초가 소요된다. 따라서 5에서 17까지 최단 시간안에 도착하는 단계는   5-10-9-18-17 4초이다. 이 단계는 5(1노드)-> 4, 6, 10 (2노드) -> 3,8,7,12,9,11,20 (3노드) -> 2,16,14,13,24,18,22,19,21,40 (4노드) -> ...17....(5노드) (5노드는 너무 많아서 생략할게요...) 이런 씩으로 bfs를 구현할 수 있다 각 단계를 지날 때 마다 count += 1 해주면 된다는 사실 ㅎㅎ 

 

BFS를 모르신다면 유튜브로 쉽게 좋은 영상들을 찾을 수 있으니 시청 바란다.

from collections import deque

def bfs(N, K):

    visited = [False] * 100001  # 방문 여부를 저장하는 리스트

    queue = deque([(N, 0)])      # 시작 지점과 현재까지의 시간을 저장하는 큐

    visited[N] = True           # 시작 지점 방문 표시

    while queue:

        current, time = queue.popleft()  # 현재 위치와 시간을 가져옴

        if current == K:  # 동생을 찾았을 때 시간 반환

            return time

        # 다음 이동할 위치 계산 및 큐에 추가

        for next_pos in [current - 1, current + 1, current * 2]:

            if 0 <= next_pos <= 100000 and not visited[next_pos]:

                visited[next_pos] = True  # 방문 표시

                queue.append((next_pos, time + 1))  # 시간을 1초 증가시킴

N, K = map(int, input().split())

print(bfs(N, K))

두번째 코드인 이것은 더욱 더 가독성 좋고, 바로 알아 볼 수 있게 더 정리하여서 만들었다. 남들이 보기에도 좋게 만드는 것이 잘 숙달되어야겠다는 생각을 했다 ㅎㅎ