[코테]99클럽 코테스터디 7일차 TIL 백준 1697 숨바꼭질

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

이번 문제도 어제와 마찬가지로 그래프 탐색 문제이다. 나는 항상 코딩테스트 문제를 잘 풀기 위해서는 이 문제를 어떤 알고리즘을 사용하여 풀어야할지 고민해봐야한다고 생각하는데, 이문제는 최단경로 라는 단어에서 힌트를 준것 같았다. DFS는 깊이 우선탐색으로, 특정한 경로를 원할 때 주로 사용한다고 보면되고, BFS는

• 탐색을 현재 노드와 가까운 노드부터 순서대로 진행합니다.
• 큐를 사용하며, 먼저 들어온 노드부터 처리됩니다.
• 특징: BFS는 모든 경로를 동일한 깊이(거리)로 탐색하므로, 특정 노드에 처음 도달한 순간이 곧 최단 경로임이 보장됩니다. 
  라는 특징 때문에 이 문제에 사용할 수 있다고 생각하였다. 

---

처음에는 node를 print하면 최단경로가 나올줄 알았는데, node는 단지 방문 여부만 체크하므로, -1, +1, *2의 계산 방식으로 나올 수 있는 노드가 가까운 순서로 전부 나올뿐이였다. (예제의 경우5,4,6,10,3,8,7 등등)

import sys

from collections import deque

read = sys.stdin.readline

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

visited = [False] * (max(N,K) * 2 + 1)

def bfs(start):

    queue = deque()

    queue.append(start)

    visited[start] = True

    while queue:

        node = queue.popleft()

        print(node)

        if node == K:

            return

        for i in [node-1, node+1, 2*node]:

            if 0 <= i < max(N,K) * 2 + 1 and not visited[i]:

                queue.append(i)

                visited[i] = True

bfs(N)

---

따라서 GPT의 도움을 받아,,(나혼자 풀게될 날 언제오려나,,) 최단 거리를 체크하는 코드를 추가하여 다음과 같이 작성하여 성공하였다.

import sys

from collections import deque

# 입력

read = sys.stdin.readline

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

# 방문 배열 생성

visited = [False] * (max(N,K) * 2 + 1)

def bfs(start, target):

    # 큐에 현재 위치와 이동 횟수를 저장

    queue = deque([(start, 0)])  # (현재 위치, 이동 횟수)

    visited[start] = True

    while queue:

        node, distance = queue.popleft()

        # 목표에 도달하면 이동 횟수 반환

        if node == target:

            return distance

        # 가능한 다음 위치 탐색

        for next_node in [node - 1, node + 1, node * 2]:

            # 범위를 벗어나지 않고 방문하지 않은 경우만 큐에 추가

            if 0 <= next_node < max(N,K) * 2 + 1 and not visited[next_node]:

                queue.append((next_node, distance + 1))

                visited[next_node] = True

# BFS 호출 및 결과 출력

result = bfs(N, K)

print(result)