728x90
반응형
위 문제는 DFS풀이의 가장 기본적인 문제이다.
문제를 풀기에 앞서 풀이 순서를 짚어보자.
1. 최대 정점의 개수와 문제풀이 시간을 대조해본다.
- 문제 풀이 시간은 3초이다. 최대 노드의 개수는 1000개로 n^2의 복잡도로 문제를 풀어도 충분히 시간이 남는다.
2. 해당 그래프를 직접 그려본다.
- 첫 예시의 그래프를 만들어보자면 다음과 같다. (혼을 담아 정성스럽게 그려보았다)
3. 이처럼 두개의 그래프가 그려지는것을 확인할 수 있다. 이를 코드로 작성하기 위한 슈도코드를 작성해본다.
n(노드 개수) , m(엣지 개수)
A(그래프 데이터 저장 인접 리스트)
visited(방문 기록 저장 배열)
for(n만큼 반복
{A 인접 리스트의 각 ArrayList초기화}
for(m의 개수만큼 반복하기)
{ A인접 리스트에 그래프 데이터 저장하기 }
for(n의 개수만큼 반복하기)
{ if(방문하지 않은 노드가 있으면){ 연결 요소 개수 ++ DFS 실행하기 }
//DFS구현하기
{
DFS{ if(현재 노드 == 방문노드) return;
visited 배열에 현재 노드 방문 기록하기
현재 노드의 연결 노드 중 방문하지 않는 노드로 DFS 실행하기(재귀 함수 형태)
}
4.이를 토대로 재귀함수를 사용한 스택형식의 DFS를 구현한다.
public class test {
//방문 배열
static boolean[] visited;
//인접 리스트
static ArrayList<Integer>[] A;
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());
visited = new boolean[n+1];
A = new ArrayList[n + 1];
for (int i = 1; i < n + 1; i++) {
//인접리스트배열 초기화
A[i] = new ArrayList<Integer>();
}
//인접 리스트에 그래프 데이터 저장
for (int i=0; i<m; i++){
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
A[s].add(e);
A[e].add(s);
}
//개수를 판단할 count변수
int count =0;
//방문배열에 등록되지 않은 노드를 재귀함수를 통해 찾아냄
for (int i = 1; i <n+1; i++) {
if(!visited[i]) {
count++;
DFS(i);
}
}
System.out.println(count);
}
private static void DFS(int v) {
if(visited[v]){
return;
}
visited[v] = true;
for (int i : A[v]) {
if (!visited[i]) {
DFS(i);
}
}
}
}
728x90
반응형
'문제 풀이 > 백준 문제풀이' 카테고리의 다른 글
[백준 - 2178/ 자바(Java)] 미로 탐색 문제 BFS로 해결하기 (1) | 2024.02.28 |
---|---|
[백준 -24480 ] java , 알고리즘 수업 - 깊이 우선 탐색 2 (2) | 2024.02.26 |
숫자만 추출하기 (1) | 2023.12.10 |
팰린드롬(회문 문자열) (0) | 2023.12.10 |
회문문자열 (0) | 2023.12.10 |