728x90
320x100
https://www.acmicpc.net/problem/11724
📌 접근 방식
1️⃣ 접근 방식
- 그래프의 표현
- 입력된 정점과 간선 정보는 인접 리스트를 사용하여 그래프 표현
- 인접 리스트 : 정점마다 연결된 다른 정점들의 목록을 저장하는 구조로, 메모리 사용량이 적고 효율적인 탐색이 가능함
- ex) 간선 정보가 (1, 2)와 (2, 3)이라면 인접 리스트는
1: [2]
2: [1, 3]
3: [2]
- 방문 배열 사용
- 그래프 탐색 과정에서 방문한 노드를 다시 방문하지 않기 위해 방문 배열(visited) 사용
- visited[i]가 True라면, 정점 i는 이미 방문한 상태를 의미
- DFS 탐색
- 방문하지 않은 정점을 시작으로 DFS를 호출하여, 해당 정점과 연결된 모든 정점을 탐색
- DFS가 끝나면 하나의 연결 요소 탐색이 완료된 것이므로, 연결 요소의 개수를 1 증가시킨다.
2️⃣ 알고리즘의 흐름
- 그래프와 방문 배열 초기화
- 입력으로 주어진 정점과 간선 정보를 기반으로 인접 리스트 생성
- 방문 배열을 False로 초기화
- DFS 탐색 및 연결 요소 개수 증가
- 정점 1부터 N까지 반복하며, 아직 방문하지 않은 정점을 찾음
- 방문하지 않은 정점에서 DFS를 호출하고, 해당 DFS 호출이 끝나면 연결 요소 개수를 증가 시킴
- 결과 출력
- 연결 요소의 개수 출력
✅ PASS CODE
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer> []arr;
static boolean[] visited;
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());
st = new StringTokenizer(br.readLine());
arr = new ArrayList[N+1];
visited = new boolean[N+1];
for (int i = 1; i <= N; i++) {
arr[i] = new ArrayList<>();
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
arr[u].add(v);
arr[v].add(u);
}
int count = 0;
for(int i = 1; i <= N; i++) {
if(!visited[i]) {
count ++;
DFS(i);
}
}
System.out.println(count);
}
public static void DFS(int v) {
if(visited[v]) return;
visited[v] = true;
for(int i : arr[v]) {
DFS(i);
}
}
}
🌟 느낀점
DFS는 그래프 탐색 문제에서 정말 유용한 도구라는 걸 다시 한번 느꼈다. 노드를 한 번 방문하면 재방문하지 않게 방문 배열로 체크하고, 연결된 노드를 쭉 탐색해 나가는 방식이 너무 깔끔하고 간단하다고 느껴졌다.
처음엔 이해가 잘 안가서 직접 손으로 따라 그려보며 머릿속으로 이해해보았다. 그리고 그래프를 인접 리스트로 표현했는데, 메모리도 아끼고 탐색도 빨라서 큰 도움이 됐고, 머릿속으로 이해한 그래프와 잘 연결되는 것 같아서 금방 풀 수 있었다! DFS를 구현할 때는 인접 리스트를 사용한다는 것.. 메모 🗒️
728x90
반응형
'Baekjoon' 카테고리의 다른 글
[JAVA][Baekjoon] 13023번 ABCDE 🌟🌟 (2) | 2025.01.05 |
---|---|
[JAVA][Baekjoon] 2023번 신기한 소수 (0) | 2025.01.04 |
[JAVA][Baekjoon] 10989번 수 정렬하기 3 🌟🌟🌟🌟🌟 (2) | 2025.01.03 |
[JAVA][Baekjoon] 1517번 버블 소트 🌟🌟🌟 (0) | 2025.01.03 |
[JAVA][Baekjoon] 2751번 수 정렬하기 2 🌟🌟🌟 (0) | 2025.01.03 |