BFS: 백준 13549 오답노트

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

---

1. 개요

• 입력:
  • 수빈이의 위치: $N=5$
  • 동생의 위치: $K=17$
• 이동 방법:
  • 걷기:
    $x\rightarrow x-1$
    $x\rightarrow x+1$
    (각각 1초 소요)
  • 순간이동:
    $x\rightarrow 2x$
    (0초 소요)
• 제한:
  이동 가능한 범위는 $0\le x\le \texttt{MAX}$이며, 여기서는 $\texttt{MAX}=200$로 임의 설정하여 설명함.
• 목표:
  수빈이가 동생에게 도달하는 최소 시간을 구함.
• 핵심 아이디어:
  간선의 가중치가 0과 1인 문제이므로 0-1 BFS를 사용.
  • 순간이동(0초)은 덱의 앞쪽에 추가하여 우선 적으로 popleft()될 수 있도록 함.
  • 걷기(1초)는 덱의 뒤쪽에 추가.
  • 한 번 방문한 노드는 다시 처리하지 않도록 $\texttt{visited}[x]$ 배열로 관리.

---

2. 0-1 BFS 알고리즘 개요

• 순간이동 (teleport):
  $x\rightarrow 2x$

  • 조건: $2x\le 200$
  • 비용: $0\text{초}$
  • 추가: 덱의 앞쪽 (appendleft)

• 걷기 (walk):
  $x\rightarrow x-1$
  $x\rightarrow x+1$

  • 비용: $1\text{초}$
  • 추가: 덱의 뒤쪽 (append)

• 방문 배열:
  $\texttt{visited}[x]$

  • 초기값: $-1$ (미방문)
  • 한 번 방문하면 최소 시간 값이 저장되어 중복 방문을 방지함.
  • 즉, visited[x]의 초기값인 -1 에서 어떤 값으로 변경되었다는 사실은 수빈이가 해당 visited[x]의 x까지 이르는데 visited[x]만큼 걸렸다는 사실과 동일함.

---

3. 단계별 실행 과정 (MAX=200, $N=5$, $K=17$)

다음 표는 각 BFS 반복(iteration)마다의 현재 노드 $x$,
해당 노드에서의 순간이동과 걷기 연산,
업데이트되는 $\texttt{visited}$ 값, 그리고 덱(Queue)의 상태를 정리한 것

단계	현재 노드 $x \, (\texttt{visited}[x])$	순간이동: $2x$ (조건, 새 방문시간)	걷기: $x-1, \; x+1$ (조건, 새 방문시간)	덱(Queue) 상태 (왼쪽이 먼저 꺼냄)	비고 및 방문 처리
0	–	–	–	[$5$]	초기 상태: $\texttt{visited}[5]=0$
1	$5 \, (0)$	$2\times5=10$ 조건: $10\le200$ 설정: $\texttt{visited}[10]=0$	$5-1=4$ → $\texttt{visited}[4]=0+1=1$ $5+1=6$ → $\texttt{visited}[6]=1$	[$10,\; 4,\; 6$]	5에서 출발
2	$10 \, (0)$	$2\times10=20$ 조건: $20\le200$ 설정: $\texttt{visited}[20]=0$	$10-1=9$ → $\texttt{visited}[9]=0+1=1$ $10+1=11$ → $\texttt{visited}[11]=1$	[$20,\; 4,\; 6,\; 9,\; 11$]	10 처리
3	$20 \, (0)$	$2\times20=40$ 조건: $40\le200$ 설정: $\texttt{visited}[40]=0$	$20-1=19$ → $\texttt{visited}[19]=0+1=1$ $20+1=21$ → $\texttt{visited}[21]=1$	[$40,\; 4,\; 6,\; 9,\; 11,\; 19,\; 21$]	20 처리
4	$40 \, (0)$	$2\times40=80$ 조건: $80\le200$ 설정: $\texttt{visited}[80]=0$	$40-1=39$ → $\texttt{visited}[39]=0+1=1$ $40+1=41$ → $\texttt{visited}[41]=1$	[$80,\; 4,\; 6,\; 9,\; 11,\; 19,\; 21,\; 39,\; 41$]	40 처리
5	$80 \, (0)$	$2\times80=160$ 조건: $160\le200$ 설정: $\texttt{visited}[160]=0$	$80-1=79$ → $\texttt{visited}[79]=0+1=1$ $80+1=81$ → $\texttt{visited}[81]=1$	[$160,\; 4,\; 6,\; 9,\; 11,\; 19,\; 21,\; 39,\; 41,\; 79,\; 81$]	80 처리
6	$160 \, (0)$	$2\times160=320$ 조건: $320>200$ → 무시	$160-1=159$ → $\texttt{visited}[159]=0+1=1$ $160+1=161$ → $\texttt{visited}[161]=1$	[$4,\; 6,\; 9,\; 11,\; 19,\; 21,\; 39,\; 41,\; 79,\; 81,\; 159,\; 161$]	160 처리 (순간이동 무시)
7	$4 \, (1)$	$2\times4=8$ 조건: $8\le200$ 설정: $\texttt{visited}[8]=1$	$4-1=3$ → $\texttt{visited}[3]=1+1=2$ $4+1=5$ → 무시 (이미 방문)	[$8,\; 6,\; 9,\; 11,\; 19,\; 21,\; 39,\; 41,\; 79,\; 81,\; 159,\; 161,\; 3$]	4 처리
8	$8 \, (1)$	$2\times8=16$ 조건: $16\le200$ 설정: $\texttt{visited}[16]=1$	$8-1=7$ → $\texttt{visited}[7]=1+1=2$ $8+1=9$ → 무시 (이미 방문)	[$16,\; 6,\; 9,\; 11,\; 19,\; 21,\; 39,\; 41,\; 79,\; 81,\; 159,\; 161,\; 3,\; 7$]	8 처리
9	$16 \, (1)$	$2\times16=32$ 조건: $32\le200$ 설정: $\texttt{visited}[32]=1$	$16-1=15$ → $\texttt{visited}[15]=1+1=2$ $16+1=17$ → $\texttt{visited}[17]=1+1=2$	[$32,\; 6,\; 9,\; 11,\; 19,\; 21,\; 39,\; 41,\; 79,\; 81,\; 159,\; 161,\; 3,\; 7,\; 15,\; 17$]	16 처리: 도착, $K=17$

• 각 단계에서 순간이동은 비용 $0$으로 처리되어, 현재 노드의 방문 시간 그대로 다음 노드에 전달됨.
• 걷기 연산은 현재 노드의 방문 시간에 $1$을 더해 할당되며
• 이미 방문된 노드(예: $5$, $9$ 등)는 다시 덱에 추가되지 않음.
• 최종적으로 $\texttt{visited}[17]=2$가 되어, 동생에게 도달하는 최소 시간이 $2$초임을 확인할 수 있음.
• 다만, 바로 17이 된 순간 정답이 도출되는 것은 아니고, 루프가 다 돌아서 해당하는 수(17)를 발견하게 되면 return됨.

---

4. 결론

• 최단 시간: $2\text{초}$
• 핵심 포인트:
  • $x\rightarrow 2x$ (순간이동, 비용 $0$)는 덱의 앞쪽에 추가되어 우선 처리
  • $x\rightarrow x-1$ 및 $x\rightarrow x+1$ (걷기, 비용 $1$)는 덱의 뒤쪽에 추가
  • $\texttt{visited}[x]$ 배열을 사용해 한 번 방문한 노드는 재방문하지 않으므로, 불필요한 연산과 무한 루프를 방지
  • 모든 이동은 $0\le x\le200$ 범위 내에서만 이루어짐.