[Python] 이것이 코딩테스트다 5장 BFS/DFS

BFS 와 DFS의 핵심

 

 

완전탐색이라면 BFS, DFS에서 사실상 시간은 비슷하지만 일반적으로는 BFS가 더 성능이 좋고 보면된다.

왜냐하면 DFS는 재귀함수를 이용하며 BFS는 반복문을 기반으로 하기 때문

 

재귀와 반복의 시간차이는 피보나치 수열로 확인해보면 알 수 있다.

 

하지만, 완전 탐색이 아니라면

Backtracking같은 곳에서는 이야기가 다르다.

백트래킹에서는 DFS가 더 성능이 좋은경우가 많다. (예를들어 branch and bound)

Best first search (우선순위 큐 이용) > Depth first search (스택 이용) > Breath first search (큐 이용) 순이다.

이 밖에 더 좋은 알고리즘이 있을 수 있다.

 

어찌됐든 완전탐색을 해야하는 경우라면 BFS를 선호하는 것이 좋다.

 

인접행렬을 기반으로 BFS와 DFS를 구하여려면 두가지 모두 기본적으로는 visited (방문에 관한 내용을 담을 리스트)가 필요하다.

하지만 인접 행렬이 아니라면 이것 또한 유동적으로 방문 리스트는 없이 구현할 수도 있다.

 

 

 

DFS에 관한 얘기 

 

DFS는 스택 자료구조를 이용하며, 재귀를 이용한다.

 

 

BFS에 관한 얘기 

 

BFS는 큐 자료구조를 이용하며, 반복문을 이용한다.

주로 문제에서 최단거리를 구하라고하면 DFS보단 BFS로 구해야 한다.

파이썬을 이용할 때에는 deque를 사용하여 구하는 것이 좋다. 리스트랑 차이가 없어 보이지만, 파이썬에서 deque가 리스트보다 시간 면에서 빠르기 때문이다.

 

 

정리를 하자면.

각 간선들간의 가중치가 없는데 최단거리를 구하라하면 BFS, 간선들간의 가중치까지 있다면 그때는 다익스트라, 프림, 크루스칼 등을 이용하면 된다 💡

 

---

DFS 예제

 

 

 

📝 체감난이도 : ★★☆☆☆

 

🎨 내가 짠 코드

 

 

 

 

🎨 좀 더 효율적인 코드

 

 

 

 

 

 

 

🔑 Key Point 

 

비슷하게 구현을 하였지만 나는 방문 리스트가 for문 밖에 빠져 있고, 저자는 반복문 안에 있다. 

 

DFS는 하나하나 방문하기 때문에 반복문 바깥에서 방문했다고 놓아도 되며,

재귀를 타고들어가기 때문에 어찌보면 반복문 안에 있는 것과 같은 효과를 준다.

 

하지만 BFS는 한꺼번에 방문처리하여 큐에 넣기때문에 큐에 넣을때 바다 방문한 것이므로 반복문 안에 해주어야한다. 

 

---

BFS 예제

 

 

 

📝 체감난이도 : ★★☆☆☆

 

 

🎨 내가 짠 코드

 

 

 

🔑 Key Point 

 

저자랑 거의 비슷하게 구현해서 내 코드만 가져왔다

우선 BFS에서는 while queue: 라는 문이 자주 등장함을 알아두면 기계적으로 알아두면 좋을것 같다. 

그리고 그 이전에 구문들은 재귀함수가 아니므로 딱 한번만 실행된다. 

그리고 그 이후에는 큐에서 앞에서부터 빼줘야된다

 

---

음료수 얼려 먹기

 

 

 

📝 체감난이도 : ★★☆☆☆

 

 

🎨 내가 짠 코드

 

 

 

🎨 좀 더 효율적인 코드

 

 

 

 

🔑 Key Point 

 

이 문제는 인접행렬로 주어진 문제는 아니다.

하지만 인접한 노드들은 상, 하 ,좌, 우 4가지로 정해져 있기 때문에, 일일히 써서 넣어도 되지만,

구현 파트에서 캐치한 아이디어

dx = [-1,1,0,0]
dy = [0,0,-1,1]

를 이용하여 for문 4번을 돌려도 된다. 하지만 4번이라 아마 그냥 쓰는것이 코드수는 더 짧을것으로 보인다.

 

그리고 필요한 조건에 따라 주어진 범위가 벗어나면 return 되게 if문을 구현하였다.

 

그리고 dfs에 들어가기 전에, 이중포문을 이용하였는데 , 리스트에 0인 곳들에 대한 완전탐색을 모두 해보아야 하며 그 뭉탱이 들을 세는 것이 문제이기 때문이다

 

당연히 BFS로 구현해도되지만 DFS로 구현해보았다.

 

코드 길이의 수는 저자와 거의 비슷하다 (❁´◡`❁)

 

 

---

미로 탈출

 

 

 

📝 체감난이도 : ★★☆☆☆

 

🎨 내가 짠 코드

 

 

 

🎨 좀 더 효율적인 코드

 

 

 

🔑 Key Point 

 

이 문제는 최단 경로를 구하는 문제 이기 때문에 DFS가 아닌 BFS로 구현하는 것이 적합하다

완전 탐색에서 어떻게 최단 경로를 구하는지가 이 문제에 잘 나와있어 이해하기 쉬웠다. 

 

방문한 노드들의 값을 부모 노드 +1 을 하면 된다는 것이 키포인트 인듯하다

 

그렇게하여 목적지 까지 반복하면 목적지에서는 가장 짧은 경로로 왔을 때 그 거리가 나오게 된다 

 

 

 

내 코드에서 잘한점은

구현에서 배운 dx, dy 리스트를 이용하였다는 것

큐에 넣는 대상이 (x,y) 좌표 라는것

반복문안에서 x,y를 바로 업데이트 하지않고, 따로 잡아준 변수 nx,ny에 넣은뒤 조건에 만족하는지부터 검사하였다는 것.

 

 

 

부족한 점은

방문리스트를 따로 잡을 필요가 없었다

graph[nx][ny]==1 

이라면 처음 방문하는 노드라는 것이기 때문에 if 문 한 줄이였음 충분했다 😂

 

그리고 count 를 잡아주어서 부모 노드 +1 해줄 필요가 없다. nx, ny는 업데이트 된 따로 잡아준 변수 이기 때문에

업데이트 되기 전인 x, y를 이용하면 바로 부모 노드가 나온다 즉

graph[nx][ny] = graph[x][y]+1

이 한줄이면 충분했다

 

 

 

 

마무리

 

DFS / BFS는 감을 계속 풀어 익히는것이 중요한 것 같다. 책의 문제 말고도 다른 사이트에서 꾸준히 풀어봐야 될 것 같다😣