백준 1697번 숨바꼭질 문제풀이, 파이썬

백준 1697번 : 숨바꼭질 문제풀이 [파이썬] 

---

<문제>

 

1697번 문제의 내용은 아래와 같습니다. 

 

 

숨바꼭질 

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

---

 

 

<작성한 코드>

 

---

 

 

<코드 풀이>

 

본 문제는 BFS 알고리즘을 사용해 풀었다. 

본 문제에 DFS 알고리즘을 사용하면 각 노드마다

얼마나 깊이까지 가는지 모두 확인해서 결과값을 도출해야하기 때문에 굉장히 비효율적이다.

따라서 BFS를 사용해 동일한 그래프 깊이에서 동생의 위치에 도달하는 경우가 생기면 

결과값을 도출할 수 있도록 BFS를 사용하는 것이 더 효과적이라고 생각했다. 

 

 

문제의 기본 세팅은 위와같다.

array라는 이름의 리스트를 만들어준 이유는 

수빈이가 이동한 위치를 걸린 시간과 함께 방문처리 하기 위함이다. 

즉 array의 인덱스는 수빈이의 위치를 , 그 인덱스에 해당하는 값에는 걸린 시간을 넣어주려고 했다. 

(범위를 저렇게 설정한건 문제에서 점 N(0 ≤ N ≤ 100,000)의 범위를 설정해주었기때문)

 

bfs 함수를 정의한 내용은 위와 같다. 

큐에 들어있는 값을 빼내어 v라는 변수에 할당하는데

이때 이 값은 수빈이가 이동해가는 위치를 의미하고, 이런 v와 동생의 위치가 같다면

결과값을 출력하면 되는거기때문에 array[v]를 통해 담겨있는 원소인

걸린 시간을 리턴하도록 했다. 

 

조건문) if 0<=i<=100000 and not array[i]

위 조건문을 조금 설명해보자면 

i값, 즉 수빈이가 이동할 위치가 주어진 점의 범위를 벗어나지 않고,

not array[i]일때만 다음의 코드들을 수행하도록 작성했다.

만약 수빈이가 이동할 위치가 이미 방문한 위치였다면 array[i]의 값에는 초기값 0이 아닌

다른 숫자가 들어있을 것이다. 따라서 중복 방문을 피하기 위해 초기값 0이 들어있는 위치일때만

방문하도록 처리하기 위해서 not array[i]를 썼다.

(방문 안했다면 값이 0으로, 불리언 값으로 false를 갖는데, not false일때 실행 -> 즉 0이면 항상 실행)