백준 11724번 자바

문제

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

1. DFS? 그래프? 노드? 간선?

이 문제를 풀기위해선 먼저 DFS알고리즘의 개념과 노드,간선의 개념들에 대한 이해가 선행되어야 한다. 

- 그래프 : 노드(Node)와 그것을 연결하는 간선(Edge)으로 원소간의 관계를 표현한 자료구조이다.

• 정점(Vertex) : 노드, 정점엔 데이터가 저장된다.
• 간선(Edge) : 정점과 정점을 연결하는 선
• 인접 정점(Adjacent Vertex) : 간선이 연결된 정점
• 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

- 그래프 구현 방식

구분	장점	단점	비고
인접행렬	- 간선정보 확인이 빠름 - 간선 추가,제거가 빠름	- 배열의 크기가 항상 N*N이다.   (N은 정점의 개수, 메모리낭비) - 특정 노드에 인접한 노드를 찾기위해    모든 노드를 순회 - 노드 추가,제거 오래걸림 - 모든 간선 수를 찾는데 오래걸림	비교적 노드수가 적고 간선 수가 많을 때 유용
인접리스트	- 메모리 효율이 좋음 - 인접노드 찾기 쉬움 - 노드 추가,삭제 용이 - 간선 추가 빠름 - 모든 간선 수 찾는데 용이	- 두 노드간 간선정보 확인 불리	비교적 간선 수가 적고 노드수가 많을 때 유용

- DFS : 깊이우선탐색(재귀함수, Stack을 주로 이용해 구현)

그림1

위 그림의 숫자 순서대로 탐색을 한다. 말로 풀어서 설명하자면 인접한 노드이면서(1), 방문한적(2)이 없는 노드를 탐색하는 것이다. (1),(2)의 조건 중 하나라도 성립하지 않으면 해당 노드에서 탐색을 마치고 다음 노드로 넘어간다.

 

2. 인접행렬을 활용한 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main11724 {
	static int N,M;
	static boolean[] visited;
	static int[][] map;
	static int ans = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		visited = new boolean[N+1];
		map = new int[N+1][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());
			map[x][y] = map[y][x] = 1;
		}
		
		for (int i=1; i<=N; i++) {
			if (!visited[i]) {
				dfs(i);
				ans++;				
			}
		}
		
		System.out.println(ans);
	}
	
	public static void dfs(int start) {
		if (visited[start]) {
			return;
		}
		visited[start] = true;
		for (int i=1; i<=N; i++) {
			if (!visited[i] && map[start][i] == 1) {
				dfs(i);
			}
		}
	}
}

 

3. 인접리스트를 활용한 구현

import java.io.*;
import java.util.*;
public class P11724_연결요소의개수 {
  static ArrayList<Integer>[] A;
  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());
    A = new ArrayList[n + 1];
    visited = new boolean[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);
    }
    int count = 0;
    for (int i = 1; i < n + 1; i++) {
      if (!visited[i]) { // 미 방문한 정점이 없을 때까지 반복
        count++;
        DFS(i);
      }
    }
    System.out.println(count);
  }
  static void DFS(int v) {
    if (visited[v]) {
      return;
    }
    visited[v] = true;
    for (int i : A[v]) {
      if (visited[i] == false) { // 연결 정점 중 방문하지 않았던 정점만 탐색함
        DFS(i);
      }
    }
  }
}
출처 : https://github.com/doitcodingtestjava/answer/blob/main/%ED%83%90%EC%83%89/P11724_%EC%97%B0%EA%B2%B0%EC%9A%94%EC%86%8C%EC%9D%98%EA%B0%9C%EC%88%98.java

 

정리 : 그래프의 개념 및 구현이 미숙해 헤맨 문제다. 그래프에 대해 깊이있게 추가 공부를 하자