https://www.acmicpc.net/problem/11724
문제
풀이
import java.io.*;
import java.util.*;
public class Main {
static boolean check[];
static int arr[][];
static int edge, node;
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
edge = Integer.parseInt(st.nextToken());
node = Integer.parseInt(st.nextToken());
arr = new int[edge+1][edge+1];
check = new boolean[edge + 1];
for (int i = 0; i < node; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y] = arr[y][x] = 1;
}
for(int i = 1; i <= edge; i++){
if(check[i] == false) { // 방문한 적 없는 노드라면 dfs.
dfs(i);
count++;
}
}
System.out.println(count);
}
public static void dfs(int start) {
check[start] = true;
for(int i = 0 ; i <= edge; i++) {
if(arr[start][i] == 1 && !check[i]) {
dfs(i);
}
}
}
}
연결된 노드를 먼저 인접행렬로 표현한 뒤에 방문한 적이 없는 노드를 기준으로 dfs를 사용하는 것이다.
재귀적인 개념이 들어가 있기 때문에 처음 사용해 봐서 어려움이 있었지만 조금 힘들더라도 한 줄씩 직접 숫자를 넣어가며 찾아가는 과정을 통해 이해할 수 있었다.
'문제 풀이 > 백준' 카테고리의 다른 글
[백준] 2667번. 단지 번호 붙이기(JAVA) (0) | 2024.02.12 |
---|---|
[백준] 2178번. 미로 탐색(JAVA) (0) | 2024.02.12 |
[백준] 2331번. 반복수열 (JAVA) (0) | 2024.02.11 |
[백준] 13560번. 축구 게임(JAVA) (1) | 2024.02.09 |
[백준] 2075번. N번째 큰 수 (JAVA) (0) | 2024.02.08 |