https://www.acmicpc.net/problem/1260
1. 문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
2. 입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
3. 출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
4. 코드
import java.util.*;
public class Num1260 {
static boolean visited[];
static ArrayList<Integer>A[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int Start = sc.nextInt();
A = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
A[i] = new ArrayList<Integer>();
}
for (int i = 0; i < M; i++) {
int S = sc.nextInt();
int E = sc.nextInt();
A[S].add(E);
A[E].add(S);
}
for (int i = 1; i < M; i++) {
Collections.sort(A[i]);
}
visited = new boolean[N + 1];
DFS(Start);
System.out.println();
visited = new boolean[N + 1];
BFS(Start);
System.out.println();
}
private static void BFS(int Node) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(Node);
visited[Node] = true;
while (!queue.isEmpty()){
int now_Node = queue.poll();
System.out.print(now_Node + " ");
for(int i: A[now_Node]){
if(!visited[i]){
visited[i] = true;
queue.add(i);
}
}
}
}
private static void DFS(int Node) { // DFS 노드로 도착
System.out.print(Node + " ");
visited[Node] = true; // 이미 도착한 탐색노드 이기에 탐색노드로 변경해줌
for(int i: A[Node]){ // 앞서 말한 노드에서 갈수 있는 노드를 인접리스트에서 탐색해줌
if(!visited[i]){ // 이미 방문한 노드는 제외
DFS(i); // 방문하지 않은 노드만 재귀함수로 가준다.
}
}
}
}
5. 학습한 내용
코딩테스트에 자주 출몰하는 BFS(너비우선) 과 DFS(깊이우선)을 이코테 강의를 활용해서 학습하고 문제를 풀어보았다.
먼저, 앞서 포스팅한 대로 DFS와 BFS의 특징과 풀이방법을 따라쳐보면서 감을 가져보는 시간이었고 무엇보다도 손코딩처럼 바로 코드를 짜는것이 아닌 어떠한 방식으로 코드를 짤지 밑그림을 그리는것에 대한 중요성을 깨달았다.
구체적으로는
-
DFS는 Stack과 재귀함수를 사용하여 문제풀어나가야 한다는 점과 BFS는 큐를 사용하여 문제를 풀어나가야 한다는 점을 깨달았다.
해당 과정에 대해서는 그림을 그려가면서 차이점을 학습할 수 있었다. -
" 노드를 기준으로 " → 인접리스트 사용
" 에지를 기준으로 " → MST, 벨만포드 → 에지리스트 -
for 문
해당 문제에서 풀이과정 중for(int i: A[Node])
의 코드를 이해하는데 어려움이 있었다. 그래서 추가적인 학습을 통해서 for문이 어떠한 방식으로 돌아가는지를 정리하게되었다.
해당 코드를 설명하자면,
A는 배열이나 컬렉션을 의미하며 Node는 변수이다.
즉, int i 가 Node의 각 요소를 순회하면서 i 라는 변수에 할당된다.
해당 코드는 우리가 주로 사용하는
for (int i = 0; i < A[Node].length; i++) {
int element = A[Node][i];
}
와 동일한 원리로 동작한다.
