[깊이/너비우선탐색] 백준 1260번 DFS와 BFS - JAVA

 

아직도 DFS / BFS 헷갈리는 나

주말을 맞이하여 기초문제를 풀고 왔다!

 

 

---

1. 문제출처

---

 

1260번: DFS와 BFS

 

 

 

 

---

2. 설계

---

 

1) DFS

DFS는 시스템 스택을 쌓아가며 깊이 우선으로 노드를 방문해 출력하는 형식이다.

위 링크의 1번 예제를 함께보자

 

4 5 1
1 2
1 3
1 4
2 4
3 4

만약 1번부터 시작한다면 1번 인접 노드는 2,3,4이고, 이 중 작은 것 먼저 선택을 한다.

다음은 2번노드가 시작되고, 2번 인접 노드는 1,4인데, 1번은 이미 방문했으므로 4번을 선택한다.

4번의 인접노드는 1,3인데, 1번은 이미 방문했으므로 3번을 선택한다.

=> 1 2 4 3

 

2) BFS

BFS는 Queue를 이용해 출력할 순서를 정해주는 것이다.

시작 노드의 인접한 형제들을 먼저 큐에 넣음으로써 뒤에 오는 다른 형제의 자식들보다 먼저 출력할 수 있게 해준다.

위 링크의 1번 예제를 함께보자

4 5 1
1 2
1 3
1 4
2 4
3 4

만약 1번부터 시작한다면 1번 인접 노드는 2,3,4인데, 이들을 방문한 적이 없다면 모두 큐에 넣어준다.

그 후 가장 작은 숫자인 2번 부터 시작해 2번의 방문안한 자식들은 모두 큐에 넣어준다.

다음은 3번의 방문안한 자식들을 모두 큐에 넣어주고, 4번의 방문안한 자식들도 모두 큐에 넣어준다.

그 후 순차적으로 출력한다.

=> 1 2 3 4

 

 

 

 

---

3. 전체 코드

---

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N,M,V;
	static List<Node>[] nodeList;
	static boolean[] visited;
	static class Node implements Comparable<Node> {
		int num;

		public Node(int num) {
			super();
			this.num = num;
		}

		@Override
		public int compareTo(Node o) {
			return this.num>o.num?1:-1;
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();//정점의 개수
		M = sc.nextInt();//간선의 개수
		V = sc.nextInt();//탐색 시작 번호
		
		//초기화
		nodeList = new ArrayList[N+1];//정점은 1부터 시작
		for(int i=0;i<N+1;i++) {
			nodeList[i]=new ArrayList<>();
		}
		visited = new boolean[N+1];
		//간선 정보 입력받기 (양방향)
		for(int i=0;i<M;i++) {
			int startNode = sc.nextInt();
			int endNode = sc.nextInt();
			nodeList[startNode].add(new Node(endNode));
			nodeList[endNode].add(new Node(startNode));
		}
		//정렬
		for(int i=0;i<N+1;i++) {
			nodeList[i].sort(Comparator.naturalOrder());
		}
		//입력 끝
		visited[V]=true;
		DFS(V);
		System.out.println();
		BFS(V);
		
	}

	//시스템 스택을 쌓는다.
	public static void DFS(int start) {
		System.out.printf(start+" ");
		for(int i=0;i<nodeList[start].size();i++) {
			int next = nodeList[start].get(i).num;
			if(visited[next]) continue;
			visited[next]=true;
			DFS(next);
		}
		
	}
	
	public static void BFS(int start) {
		Queue<Integer> q = new LinkedList<>();
		boolean[] visited = new boolean[N+1];
		
		q.add(start);
		visited[start]=true;
		
		while(!q.isEmpty()) {
			int curr = q.poll();
			System.out.printf(curr+" ");
			
			for(int i=0;i<nodeList[curr].size();i++) {
				int next = nodeList[curr].get(i).num;
				if(visited[next]) continue;
				visited[next]=true;
				q.add(next);
			}
		}
	}
}

 

1) 새로 배운 점

ArrayList에 달린 요소들을 정렬하기 위해서 Comparator을 사용한다.

//정렬
for(int i=0;i<N+1;i++) {
	nodeList[i].sort(Comparator.naturalOrder());
}

 

주의할 점은 class를 넣는 ArrayList의 경우 클래스에 Comparable 설정을 꼭 해줘야 한다.

static class Node implements Comparable<Node> {
		int num;

		public Node(int num) {
			super();
			this.num = num;
		}

		@Override
		public int compareTo(Node o) {
			return this.num>o.num?1:-1;
		}
		
}

 

---

끝 - !