[Python/BOJ] 백준 1697 숨바꼭질 (dfs)

 

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

1697번: 숨바꼭질

 

 

 

📄 문제

 

수빈이는 -1, +1, *2 로 움직일 수 있을때 

수빈이가 동생을 찾는 가장 빠른 시간은?

 

 

🖌 어떤 생각?

 

풀었던 문제 - 촌수계산과 비슷하겠거니 하고 풀었다. 

계속 틀렸다고 나와서 백준의 질문들을 읽어보았다. 

 

 

---

 

💡 새롭게 알게된 내용

내가 몰랐던 내용은 두가지였다. 

 

 

1. dist 배열은 0으로 초기화하면 귀찮아진다. 

 

이는 수빈이와 동생의 자리가 0일 수 도있다는 것을 생각해야한다. 

수빈이가 0 자리라면 *2 를 할 때에

아래 사진처럼 visited[0] 이 1이 되어버린다. 

이곳이 0이기에 처음방문한것이라 착각하고 +1을 하기때문이다. 

 

그래서 틀린다.

 

 

-> -1로 초기화를 하고 처음 시작할때 시작하는 곳을 0으로 만들어주었다.

https://www.acmicpc.net/board/view/78843

 

글 읽기 - 반례를 찾아주세요ㅠ

 

2. 100000 초과는 고려하지않아도 된다. 

 

https://www.acmicpc.net/board/view/81044

글 읽기 - 숨바꼭질 계속 터집니다

 

3. bfs는 먼저 찾아지는 해답이 곧 최단거리다. 

 

https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

 

 

 

 

---

 

 

 

📝정답코드

from collections import deque
x , y= map(int,input().split())

dist = [-1]*100001
def bfs(n):
    queue = deque()
    queue.append(n)
    while queue:
        node = queue.popleft()
        for i in (node+1, node-1,node*2) :
            if i < 0 or i > 100000 : continue
            if dist[i] == -1 : # 처음 방문
                dist[i] = dist[node]+1
                queue.append(i) 
dist[x] = 0
bfs(x)
print(dist[y])

 

 

매일 매일 꾸준히 알고리즘 풀자!