[Java] 백준 11724.연결 요소의 개수

➡️문제 링크

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

 

 

💡아이디어

문제의 제목부터 그래프 느낌이 났는데

읽어보니 정말 그래프문제였다

예제1

 

예제2

문제에서 주어진 예제를 직접 그리면 위의 그림처럼 표현할 수 있다.

즉, 각 정점을 돌며 하나의 정점에서 끊어지지 않고 계소 연결되는 게 몇 차례 이루어지나를 묻고 있다

주어진 지도에서 마을의 개수가 몇개인지를 묻는 전형적인 그래프 문제 느낌이 나서

빠르게 풀었다

그래서

1. 방향이 없는 -> 양방향이니까, 리스트에 각각 저장해야지

2. 하나의 정점에서 연결됨을 확인하기 -> boolean 배열 만들어서 방문할때마다 true 처리해야지

이렇게 풀이방법을 잡았다

 

 

✏️문제 풀이

bfs로만 푸려다가 취약한 dfs로도 풀었다.

 

1.  dfs - 성공

int dfsCount = 0;
for(int i = 1; i <= N; i++) {
	if(!visited[i]) {
		visited[i] = true;
		dfs(i);
		dfsCount++;
	}
}

...



static void dfs(int num) {
	List<Integer> list = graph.get(num);
		
	for(int i = 0; i < list.size(); i++) {
		int nextNum = list.get(i);
			
		if(!visited[nextNum]) {
			visited[nextNum] = true;
			dfs(nextNum);
		}
	}
}

 

2.  bfs -  성공

int bfsCount = 0;
for(int i = 1; i <= N; i++) {
	if(!visited[i]) {
		visited[i] = true;
		bfs(i);
		bfsCount++;
	}
}


...



static void bfs(int num) {
	Queue<Integer> que = new LinkedList<>();
	que.add(num);
		
	while(!que.isEmpty()) {
		int curNum = que.poll();
			
		List<Integer> list = graph.get(curNum);		// 해당 숫자의 리스트
			
		for(int i = 0; i < list.size(); i++) {
			int nextNum = list.get(i);
			if(!visited[nextNum]) {
				visited[nextNum] = true;
				que.add(nextNum);
			}
		}
	}
}