[백준] 11724번 : 연결 요소의 개수

문제

 

 

접근 방식

끊기지 않고 연결된 묶음이 몇 개인지 찾는 문제로 BFS와 DFS 둘 중 아무거나 사용해서

풀 수도 있고, 인접 행렬이나 인접 리스트 중 아무거나 사용해도 상관없기에

BFS를 사용해서 인접 행렬과 인접 리스트 둘 다 사용해 풀어봤다.

 

문제에서 주어진 그래프는 무방향 그래프이기 때문에

인접 행렬이나 리스트를 만들 때 (x, y)와 (y, x) 모두 추가해줘야 한다.

 

인접 행렬의 경우에는 0과 1로 구분해서 간선이 존재하는 경우를 1로 표현해주면 되고

인접 리스트의 경우에는 해당 정점에서 이동할 수 있는 정점을 추가해주면 된다.

 

풀이

 

인접 행렬을 사용한 풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int count = 0;

		int[][] nearArr = new int[n + 1][n + 1];
		boolean[] isVisited = new boolean[n + 1];

		Queue<Integer> q = new ArrayDeque<>();

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			nearArr[x][y] = 1;
			nearArr[y][x] = 1;
		}

		for (int i = 1; i <= n; i++) {
			if (isVisited[i]) continue;
			count++;
			q.offer(i);
			isVisited[i] = true;

			while (!q.isEmpty()) {
				int cur = q.poll();

				for (int j = 0; j <= n; j++) {
					if (nearArr[cur][j] != 1 || isVisited[j]) continue;
					q.offer(j);
					isVisited[j] = true;
				}
			}
		}

		System.out.println(count);
	}
}

 

인접 리스트를 사용한 풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int count = 0;

		ArrayList<ArrayList<Integer>> nearList = new ArrayList<>();
		boolean[] isVisited = new boolean[n + 1];

		Queue<Integer> q = new ArrayDeque<>();

		for (int i = 0; i <= n; i++) {
			nearList.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			nearList.get(x).add(y);
			nearList.get(y).add(x);
		}

		for (int i = 1; i <= n; i++) {
			if (isVisited[i]) continue;
			count++;
			q.offer(i);
			isVisited[i] = true;

			while (!q.isEmpty()) {
				int cur = q.poll();

				for (int near : nearList.get(cur)) {
					if (isVisited[near]) continue;
					q.offer(near);
					isVisited[near] = true;
				}
			}
		}

		System.out.println(count);
	}
}