문제
요약
1~N 번의 번호를 가진 사람이 있을 때, 각 사람들의 인간관계를 연결해서 무리를 만들어야한다.
최종적으로, 받은 입력으로 만들어지는 전체 무리 개수를 출력해야한다.
접근
이 문제를 보고 사람과 사람 사이의 관계를 그래프로 표현할 수 있다고 생각했다. 각 사람을 정점으로 두고, 서로 알고 있는 두 사람 사이에 간선을 연결하면 된다.
그래프는 인접 행렬과 인접 리스트 모두 사용할 수 있다. 인접 행렬은 두 사람이 연결되어 있는지 O(1)에 확인할 수 있지만, 특정 사람과 연결된 모든 사람을 찾으려면 1번부터 N번까지 확인해야 한다. 또한 사람 수가 많고 실제 관계의 수가 적다면 사용하지 않는 공간이 많아질 수 있다.
이 문제에서는 한 사람과 연결된 사람들을 탐색하고, 다시 그 사람들과 연결된 사람들을 연속해서 탐색해야 한다. 따라서 실제로 연결된 사람들만 저장하고 탐색할 수 있는 인접 리스트가 더 자연스럽다고 판단했다.
각 사람마다 연결된 사람들을 리스트에 저장한 뒤, 1번부터 N번까지 순차적으로 확인한다. 아직 방문하지 않은 사람을 발견하면 새로운 무리라고 판단해 무리의 개수를 1 증가시키고, DFS나 BFS를 통해 해당 사람과 연결된 모든 사람을 방문 처리한다. 이후 이미 방문한 사람은 같은 무리에 속한 사람이므로 다시 탐색하지 않는다. 나는 BFS를 활용해서 문제를 풀었다.
이 과정을 N번 사람까지 반복하면 서로 연결된 사람들의 집합, 즉 연결 요소의 개수를 구할 수 있고 이것이 마을의 무리 개수가 된다.
알고리즘
- 인접 리스트로 사람 사이의 관계를 표현한다.
- visited 배열을 만들어 각 사람의 방문 여부를 관리한다.
- 1번부터 N번까지 순차적으로 확인한다.
- 현재 사람이 이미 방문했다면 같은 무리에서 처리된 사람이므로 넘어간다.
- 아직 방문하지 않은 사람이라면 새로운 무리의 시작이므로 무리 수를 1 증가시키고, 해당 사람을 Queue에 넣어 BFS~
- Queue에서 사람을 하나씩 꺼내 해당 사람과 연결된 사람들을 확인한다. 아직 방문하지 않은 사람이 있다면 방문 처리한 뒤 Queue에 넣는다.
- Queue가 빌 때까지 반복하면 현재 사람과 연결된 하나의 무리가 모두 처리된다.
- N번 사람까지 반복한 뒤 무리 수를 출력한다.
제출 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class swea_7465_창용마을무리의개수 {
static boolean[] visited;
static List<List<Integer>> peoples;
static int N;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken()); // 정점 개수
int M = Integer.parseInt(st.nextToken()); // 엣지 개수
int group = 0; // 그룹 수 카운트
peoples = new ArrayList<>(); // 사람들 연결된 그래프
for (int i = 0; i <= N; i++) {
peoples.add(new ArrayList<>()); // 0~N번까지 노드까지 초기화
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
// 양방향 처리
peoples.get(s).add(e);
peoples.get(e).add(s);
}
// 인접리스트 확인
// printAdjList();
visited = new boolean[N+1]; // 인맥 방문 처리
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
bfs(i);
group++;
}
}
sb.append("#").append(tc).append(" ").append(group).append("\n");
}
System.out.println(sb.toString());
}
static void bfs(int people) {
visited[people] = true;
Queue<Integer> q = new ArrayDeque<>();
q.offer(people);
while(!q.isEmpty()) {
int me = q.poll();
for (int i = 0; i < peoples.get(me).size(); i++) {
// 나와 연결되어있는 친구를 큐에 넣는다.
int friend = peoples.get(me).get(i);
if (!visited[friend]) {
q.offer(friend);
visited[friend]= true;
}
}
}
}
// static void printAdjList() {
// System.out.println();
// for (int i = 0; i <= N; i++) {
// System.out.print(i + " : ");
// if (peoples.get(i).isEmpty()) {System.out.println(); continue;}
// for (int j = 0; j < peoples.get(i).size(); j++) {
// System.out.print(peoples.get(i).get(j) + ", ");
// }
// System.out.println();
// }
// }
}어려웠던 점
- 인접 리스트 개념은 알고 있는데 직접 구현하려니 어렵다..
- ArrayList로 구현을 했는데, 처음이라 어색한 듯하다... 이걸 LinkedList로 직접 구현해서 푸는 방법으로도 해봐야한다. - 또 다른 핵심은 무방향 그래프이기에 양방향 그래프로 처리를 해야한다! 단방향으로 처리하게 되면, 모든 관계를 표현하지 못한다.
깨달은 점
List<List> 이렇게 구현할수도 있고, List[] 이렇게 구현하면, 배열 안에 List를 집어넣을 수 있다!
