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

 

11724번: 연결 요소의 개수

 

 

package 백준renew;

import java.io.*;
import java.util.*;

public class 실버2_11724_연결요소의개수 {
	static int computers, lines;
	static int map[][];
	static boolean visited[];
	static int cnt;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		computers = Integer.parseInt(st.nextToken());
		lines = Integer.parseInt(st.nextToken());
		
		map = new int[computers][computers];
		visited = new boolean[computers];
		
		for(int i=0; i<lines; i++) {
			st = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			map[num1 -1][num2 -1] = 1;
			map[num2 -1][num1 -1] = 1;
		}
		
		for(int i=0; i<computers; i++) {
			if(!visited[i]) {
				DFS(i);
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}
	static void DFS(int i) {
		visited[i] = true;
		
		for(int j=0; j<computers; j++) {
			if(!visited[j] && map[i][j] == 1) {
				DFS(j);
			}
		}
	}
}

 

 

이전에 풀었던 문제들과 비슷한 문제.

이전꺼 잘 풀어놓고 또 헷갈렸다 .. 다시 리마인드.

 

연결요소의 개념에 대해 이해가 안되어서 조금 고민했는데,

연결요소는 정점의 개수를 말하는 거였다. ex) 컴퓨터의 개수 

간선은 컴퓨터에 연결되어있는 네트워크의 개수라고 이해하니 편-안

 

앞으로 연결요소와 간선의 문제가 나오면,

    1) 2차원 배열을 컴퓨터의 개수만큼 만들어서

    2) 연결되어 있는 경우 [1번컴퓨터][2번컴퓨터] = 1 로 표시해준 뒤,

    3) 컴퓨터 방문처리할 1차원 배열을 만들어서

    4) 컴퓨터 개수 만큼 반복문을 돌면서, 방문하지 않은 컴퓨터에 대해 DFS 탐색.

         DFS에 전해줄 땐, 내가 지금 방문한 컴퓨터의 번호를 변수로 넘겨줘야 함.

    5) DFS 안에서 방문체크 해준 다음,

    6) 다른 컴퓨터와 연결되어 있는지 확인해야하니까 컴퓨터의 수 만큼 또 반복문을 돌면서

    7) 해당 컴퓨터에 방문을 하지 않았고, 해당 컴퓨터와 연결되어 있으면

    8) 재귀로 DFS에 연결된 컴퓨터의 번호를 변수로 넘겨준다!

로 풀어볼 생각이다 .. 다시 한번 리마인드 할 수 있어서 감사한 하루 🍀

 

 

<비슷한 유형이라고 생각하는 문제들>

[Baekjoon] 2606: 바이러스(실버3)

 

[Programmers] Lv.3 네트워크 (DFS/BFS)