백준 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이면 항상 실행)
'백준 알고리즘' 카테고리의 다른 글
백준 2750번 수 정렬하기 파이썬 문제풀이 (0) | 2023.02.23 |
---|---|
백준 11724번 연결 요소의 개수 문제풀이, 파이썬 (0) | 2023.02.10 |
백준 7576번 토마토 문제풀이, 파이썬 (0) | 2023.02.08 |
백준 1012번 유기농 배추 문제풀이, 파이썬 (0) | 2023.02.07 |
백준 2667번 단지번호 붙이기 문제풀이, 파이썬 (0) | 2023.02.02 |