[Java] 백준 1260번 <DFS와 BFS>

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

백준 1260번 <DFS와 BFS>

문제  설명

이 문제는 DFS와 BFS를 가볍게 실습할 수 있는 문제이다. 

---

코드 구현하는 과정

---

1. 필요 필드 구현

static boolean visited[]; // 방문 확인 배열
static ArrayList<Integer>[] a; // 인접 숫자 리스트

각각의 노드에 방문했었는지 확인할 boolean타입의 배열과

각 노드의 인접 노드를 저장할 ArrayList를 만든다. 

 

---

2. main 메소드 구현

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
		
	int N = sc.nextInt(); // 정점의 개수
	int M = sc.nextInt(); // 간선의 개수
	int V = 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 x = sc.nextInt();
		int y = sc.nextInt();
		a[x].add(y);
		a[y].add(x);
	}
		
	// 번호가 작은 것을 먼저 방문하기 위해 정렬
	for(int i = 1; i <= N; i++) {
		Collections.sort(a[i]);
	}
		
	// DFS 방문 배열 초기화하기
	visited = new boolean[N+1];
	dfs(V); 
	System.out.println();
	
	// BFS 방문 배열 초기화하기
	visited = new boolean[N+1];
	bfs(V);
	System.out.println();
}

 위 입력대로 간선을 연결해 리스트를 만들면 다음과 같다. 

a[1] => 2, 3, 4

a[2] => 1, 4

a[3] => 1, 4

a[4] => 1, 2, 3

 

이제 위 리스트로 DFS와 BFS 과정을 수행하면 이 문제는 해결된다. 

 

---

3. DFS (깊이우선탐색) 구현

// DFS 구현
public static void dfs(int num) {
	System.out.print(num + " ");
	visited[num] = true;
	for(int i : a[num]) {
		if(!visited[i]) {
			dfs(i); // 재귀함수
		}
	}
}

위 예시 입력에서 탐색을 시작할 정점의 번호로 1번을 지정했기 때문에

1번을 기준으로 예시 설명을 하자면 다음과 같다. 

 

1번 정점을 받아 dfs 메소드가 실행되면

1이 출력되고 방문을 확인하는 boolean배열의 '1'자리를 true로 바꾼다. 

 

그리고 다음으로 방문하지 않은 하나의 노드로 가게되는데 

main 메소드에서 리스트 배열을 오름차순으로 정렬했기 때문에

재귀함수를 통해 2번 노드로 가게된다. 

 

이 과정을 반복하면 하나씩 방문하게 되고 

결국엔 모두 방문하게되어 DFS과정이 끝나게 된다. 

 

---

4. BFS (너비우선탐색) 구현

// BFS 구현
public static void bfs(int num) {
	Queue<Integer> queue = new LinkedList<Integer>();
	queue.add(num);
	visited[num] = true;
		
	while(!queue.isEmpty()) {
		int nowNum = queue.poll();
		System.out.print(nowNum + " ");
		for(int i : a[nowNum]) {
			if(!visited[i]) {
				visited[i] = true;
				queue.add(i); 					
			}
		}
	}
}

이 역시 위 예시 입력에서 탐색을 시작할 정점의 번호로 1번을 지정했기 때문에

1번을 기준으로 예시 설명을 하자면 다음과 같다. 

 

1번 정점을 받아 bfs 메소드가 실행되면

노드를 차례차례 저장할 Queue구조를 만들고 1번 노드를 넣고, 

방문을 확인하는 boolean배열의 '1'자리를 true로 바꾼다. 

 

그리고 큐가 비어있지 않을 때까지 

빼고 인접노드를 넣는 작업을 반복한다. 

 

---

 

---

코드 실행

---

위 코드를 조합하여 프로그램을 만들어 실행하면 

다음과 같은 결과가 출력된다. 

 

위 입력은 아까 예시로 설명한 정점과 간선을 그대로 입력한 것이다. 

출력된 첫번째 줄은 DFS 실행결과, 

출력된 두번째 줄은 BFS 실행결과이다.