mingssssss
1. 문제
https://www.acmicpc.net/problem/11724
2. 코드
package mymain;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ_11724 {
static boolean visited[];
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
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());
int[][] map = new int[N + 1][N + 1];
visited = new boolean[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
map[r][c] = 1;
map[c][r] = 1;
}
// 입력 종료
int answer = 0;
for (int i = 1; i < N + 1; i++) {
if (visited[i] == false) {
BFS(i, N, M, map, visited);
answer++;
}
}
System.out.println(answer);
}
public static void BFS(int idx, int N, int M, int[][] map, boolean[] visited) {
Queue<Integer> q = new LinkedList<>();
q.add(idx);
int cnt = 0;
while (!q.isEmpty()) {
int check = q.poll();
for (int i = 1; i < N + 1; i++) {
if (map[check][i] == 1 && visited[i] == false) {
visited[i] = true;
q.add(i);
}
}
}
}
}
3. 리뷰
bfs문제만 골라서 풀고 있는데, 다른 문제는 리스트가 만들어져 있는 문제만 풀었는데,
이 문제는 노드 간선으로 이루어진 문제라서 처음 접해보는 유형이었다.
처음에 주어진 입력만으로 푸려고 했는데 도저히 아이디어가 안 떠올라서
구글링을 해서 다른 분들의 풀이를 봤는데 이해가 가지 않았다.
혼자 끙끙거리면서 푼 경험을 살려 상세히 설명하겠다.
-
노드와 간선과 연결되어있는 좌표가 나오므로, 이 좌표를 인접리스트를 생성하여
값을 넣어줬다. 무방향 그래프므로, 1 2는 2 1처럼 서로 방향성을 설정하여 넣어줬다.
예제 1번의 경우 인접리스트는 다음과 같이 그려진다.
0 0 0 0 0 0 0
0 0 1 0 0 1 0
0 1 0 0 0 1 0
0 0 0 0 1 0 0
0 0 0 1 0 0 1
0 1 1 0 0 0 0
0 0 0 0 1 0 0 -
인접리스트 생성 후 방문 했는지 체크하는 boolean형 배열을 생성했다.
혼동을 피하기 위해, 들어온 좌푯값 그대로 설정했다. (1, 1)의 경우 (0, 0)에
집어넣지 않고 그대로 (1, 1)에 넣었다. -
i를 1부터 N + 1까지 순회하면서 각 노드들이 연결되어있는지 확인한다.
visited[i]가 true인 경우에는 이미 방문했으므로, false일 때만
BFS에 i값을(행값) 넣어줘서 연결을 확인했다. -
Queue를 만들어서 들어온 i 값을 넣고 탐색을 시작한다.
인접리스트의 열의 길이도 N이므로 N + 1까지 확인해서 한 열의 끝까지 확인한다.
값을 확인했을 때 1인 경우이면서 방문하지 않은 경우, 큐에 해당 좌푯값을 넣어줬다.
그리고 방문처리를 했다.
그렇게 되면 (1, 2)의 경우 큐에 2가 들어가게 된다.
그리고 그 줄에 (1, 5)의 경우에도 동일하게 5가 들어가게 된다.열 탐색이 끝났으므로, 큐에 들어가있는 2를 탐색한다.
2번째 열을 쭉 탐색하면서 2와 연결되어 있는 노드를 탐색하고 큐에 집어넣는다.
이런 탐색을 하게 되면 처음 i = 1인 값부터 1과 연결된 모든 노드를 탐색하게 된다.Queue가 비어있다면, 연결되어 있는 모든 노드를 탐색했으므로, 탐색을 종료하고
answer++ 해준다.다음 i는 2이므로 2번째 행에 있는 모든 노드를 탐색한다... N + 1까지!
총평: 노드와 간선으로 이루어진 문제를 처음 풀어봤는데, 다른 문제도 풀 수 있을 것 같다.
오랜 시간 고민해서 그런지 완전히 내 것이 된 것 같다.
