조건 체크를 안해서 시간초과가 떴다. 그래서 3시간을 날렸다...
연결 요소가
1 5
1 3
5 6
3 4
처럼 있다는 가정하게 bfs(1)부터 시작하여
map[1][1]~map[1][n]까지 돌아 조건에 맞는값을 queue에 넣고
넣은값 n으로 다시 요소들을 검색하는 방법을 생각했다.
1 -> 5,3 저장
5 -> 6 저장
3 -> 4 저장
6 탐색, 4 탐색..
1 3 4 5 6 을 한 요소로 묶고 방문했다는 표시를 남겨
다른 요소에서 1,3,4,5,6을 접근할수 없도록 했다.
문제를 풀기전에 chk를 2차원 배열로 만들었었다.
하지만 위의 logic을 구현하기 위해서는 각 번호의 방문값만 체크하면 된다고 생각했기에
1차원 배열로 수정했다.
만약에 map[i][j]에서 i를 이미 방문한적이 있다면 다시 탐색을 할 필요가 없으므로
방문한적이 없을때 bfs를 돈다.for (int i = 1; i <=n; i++) { if(!chk[i]){ bfs(i); } }
bfs들어왔다는것은 하나의 연결요소라는 뜻이므로 answer++를 해준다.
이값을 queue에 넣고 그 배열에 가로 값들을 탐색해서 방문한적이 없고, 조건에 맞으면 queue에 넣고 해당 값은 true로 바꿔준다.public static void bfs(int y) { Queue<Integer> queue = new LinkedList<>(); queue.add(y); answer++; while (!queue.isEmpty()) { int now = queue.poll(); chk[now] = true; for (int i =1; i <=n; i++) { if (!chk[i] && map[now][i] == 1 ) { queue.add(i); chk[i] = true; } } } }
import java.util.*;
public class Main {
static int n;
static int m;
static int[][] map;
static boolean[] chk;
static int answer = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
map = new int[n+1][n+1];
chk = new boolean[n+1];
for (int i = 0; i < m; i++) {
int y = sc.nextInt();
int x = sc.nextInt();
map[y][x] = 1;
map[x][y] = 1;
}
for (int i = 1; i <=n; i++) {
if(!chk[i]){
bfs(i);
}
}
System.out.println(answer);
}
public static void bfs(int y) {
Queue<Integer> queue = new LinkedList<>();
queue.add(y);
answer++;
while (!queue.isEmpty()) {
int now = queue.poll();
chk[now] = true;
for (int i =1; i <=n; i++) {
if (!chk[i] && map[now][i] == 1 ) {
queue.add(i);
chk[i] = true;
}
}
}
}
}