백준 - 13549번 숨바꼭질 (3) python 문제풀이 [Hellfer]

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

13549번: 숨바꼭질 3

🔷 알고리즘 분류 - BFS(너비우선탐색), 난이도 - 골드 5

🔶문제 풀이 - BFS(너비우선탐색)을 이용한 풀이

너비 우선 탐색(Breadth-First Search, BFS)은 그래프나 트리를 탐색하는 알고리즘 중 하나로, 시작 노드에서 가까운 노드부터 차례로 탐색하는 방법입니다. BFS는 "먼저 발견한 노드를 먼저 탐색한다"는 원칙에 따라 진행됩니다.

BFS의 주요 동작 원리는 다음과 같습니다:

탐색의 시작점(루트 노드)을 큐에 넣습니다.

큐에서 노드를 하나씩 꺼냅니다. 이때 꺼낸 노드가 탐색의 목표라면 탐색을 종료합니다.

꺼낸 노드가 탐색의 목표가 아니라면, 그 노드의 모든 이웃 노드 중 아직 방문하지 않은 노드를 큐에 넣습니다.

큐가 빌 때까지 이 과정을 반복합니다.

BFS는 이렇게 큐를 이용해 진행되므로, 먼저 발견한 노드를 먼저 탐색하게 되며, 이는 "시작 노드에서 가까운 노드를 먼저 탐색한다"는 특성을 만들어냅니다. 따라서 BFS는 최단 경로 문제 등에서 자주 사용됩니다.

하지만 BFS는 모든 간선의 비용이 동일할 때만 최단 경로를 보장합니다. 간선의 비용이 다른 경우에는 다익스트라 알고리즘 등 다른 알고리즘을 사용해야 합니다.

from collections import deque  # deque 라이브러리 호출

def bfs():  # 너비 우선 탐색 함수 정의
    queue=deque()  # 큐 생성
    queue.append(n)  # 시작점을 큐에 삽입
    visited[n]=0  # 시작점 방문 처리
    while queue:  # 큐가 빌 때까지 반복
        x=queue.popleft()  # 큐에서 가장 먼저 들어온 원소(현재 위치)를 꺼냄
        for nx in [x-1,x+1,x*2]:  # 현재 위치에서 이동 가능한 위치를 모두 검사
            if 0<=nx<100001 and visited[nx]==-1:  # 이동할 위치가 유효하고 아직 방문하지 않았다면
                if nx == x*2:  # 이동할 위치가 현재 위치의 2배라면
                    visited[nx]=visited[x]  # 이동할 위치를 현재 위치의 거리로 설정
                    queue.appendleft(nx)  # 이동할 위치를 큐의 왼쪽에 삽입
                else:
                    visited[nx]=visited[x]+1  # 이동할 위치를 현재 위치의 거리 + 1로 설정
                    queue.append(nx)  # 이동할 위치를 큐에 삽입

visited=[-1]*100001  # 각 위치의 방문 여부와 거리를 저장할 리스트 초기화
n,m=map(int,input().split())  # 시작점 n과 목표점 m을 입력 받음
bfs()  # 너비 우선 탐색 시작
print(visited[m])  # 목표점까지의 최단 거리 출력

 

🔶 초보자를 위한 생각주머니 키우기

🔸문제요약

이 문제는 시작점(n)에서 목표점(m)까지 이동하는데 필요한 최소 이동 횟수를 구하는 것입니다. 이동은 현재 위치에서 -1, +1, *2의 세 가지 방법이 가능하며, 이동 범위는 0 이상 100000 이하입니다.

🔸해결전략

이 문제를 해결하기 위해 너비 우선 탐색(BFS) 알고리즘을 사용합니다. BFS를 이용하면 시작점에서 가까운 위치부터 차례로 탐색할 수 있으므로, 시작점에서 목표점까지의 최소 이동 횟수를 효율적으로 구할 수 있습니다.

특히 이 문제에서는 현재 위치에서 *2 위치로 이동하는 경우 이동 횟수가 증가하지 않습니다. 따라서 이 경우에는 이동할 위치를 큐의 왼쪽에 삽입하여 우선적으로 탐색하도록 합니다. 이렇게 하면 *2로 이동하는 것이 더 빠른 경우에도 올바른 결과를 얻을 수 있습니다.

이렇게 BFS를 진행하면서 각 위치에 도달하는 데 필요한 최소 이동 횟수를 계산하면, 문제의 답을 구할 수 있습니다.

 

🤗파이팅입니다~ 여러분!!🤗