[BOJ - JAVA] 11724 - 연결 요소의 개수 (BFS)

# 주소

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

11724번: 연결 요소의 개수

# 문제

# 문제 해설 및 코드 리뷰

import java.util.LinkedList;
import java.util.Scanner;
public class Main{
	static int[][] arr;
	static int n;
	static boolean[] visit;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		int m = scan.nextInt();
		arr = new int[n+1][n+1];
		visit = new boolean[n+1];
		for(int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			arr[a][b] = arr[b][a] = 1;
		}
		int count = 0;
		for(int i = 1; i <= n; i++) {
			if(!visit[i]) {
				bfs(i);
				count++;
			}
		}
		System.out.println(count);
	}
	public static void bfs(int t) {
		LinkedList<Integer> list = new LinkedList<>();
		list.offer(t);
		visit[t] = true;
		while(!list.isEmpty()) {
			int now = list.poll();
			for(int i = 1; i <= n; i++) {
				if(!visit[i] && arr[now][i] == 1) {
					visit[i] = true;
					list.offer(i);
				}
			}
		}
	}
}

오랜만에 다시 BFS문제를 가져왔습니다. 

BFS문제는 대체로 평이한 것 같습니다.

너비의 영역의 개수를 구한다던지, 아님 방문하지 않을 노드의 개수를 구한다던지, dx,dy를 static하게 선언하여 백트래킹기법을 써서 체스처럼 움직이며넛 배열을 움직인다던지 등등...

간단한 문제같은 경우는 bfs로 풀되 n개수가 많아질수록 dfs가 유리하다고 하더라고요. 이번엔 bfs로 풀었습니다.

아무래도 Queue를 다루는게 참 재미있기도 하고 (dfs는 스택이라서 너무 따분함) 동적인 상태로 문제를 푸는게 재밌습니다.. 

어쨌든 풀이를 해보도록 할게요

제일 먼저 int타입의 arr와 boolean타입의 visit을 선언합니다.

모든 bfs문제에서 그렇듯, 이 둘을 선언하지 않는 문제는 아마 거의 없을 것입니다.

그리고 입력받는 각각의 arr위치에 1을 저장합니다. (2차원이기 떄문에 인덱스 바꿔도 1넣어야함)

그리고 방문하지 않은 visit값에 대하여 bfs를 실행할 것입니다. 그리고 bfs가 실행될 때마다 1씩 증가시킵니다.

bfs문으로 들어갔습니다.

LinkedList<Integer>타입의 list를 선언합니다.

제일 먼저 이 list에 for문에 있던 i값(여기선 t로 받음)을 삽입하고 visit[t] = true로 바꾸어 줍니다.

그럼 다시는 이 인덱스에 대해 방문할 일은 없습니다.

while문으로 들어가서 (모든 bfs문제는 !queue.isEmpty()) <--- 꼭 들어가있음) list.poll()을 now에 저장합니다.

이후 for문으로 들어가, visit[i] = false이고 arr[now][i] = 1인 값(방문하지 않았고 노드가 연결되어있는) 해당 인덱스를 true로 바꾸고 그 때마다 list에 i를 넣습니다.

이렇게 되면 제일 처음 인덱스에 넣었던 int t의 주변 인덱스(연결된)에 모두 들어가서 연결이 됩니다.

근데 만약 연결이 되어 있지 않다면 while문을 빠져나올테고 자연스럽게 bfs문을 재실행할 것입니다.

이해가셨나요??

문제에서 나오는 연결 요소라는 개념이 전 처음엔 헷갈렸었습니다. (학부생 때 분명 배웠습니다만..)

이제야 확실히 알았습니다. 연결되어있는 노선들! 이렇게 생각하면 되겠습니다.

그러므로 bfs 또는 dfs가 실행될 때마다 계속해서 count를 증가시켜 답이 될 수 있겠습니다.

감사합니다.