[BOJ] 11724. 연결 요소의 개수

BaekJoon 11724. 연결 요소의 개수

* 문제의 저작권은 BOJ 및 문제를 만든 사람에게 있습니다.

 

 

 

 

 

[문제 접근]

DFS와 BFS로 모두 풀 수 있는 문제 같은데 나는 BFS를 이용해서 풀었다.

연결되어 있는 간선들을 표시할 connect라는 2차원 배열을 하나 만들고 1로 표시해줬다.

그리고 해당 정점들의 방문 여부를 확인 할 수 있는 visit라는 1차원 배열을 만들어줌

 

해당 정점을 방문하지 않았으면 해당 정점과 y좌표 값이 1일 때의 y좌표 값을 큐에 넣어준다.

큐에 있는 값을 확인 했을 때 방문하지 않았으면 위에 방법과 동일하게 검사하고 큐에 넣어주고 방문 표시를 해준다.

그리고 while문이 끝나면 연결 요소의 개수를 세는 cnt를 ++한다.

 

처음에 실수로 cnt를 if문이 끝나고 넣었다.

이렇게 넣으면 결국 연결 요소의 여부와 상관없이 모든 정점의 개수를 세는 것이기 때문에 while문을 끝나고 넣어줘야 함 ! ! !

 

 

 

 

 

 

 

[코드]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main_11724 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); //정점의 개수
		int M = sc.nextInt(); //간선의 개수
		int[][] connect = new int[N+1][N+1];
		boolean[] visit = new boolean[N+1];

		for (int i = 0; i < M; i++) {
			int tempx = sc.nextInt();
			int tempy = sc.nextInt();
			connect[tempx][tempy] = 1;
			connect[tempy][tempx] = 1;
		}

		int cnt = 0;
		Queue<Cord> queue = new LinkedList<>();

		for (int i = 1; i <= N; i++) {
			if (!visit[i]) {
				visit[i] = true;
				for (int j = i; j <= N; j++) {
					if (connect[i][j] == 1) {
						queue.add(new Cord(j));
					}
				}
				while (!queue.isEmpty()) {
					Cord temp = queue.poll();
					int tempx = temp.x;

					if (!visit[tempx]) {
						for (int j = 1; j <= N; j++) {
							if (connect[tempx][j] == 1) {
								queue.add(new Cord(j));
								visit[tempx] = true;
							}
						}
					}
				}
				cnt++;
			}
		}

		System.out.println(cnt);


	}
	static class Cord{
		int x;

		public Cord(int x) {
			this.x = x;
		}
	}
}