[백준] code.plus(큐와 그래프,JAVA)11724번, 연결 요소의 개

문제 링크

11724번: 연결 요소의 개수

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에서 그래프와 BFS를 통하여 문제를 해결하였습니다.

 

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 연결 요소의 개수를 구해서 출력해야 합니다.

2. 입력되는 간선은 무방향입니다.

 

먼저 문제에서 연결요소라고 표현하는 것을 그림으로 설명하면

예제입력의 요소들의 간선을 표현한 것입니다.

위와 같이 영역이 2가지 부분으로 나누면 연결요소가 2개 있다고 출력되는 것처럼

연결요소 = 영역이라고 생각하고 문제를 해결하였습니다.

 

 

 

알고리즘을 구현하기 위해 저는 BFS(너비 우선 탐색)을 통해 구현하였습니다.

 

그래프에 대한 내용을 정의하기 위해 ArrayList<ArrayList<Integer>>의 형태로 리스트를 만들어주었습니다.

위와 같이 정의하여 데이터를 저장하면 각 정점이 어떤 정점으로 이동하는지 간단하게 저장할 수 있습니다.

예를 들어 

1 -> 4

1 -> 3

2 -> 5

3 -> 4

ArrayList<ArrayList<Integer>>의 저장되는 모습은 리스트 안에 리스트가 포함되는 형식으로 저장됩니다.

정점
1	3	4
2	5
3	1	4
4	1	4
5	2

 

BFS를 통해 정점을 방문한 것을 확인하여 영역의 개수를 확인하였습니다.

예제입력1으로 BFS가 진행되는 과정을 보여드리겠습니다.

 

정점 1으로 시작할 때

정점 1에 연결된 정점 2와 정점 5를 방문하였습니다.

 

정점 1에서 연결된 정점 2를 탐색하면

정점 5로 이동할 수 있지만 정점 5는 정점1에서 벌써 탐색하였기 때문에 탐색하지 않고 BFS탐색을 종료합니다.

 

정점 2에서 시작할 때

정점 2는 벌써 방문하였기 때문에 시작 정점으로 사용할 수 없습니다.

 

정점 3에서 시작할 때

정점 3에 연결된 정점 4를 방문하였습니다.

 

정점 3에서 연결된 정점 4를 탐색하면

정점 4에 연결된 정점 6을 방문하였습니다.

 

정점 4에서 연결된 정점 6에서는 더 이상 방문할 정점이 없기 때문에 BFS탐색을 종료합니다.

 

이후 정점 4, 5, 6으로 시작할 때에는 모두 탐색되었기 때문에 BFS를 진행하지 않고 결과로 나온 영역을 출력합니다.

 

결과 = BFS 연산을 시작한 횟수

정점 1, 정점 3일 때 BFS 연산을 시작하였으므로 연결 요소는 2개가 됩니다.

 

결과로 2를 출력합니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 정점들의 간선을 ArrayList<ArrayList<Integer>>에 저장합니다.

2. BFS(너비 우선 탐색)을 이용하여 시작 노드 1~N까지 모든 경우를 탐색합니다.

3. 연결 요소 = BFS 시작되는 횟수로 결과를 출력합니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 노드에 대한 값을 나누었습니다.
• BFS탐색으로 정점과 노드를 탐색하는 bfs함수를 사용하였습니다.
• BufferedWriter에 BFS탐색이 시작되는 횟수(연결 요소)를 저장하였습니다.
• BufferedWriter에 저장된 값을 결과로 출력하였습니다.

• bfs 함수는 너비 우선 탐색을 이용하여 정점과 노드를 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int N,M;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();	//간선 정보 저장
	static boolean[] check;		//방문 확인 배열
	public static void main(String[] arg) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
        	//--------입력값 저장 및 리스트 초기화--------
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		check = new boolean[N+1];
		
		for(int i=0;i<=N;i++)
			graph.add(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());
			graph.get(u).add(v);		//간선 값 저장
			graph.get(v).add(u);		//간선 값 저장
		}
		int count = 0;
		for(int i=1;i<=N;i++) {
			if(!check[i]) {		//정점 방문하지 않았을 때
				bfs(i);		//BFS 함수 실행
				count++;		//BFS 시작시 연결 요소 + 1
			}
		}
		bw.write(count + "\n");		//연결 요소 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//BFS를 이용하여 정점과 간선을 탐색하는 함수
	static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);		//시작 정점 저장
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			for(int value : graph.get(temp)) {
				if(!check[value]) {		//해당 정점 탐색하지 않았을 때
					queue.add(value);
					check[value] = true;
				}
			}
		}
		return;
	}
}