99클럽 코테 스터디 _ 7일차 TIL (BFS)

 

< 문제 >

[백준] 1697. 숨바꼭질 / 실버1

---

< 풀이 >

코드 변수 정의

• x, time : 현재 위치, 현재 위치까지 오는 데 걸리는 시간
• ans : 수빈이가 동생을 찾을 수 있는 가장 빠른 시간

---

BFS
시간복잡도 : O(N)  *N=100001 (문제에서 위치 최대 값+1)

from collections import deque

# bfs 함수 : N에서 K로 이동하는 최소 시간을 계산
def bfs(N, K, time):
	# 큐를 생성하고 초기 위치와 시간(time=0)을 삽입
    q = deque()
    q.append((N, time))
    # 위치 x를 방문했는지 방문 여부 기록
    visited = [False] * 100001
    # 최소 시간 변수 (초기값=무한대)
    ans = float('inf')
    
    # 탐색
    while q:
        x, time = q.popleft() # 현재 위치 x와 해당 위치까지 걸린 시간 time을 큐에서 꺼냄
        visited[x] = True # 현재 위치 방문 처리
        
        # K인 경우, 최소 시간 갱신
        if x == K:
            if ans > time:
                ans = time
        
        # 이동 가능한 3가지 경우를 큐에 추가
        # 1. x-1로 이동
        if 0 <= x - 1 < 100001 and not visited[x-1]:
            q.append((x - 1, time + 1))
        # 2. x+1로 이동
        if x + 1 < 100001 and not visited[x+1]:
            q.append((x + 1, time + 1))
        # 3. 2*x로 순간이동
        if 2 * x < 100001 and not visited[2*x]:
            q.append((2 * x, time + 1))
            
	# 탐색 종료 후, 최소 시간 반환
    return ans

        
def f():
    N, K = map(int, input().split())
    if N == K: print(0) # 만약 수빈이와 동생의 위치가 같으면 이동할 필요가 없음
    else: print(bfs(N, K, 0))

f()

---

풀이 과정

1. 초기화
   • 큐(deque)를 생성하고, 시작 위치 N과 초기 시간(0초)을 큐에 삽입한다.
   • 방문 여부를 기록하는 visited 배열을 생성하여 초기에는 모두 False로 설정한다.
2. BFS 탐색
   • 큐에서 현재 위치 x와 해당 위치까지 걸린 시간을 popleft로 꺼낸다.
   • 현재 위치를 방문 처리(visited[x]=True)하여 중복 탐색을 방지한다. (+무한 루프 방지)
   • 현재 위치 == K인 경우  →  최소 시간 값을 갱신
   • 현재 위치에서 이동 가능한 3가지 경우(x-1, x+1, 2*x) 계산
     • 각 경우에 대해 위치(x)가 0 ~ 100,000이며, 아직 방문하지 않은 경우만 큐에 삽입한다.
     • 각 위치로 이동하는 경우 1초의 시간이 경과하므로 큐에 time 값을 time + 1로 넣어준다.
3. 탐색 종료 조건
   • 큐가 비어있지 않을 때까지 탐색 진행

---

< 회고 >

🤔 💭_

bfs로 풀어야겠다는 생각은 했지만, 최단 시간을 구하기 위해 q에 time 변수를 위치와 함께 저장하는 방법을 생각하는 데 풀이 시간이 소요됐다. bfs 탐색 과정에서 x-1로 이동하는 경우 x가 음수 값을 가질 수 있다는 것을 인지하지 못해서 처음에 틀렸었다.

 

문제를 BFS로 풀이한 이유

• 모든 경로를 동일한 단위로 탐색한다.
  • BFS는 같은 깊이에 있는 노드를 탐색하기 때문에 가장 먼저 도달한 경로가 최단 경로임이 보장된다.
• 최소 시간을 구하기 위해 최단 거리를 효과적으로 탐색 가능하다.

---

BFS에서 변수를 두 개  이상 사용하는 경우(위치와 시간 or 좌표와 상태 등)

 

 

1. 큐에 저장하는 데이터의 구조

BFS에서 변수를 두 개 이상 사용할 때, 일반적으로 큐에 튜플 or 리스트 형태로 데이터를 저장

 

예시

• 위치, 시간 : (x, time)
• 좌표, 상태 : (x, y, 상태)
• 노드, 방문 여부 : (node, visited)

 

 

2. visited 배열 확장

 

예시 1 : 2차원 방문 배열 (좌표 기반 문제)

visited = [[False] * m for _ in range(n)]  # n x m 격자

 

예시 2 : 3차원 방문 배열 (추가 상태를 포함한 문제)

visited = [[[False] * 상태개수 for _ in range(m)] for _ in range(n)]

 

활용 예시

• 미로 탐색에서 벽 부수기 (추가 상태 : 벽을 부쉈는지 여부)
  • visited[x][y][has_broken]