[백준 알고리즘] 11724 연결 요소의 개수 (21.05.02)

이전 이야기 ....

 

 

2021.05.02 - [알고리즘 스터디] - [백준 알고리즘] 2606 바이러스 (21.05.02)

[백준 알고리즘] 2606 바이러스 (21.05.02)

 

 

 

---

 

 

두 번째 BFS/DFS 문제는 !!!!

 

 

백준 2606 연결 요소의 개수

 

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

 

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

 

문제 사이트 : www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

 

---

 

여기서 핵심 포인트!!!

 

 

-  연결 요소의 개수를 어떻게 얻는가?

 

- 그래프 구현

- BFS 혹은 DFS

 

---

 

 

 

 

직접 작성해본 소스코드 및 간단한 설명

 

import java.util.ArrayList;
import java.util.Scanner;


class AdjListGraph {
	private ArrayList<ArrayList<Integer>> adjListGraph;
	private boolean visited[] = new boolean[1001];
	
	public AdjListGraph(int size) {
		this.adjListGraph = new ArrayList<ArrayList<Integer>>(); // 그래프 생성
		for (int i = 0; i < size + 1; i++) {
			adjListGraph.add(new ArrayList<Integer>());
		}
	}

	public ArrayList<ArrayList<Integer>> getGraph() {
		return this.adjListGraph;
	}

	public ArrayList<Integer> getNode(int i) {
		return this.adjListGraph.get(i);
	}

	public int getNodeSize(int i) {
		return this.adjListGraph.get(i).size();
	}

	public void put(int x, int y) {
		adjListGraph.get(x).add(y);
		adjListGraph.get(y).add(x);
	}

	public void resetVisited() {
		for (int i = 0; i < 1000; i++) {
			visited[i] = false;
		}
	}

	public void DFS(int v) {
		visited[v] = true;
	    for (int i=0; i <adjListGraph.get(v).size(); i++) {
	    	int y = adjListGraph.get(v).get(i);
	        if (visited[y] == false){
	        	DFS(y);
	        }
	    }
	}
	
	public boolean[] getVisited() {
		return visited;
	}

}

public class CountConnection {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int node, edge;
		
		node = sc.nextInt();
		edge = sc.nextInt();
		
		AdjListGraph alg = new AdjListGraph(node);
		
		for(int i = 0; i < edge; i++) {
			int first, end;
			first = sc.nextInt();
			end = sc.nextInt();
			alg.put(first, end);
		}
		
		int connectionCount = 0;
		for (int i = 1; i < node + 1; i++) {
			boolean[] visited = alg.getVisited();
			if (!visited[i]) {
				connectionCount++;
				alg.DFS(i);
			}
		}
		System.out.println(connectionCount);

	}
}

 

 

이전의 그래프 코드를 그대로 가져와 응용했으니

 

중요 포인트만 짚어보자면!!!

 

 

• 1부터 node 까지 방문했는 지를 확인한다.
• 방문을 안했다면, 해당 노드의 DFS 를 해준다.

 

---

 

사실 엄청 나게 어려운 건 아니지만,

DFS 개념이 잘 생각이 안 나서 오래 걸린 것 같다!!!

 

---

 

 

 

 

 

 

 

백준 알고리즘

 

채점 결과!!!

 

 

 

다행히 맞았습니다!!

 

백준 11724 채점 결과

 

 

 

 

 

 

 

 

 

 

 

---

스터디를 하며 얻은 방법?

• node의 개수가 1000으로 주어졌으니, visited는 1001까지 크기가 되어야 한다.

     (이건 내가 그래프를 1부터 집어넣기 때문!!!)