[Python] 백준 1260번(DFS와 BFS) - BFS 알고리즘

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

---

아이디어

1. 인접리스트를 만들어주고 문제에서 요구한대로 깊이 우선탐색과 너비 우선탐색 알고리즘을 만들면 된다.

 

 

코드

새롭게 알게 된 것

1. 오름차순, 내림차순으로 정렬할 때 sort함수를 활용한다는 건 알고 있었지만. 리스트 내부 리스트에도 sort가 가능한지는 모르고 있었다. 가령, graph = [ [], [1, 3], [4, 2] ] 이렇게 리스트가 있을 때, graph[2].sort() 를 쓰면 graph 2번째 인덱스 리스트가 오름차순으로 정렬이 가능하다.

 

2. BFS알고리즘의 작동원리 개념을 구체화했다. 처음 배울 때, DFS는 상대적으로 이해하기 쉬웠는데 BFS는 도저히 이해가 안갔다. 그런데 이번 문제를 통해 확실히 이해함. 큐 자료구조를 활용하기 위해 deque을 지정해준다. 예를 들어 위의 코드를 기준으로, 최초 bfs(graph, 1, visited2) 함수를 실행하게 된다면 큐라는 자료구조안에 1이 가장 먼저 쌓인다. 이후 popleft 함수를 통해 가장 먼저 쌓인 1을 리턴한다. 즉 변수 v에 리턴값 1을 받는다는 뜻이다. 계속해서 for 반복문과 append 함수를 통해 큐 자료구조에 데이터가 쌓이고 리턴의 반복.

 

+) while queue:     <-- 이 반복문의 뜻이 처음 책으로 공부했을 때는 큐가 빌 때까지 반복이라고만 설명이 되어 있었다. 근데 여기서 queue는 내가 지정한 변수명이다. 변수명만 딸랑 저렇게 while문에 있으니 어떻게 저게 큐가 빌 때까지 반복이란 뜻인건지 내 머리로는 도저히 이해가 안갔고 구글링을 통해 찾아봤다. 

 

https://docs.python.org/3/library/stdtypes.html#truth-value-testing

while 반복문의 원리를 생각해보자. while (조건문): 이렇게 코드가 있을 때, 우리는 조건 문이 참일 때 해당 로직을 무한히 반복한다는 사실을 알고 있다. 그런데 이게 조건문이 아닌 변수가 있을 때도 적용된다. 즉 위에서 queue 변수가 True일 때 무한히 반복하고, False 일 때 반복하지 않아야 한다. 그렇다면 변수인 queue가 어떻게 True 였다가 갑자기 False가 될 수 있는가?

 

위 사진을 참고하자. 파이썬 문법 설명에 의하면, 디폴트값으로 object는 True로 고려되어진다. 그런데 특정 경우에는 ㄹFalse로 고려되는데, 그 경우는 해당 object가 None이거나 내가 False로 지정해줬을 때이다. 즉 변수 안에 아무 것도 없으면 False로 고려된다는 거다. 그래서 while queue:  가 큐가 빌 때까지 반복이라는 뜻이 되는 것이다.