BAEKJOON_1260) DFS와 BFS

BAEKJOON 

# 알고리즘 기초 # 2019 SW역량테스트준비-기초

# 그래프 # 그래프와 BFS # 그래프의 탐색

1260) DFS와 BFS (19.04.04) (19.09.24)

* 문제에서 ArrayList와 LinkedList 를 처음 사용했다.

* 먼저, 간선들을 나타내기 위해 ArrayList 배열을 사용해 인접리스트를 만들었다.
* list[1]은 정점 1의 간선, list[2] 는 정점 2의 간선... 으로 해서 입력받은 간선의 개수 m 개 만큼 돌렸다.
* add()를 사용해 간선 하나의 양 점 모두에 다른 점을 저장해주었다.
* 그리고 방문할 수 있는 정점이 여러 개인 경우 작은 번호부터 먼저 반복해야 하므로,
* 우선적으로 각 정점에 연결된 번호들을 Coolections.sort() 로 정렬해주었다.

* check와 checkb 배열을 만들어 각 점이 이미 지나온 곳인지 아닌지를 확인했다.

* DFS에서는 시작점에 연결된 점들을 작은 수부터 검사하면서 다음 점을 찾아
* 시작점을 계속 변경해주었고, 더이상 갈 수 없다면 이전 정점으로 돌아와야 했다.
* 여기서 재귀함수를 사용했다.

* BFS는 LinkedList의 offer() 함수로 시작점을 넣어주고,
* 그리고 queue가 빌 때까지 poll() 함수로 다음 시작점을 계속 뽑아냈다.
* 시작점이 정해지면 거기에 연결된 모든 다른 점들을 검사하고, 아직 방문하지 않은 점을
* add()로 저장하고, 다음 시작점을 찾았다.

* list 의 크기를 정점의 개수 n 이 아닌, n+3으로 한 것은,
* 우선 1부터 n 까지 이기 때문에, 그리고 dfs와 bfs에서 각각 하나씩 사용하기 위해서다.

* dfs, bfs 함수를 돌고 나서는 인덱스를 이용해 get() 함수로 출력해주었다.



* 여기서 처음 ArrayList 배열을 정의하는 부분을 다르게 바꿔봤더니 시간이 확 줄었다.

* 이번 문제는 재귀함수와 ArrayList, LinkedList 를 사용하면서 조금 어렵긴 해도 새로운 문제였다.
* 이어서 그래프 챕터에서 풀게 될 문제들에서 익숙하도록 연습을 많이 해야겠다.



* 4달 전에 풀었을때 생각해보면 비교적 수월하게 풀었다.
* 최근에 ArrayList도 꽤 자주 써서 익숙했고, queue 부분만 문법을 찾아봤다.
* Buffer 랑 Scanner 차이인지 시간이 지난번꺼랑은 꽤 많이 차이가 났다. 왜그렇지?