문제
풀이
import java.io.*;
import java.util.*;
public class Q1707_이분그래프판별하기 {
static ArrayList<Integer>[] arr;
static int[] check;
static boolean[] visited;
static boolean result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 테스트 케이스
int k = Integer.parseInt(st.nextToken());
int v;
int e;
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
// 노드 개수
v = Integer.parseInt(st.nextToken());
// 에지 개수
e = Integer.parseInt(st.nextToken());
// 트리 정보를 저장할 배열
arr = new ArrayList[v+1];
// 집합을 저장할 배열
check = new int[v + 1];
// 방문 정보를 저장할 배열
visited = new boolean[v + 1];
// 사이클을 형성하는 노드가 있는지 확인하는 변수
result = true;
for (int j = 1; j <= v; j++) {
arr[j] = new ArrayList<>();
}
for (int j = 1; j <= e; j++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
// 방향이 정해지지 않았으므로 양쪽 노드 모두에 에지 정보 저장
arr[start].add(end);
arr[end].add(start);
}
for (int j = 1; j <= v; j++) {
// 그래프가 1개로 연결되어 있는지 보장되지 않으므로 모든 노드를 탐색
if (result) {
dfs(j);
} else {
break;
}
}
// 사이클이 형성되지 않았다면 YES 아니면 NO
if (result) {
bw.write("YES\n");
} else {
bw.write("NO\n");
}
}
bw.flush();
br.close();
bw.close();
}
public static void dfs(int node) {
// 현재 노드 방문 체크
visited[node] = true;
for (int next : arr[node]) {
if (!visited[next]) {
// 다음 노드의 집합을 현재 노드와 다른 집합으로 설정
check[next] = (check[node] + 1) % 2;
dfs(next);
// 다음 노드를 이미 방문했는데, 현재 노드와 같은 집합이라면
// 사이클이 형성된 것으로 result를 false로 설정
} else if (check[next] == check[node]){
System.out.println();
result = false;
return;
}
}
}
}리뷰
트리의 경우 항상 이분 그래프가 된다. 사이클이 발생하지 않을 경우 탐색을 진행하면서 다음 노드를 이번 노드와 다른 집합에 포함시키면 되기 때문이다.
위의 트리를 예를 들어 8을 집합 a에 포함시키고, 다음 트리인 3과 10은 집합b에 포함시키는 방식으로 집합을 구분하면 이분 그래프가 된다.
전체적인 흐름은 파악을 했고, 큰 틀은 맞게 로직을 작성을 하였다.
그런데 인접 노드의 집합을 구분하는 연산 과정에서 내가 의도하지 않은 방향으로 로직이 진행되는 문제가 발생하였다. 정답 로직을 참고하더라도 내가 작성한 로직이 왜 틀렸는지 그 반례를 찾기 위해 하나하나 흐름을 따져보았고 반례를 찾았는데, 막상 이렇게 하니 시간이 오래걸렸다ㅜ
내가 작성한 로직(틀림)
public class Main {
static ArrayList<Integer>[] arr;
static int[] visited;
static boolean result;
static int pos;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 테스트 케이스
int k = Integer.parseInt(st.nextToken());
int v;
int e;
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
// 노드 개수
v = Integer.parseInt(st.nextToken());
// 에지 개수
e = Integer.parseInt(st.nextToken());
arr = new ArrayList[v+1];
visited = new int[v + 1];
result = true;
for (int j = 1; j <= v; j++) {
arr[j] = new ArrayList<>();
}
for (int j = 1; j <= e; j++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
arr[start].add(end);
arr[end].add(start);
}
for (int j = 1; j <= v; j++) {
if (result) {
dfs(j);
} else {
break;
}
}
if (result) {
bw.write("YES\n");
// System.out.println("YES");
} else {
bw.write("NO\n");
// System.out.println("NO");
}
}
bw.flush();
br.close();
bw.close();
}
public static void dfs(int node) {
// 이 부분이 틀린 부분이다.
if(pos == 1){
pos=2;
}else{
pos=1;
}
visited[node] = pos;
for (int next : arr[node]) {
if (visited[next] == 0) {
dfs(next);
} else if (visited[next] == visited[node]){
result = false;
return;
}
}
}
}- 이 로직에서 문제가 집합을 분리하는 pos를 적용하는 과정에서 문제가 발생하였다.
노드 1,2,3의 에지 정보가 아래와 같을 때
1 3
2 3
각 노드의 에지 정보는 다음과 같다
1 - 3
2 - 3
3 - 1, 2-
j = 1일때,
node = 1, pos = 1, visited = {0,1,0,0}, next = 3, visited[3]==0이므로 재귀호출
node = 3, pos = 2, visited = {0,1,0,2}, next = 1, visited[1]!=0, visited[3] != visited[1]이므로 다음 반복문 실행
next=2, visited[2]==0이므로 재귀호출
node = 2, pos = 1, visited = {0,1,1,2}, next = 3, visited[3]!=0이므로 재귀호출을 빠져나감 -
j=2일때,
node = 2, post = 2, visited = {0,1,2,2}, next = 3, visited[3]!=0, visited[3] == visited[2]이므로 else if문 실행
result = false가 되고, 재귀호출을 빠져나감
결국 이 코드에서는 노드 1과 2가 다른 집합임에도 불구하고 NO라는 결과가 나오게 된다.
어떤 점 때문에 틀렸는지 확인했고 반례도 찾을 수 있었지만 시간이 너무 오래걸려서 이렇게 하는 것이 맞을지 하는 생각이 든다. 그냥 빠르게 답을 확인하고 더 많은 문제를 풀어보는게 더 나은 방법은 아닐까 싶다ㅜㅜ
