[그래프, BFS&DFS] 1260, 2606 문제 풀이

두 문제 다 DFS와 BFS, 그래프에 대한 개념 문제라고 생각한다.

 

1260 문제 풀이
그래프는 인접 리스트, 인접 행렬로 나누어짐
인접 리스트는 각 원소 별로 인접해 있는 주변 원소들을 각 원소와 연결시킨 리스트로 표현하는 것.
인접 행렬은 배열을 선언해 전체 배열 중 인접 원소들을 true 변환하는 것이라고 볼 수 있음.
인접 행렬로 문제를 푼 결과는 해당 페이지에서 확인 가능하다.

github.com/saturdayAlgo/acmicpc/blob/master/sw/java/p01260/array/Main.java

saturdayAlgo/acmicpc

인접 리스트로 문제를 푼 결과는 다음 해당 페이지에서 확인 가능하다.

github.com/saturdayAlgo/acmicpc/blob/master/sw/java/p01260/list/Main.java

saturdayAlgo/acmicpc

풀이 과정에서 인접 행렬은 문제 없는데 인접 리스트는 정렬을 자동으로 하기 위해 PriorityQueue를 사용해서 구현했고
HashMap을 사용해 Key-Value 형태로 구성해, Key에는 각 원소, Value에는 각 원소들과 밀접한 관계로 구성되어 있는 PriorityQueue를 구성했다.
BFS와 DFS는 Breadth First Search, Depth First Search의 약어로 각각 너비 우선 탐색, 깊이 우선 탐색이다.
BFS는 해당 노드에서 level 별로 각 자식 원소 전체를 먼저 검색하는 과정을 거치며, DFS는 해당 노드의 자식 노드를 level과 관계 없이 leaf node를 먼저 찾는 과정을 거친다.
BFS와 DFS에 대한 문제 풀이 과정을 살펴보자면,
BFS는 queue를 사용하는 방법이 가장 간편(?)한 방법이라고 할 수 있고, Java에서는 Queue가 구현체가 없는 interface로 구성되어 있기 때문에 Queue를 상속받아 만들어진 LinkedList를 사용해서 문제를 해결했다.
DFS는 가장 값의 크기가 작은 원소부터 수행해야 하기 때문에 DFS를 재귀호출하는 형태로 구현했다.

 

2606
BFS로 구현.
인접 행렬을 사용해 구현했고 queue에 데이터를 추가할 때의 조건은 방문하지 않고, 행렬 원소의 값이 true일 경우 queue에 데이터가 추가되도록 구현했다.

소스 코드는 깃헙 해당 페이지를 참고하면 된다.

https://github.com/saturdayAlgo/acmicpc/blob/master/sw/java/p02606/Main.java

saturdayAlgo/acmicpc