그래프 문제를 처음 접하게되었다...
어렵드라..
간단하게 dfs와 bfs 방식을 공부하고 , 기본 형태의 코드를 보면서 어떻게 동작하는지 봤다.
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
그리고 실제로 첫번째 문제를 풀어보았다.
https://www.acmicpc.net/problem/11724
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주
www.acmicpc.net
사실 문제보고 문제 이해도못했다.
그러다가 유튜브에서 dfs,bfs 설명을 좀더 찾다가 connected component 관련 설명을 듣고나니 문제가 이해가됬다.
https://www.youtube.com/watch?v=3G2lwJkLFEY
그리고 문제를 풀었는데 45%쯤에서 계속 틀렸다.
정답을 검색해볼까하다가 아래 글을 읽고 틀린부부분을 찾아 해결하였다.
https://www.acmicpc.net/board/view/68534
글 읽기 - 틀린 사람을 위해 작성해둡니다.
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
코드는 간단하게 리뷰하면 , 기본 dfs방식코드를 사용하였고 , 입력받은 정점을 체크하기위해 boolean 타입으로 checkInt를 만들었다. dfs로 찾은 수를 checkInt에서 false 처리하는것으로 이어지지않은 정점을 체크할수있엇다.
위에 검색글에서 찾은 내용중 입력받은 수가 2 4 여도 1,3이 단일 노드로 존재하는것으로 판단하라고 하여서 입력받지 않은 수를 카운트하는 로직을 추가하니 문제가 풀렸다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] node = new int[n+1][n+1];
boolean[] bool = new boolean[n+1];
boolean[] checkInt = new boolean[n+1];
for(int i=0;i<m;i++) {
int x = sc.nextInt();
int y = sc.nextInt();
checkInt[x]=true;
checkInt[y]=true;
node[x][y]=1;
node[y][x]=1;
}
int count=0;
for(int i=1;i<checkInt.length;i++) {
if(!checkInt[i]) count++;
}
for(int i=0;i<checkInt.length;i++) {
if(checkInt[i]) {
count++;
dfs(i,node,bool,checkInt);
}
}
System.out.println(count);
}
static void dfs(int v, int[][] node ,boolean[] bool,boolean[] checkInt) {
checkInt[v]=false;
bool[v]=true;
for(int i=0;i<bool.length;i++) {
if(node[v][i]==1&&!bool[i]) {
dfs(i,node,bool,checkInt);
}
}
}
}
