BFS(백준 : 숨바꼭질-1697문제) 접근 방법

- 백준 : https://www.acmicpc.net/problem/1697

 

 

1. 생각해보기

1) 아이디어

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

입력 N, K를 받는다.

가장 빠른 시간 임으로 BFS로 문제를 푼다.

 

기존에는 상하좌우로 케이스를 선정했다면, 이번에는 X-1, X+1, 2*X 케이스로 가장 빠른 시간이 몇초인지를 구한다. 

 

 

2) 시간복잡도

BFS 임으로 O (V + E)이다. 

간선은 최악의 경우 100,001이다. 

정점은 3 * 100,001이다. (1초 안에 OK)

= O(V + 3V)

= O(4V)

=> O(V)

 

 

3) 자료구조

BFS 필수 구성요소 : 큐, 방문 배열

head

N, K

 

2. 직접 풀어보기

https://github.com/moonlight-duck/study-algorithms/pull/21

[민주] BFS 문제풀이 1 by min-99 · Pull Request #21 · moonlight-duck/study-algorithms

 

결과)