01-09 18:44
Recent Posts
Recent Comments
๊ด€๋ฆฌ ๋ฉ”๋‰ด

miinsun

[BAEKJOON] ๋ฐฑ์ค€ ๊ทธ๋ž˜ํ”„ 11724 :: ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜ ๋ณธ๋ฌธ

Algorithm/Baekjoon

[BAEKJOON] ๋ฐฑ์ค€ ๊ทธ๋ž˜ํ”„ 11724 :: ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜

miinsun 2022. 3. 29. 23:23

 

๐Ÿ’ฌ  ๋ฌธ์ œ ์„ค๋ช…

๋ฐฉํ–ฅ ์—†๋Š” ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์—ฐ๊ฒฐ ์š”์†Œ (Connected Component)์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

 

๐Ÿ”จ  ์ž…์ถœ๋ ฅ ์˜ˆ

์ž…๋ ฅ 

  • ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N๊ณผ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
  • ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์— ๊ฐ„์„ ์˜ ์–‘ ๋์  u์™€ v๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ u, v ≤ N, u ≠ v)
  • ๊ฐ™์€ ๊ฐ„์„ ์€ ํ•œ ๋ฒˆ๋งŒ ์ฃผ์–ด์ง„๋‹ค.

 

์ถœ๋ ฅ

  • ์ฒซ์งธ ์ค„์— ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

 

์˜ˆ์ œ ์ž…๋ ฅ 1)

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

 

์˜ˆ์ œ ์ถœ๋ ฅ 1)

2

 

์˜ˆ์ œ ์ž…๋ ฅ 2)

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

 

์˜ˆ์ œ ์ถœ๋ ฅ 2)

1

โ€‹

 

โ€‹

๐Ÿ’ป  Main.java

  • ์ด์ „ ๊ฒŒ์‹œ๊ธ€ 'DFS์™€ BFS' ๋ฌธ์ œ๋ฅผ ๋ฒ ์ด์Šค๋กœ ํ•ด๊ฒฐ
  • check๋ฐฐ์—ด์— ์ด๋ฒˆ ๋ฐฉ๋ฌธ์ด ๋ช‡๋ฒˆ์งธ ๋ฐฉ๋ฌธ์ธ์ง€ ์นด์šดํŒ…ํ•ด์ค€๋‹ค.
  • ์—ฐ๊ฒฐ ์š”์†Œ๋Š” ์•„๋ž˜์™€ ๊ฐ™์€ ์ด๋ฏธ์ง€๋‹ค.
์ถœ์ฒ˜: velog.io/@polynomeer
/* ๋ฐฑ์ค€ ๊ทธ๋ž˜ํ”„ - 11724 :: ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜ */
import java.util.*;
import java.io.*;

public class Main {
	public void DFS(int n, int s, boolean[][] arr, int[] check, int order) {
		//์ฒดํฌ๊ฐ€ ์•ˆ๋˜์žˆ์„ ๊ฒฝ์šฐ์—๋งŒ order๋ฅผ ๋‹ด์•„์ค€๋‹ค.
		if(check[s] == 0)
			check[s] = order;

		for(int i = 1; i <= n; i++) {
			if (check[i] == 0) {
				if(arr[s][i]) {
					DFS(n, i, arr, check, order);
				}
			}
		}
	}

	public static void main(String[] args) throws IOException{
		Main main = new Main();
		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());

		boolean[][] arr = new boolean [n + 1][n + 1];
		int[] check = new int [n + 1];

		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			// ๋ฐฉํ–ฅ ์—†๋Š” ๊ทธ๋ž˜ํ”„๋Š” 
			// (x,y) (y,x) ์ขŒํ‘œ๋ฅผ ๋ชจ๋‘ ์ €์žฅํ•ด์ค€๋‹ค.
			arr[x][y] = true;
			arr[y][x] = true;
		}
		
		// DFS
		int order = 1;
		for(int i = 1; i <= n; i++) {
			// ๋ฐฉ๋ฌธํ•œ ์ ์ด ์—†์„ ๊ฒฝ์šฐ์—๋งŒ
			// ์ •์ ์„ ๋ฐฉ๋ฌธํ•œ๋‹ค.
			if(check[i] == 0) {
				main.DFS(n, i, arr, check, order);
				order++;
			}
		}
		
		// check๋ฐฐ์—ด์—์„œ ๊ฐ€์žฅ ํฐ ๊ฐ’์ด ์—ฐ๊ฒฐ์š”์†Œ์˜ ๊ฐ’์ด๋‹ค.
		int answer = 0;
		for(int i : check)
			answer = Math.max(i, answer);
		
		System.out.println(answer);
        br.close();
	}
}
Comments