1. 최종 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
vector<int> arr[20001];
queue<int> q;
int check[20001];
bool bfs(int start) {
check[start]=1; q.push(start);
while(!q.empty()) {
int node=q.front(); q.pop();
for(int i=0; i<arr[node].size(); i++) {
int next=arr[node][i];
if(check[next]==0) {
check[next]=(3-check[node]);
q.push(next);
} else if (check[next]==check[node])
return false;
}
}
return true;
}
int main(void)
{
int t,v,e,a,b;
scanf("%d", &t);
while(t--) {
bool ans=true;
scanf("%d %d", &v, &e);
for(int i=0; i<e; i++) {
scanf("%d %d", &a, &b);
arr[a].push_back(b);
arr[b].push_back(a);
}
for(int i=1; i<=v; i++) {
if(check[i]==0) {
if(bfs(i)==false) {
printf("NO\n");
ans=false;
break;
}
}
}
if(ans) printf("YES\n");
while(!q.empty()) q.pop();
for(int i=0; i<=v; i++) arr[i].clear();
memset(check,0,sizeof(check));
}
return 0;
}
|
cs |
2. 이건 최종코드 만들기 전에 길게 풀어서 쓴거. 아마 길게 풀어서 쓴걸 보면 더 이해하기 쉬울 것 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
vector<int> arr[20001];
queue<int> q;
int check[20001];
bool bfs(int start) {
check[start]=1; q.push(start);
// 큐가 비어있지 않은 동안 (방문하지 않은 노드가 있는 동안)
while(!q.empty()) {
int node=q.front(); q.pop(); //방문할 노드 정함
//노드가 만약에 빨강색이면
if(check[node]==1) {
//사이즈만큼 도는데
for(int i=0; i<arr[node].size(); i++) {
//인접한 노드를 돈다.
int next=arr[node][i];
//만약 아직 인접한 노드를 방문하지 않았으면
if(check[next]==0) {
check[next]=2; //인접한 노드를 파랑색으로 한다.
q.push(next);
} else{ //만약 인접한 노드를 방문했다면
if (check[next]==1)// 색깔이 동일한 빨강색이면
return false; // 실패를 리턴
}
}
} else { //색깔이 파란색(check[node]==2)
//사이즈만큼 도는데
for(int i=0; i<arr[node].size(); i++) {
//인접한 노드를 돈다.
int next=arr[node][i];
//만약 아직 인접한 노드를 방문하지 않았으면
if(check[next]==0) {
check[next]=1; //인접한 노드를 빨간색으로 한다.
q.push(next);
} else {//만약 인접한 노드를 방문했다면
if (check[next]==2) // 색깔이 동일한 파랑색이면
return false; // 실패를 리턴
}
}
}
}
return true;
}
int main(void)
{
int t,v,e,a,b;
scanf("%d", &t);
while(t--) {
bool ans=true;
scanf("%d %d", &v, &e);
for(int i=0; i<e; i++) {
scanf("%d %d", &a, &b);
arr[a].push_back(b);
arr[b].push_back(a);
}
for(int i=1; i<=v; i++) {
if(check[i]==0) {
if(bfs(i)==false) {
printf("NO\n");
ans=false;
break;
}
}
}
if(ans) printf("YES\n");
while(!q.empty()) q.pop();
for(int i=0; i<=v; i++) arr[i].clear();
memset(check,0,sizeof(check));
}
return 0;
}
|
cs |
주어진 예제 말고 테스트하는데 사용한 반례는 아래와 같다. (백준 질문게시판에서 전부 긁어옴)
INPUT :
11
3 1
2 3
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
3 2
2 1
3 2
4 4
2 1
3 2
4 3
4 1
5 2
1 5
1 2
5 2
1 2
2 5
4 3
1 2
4 3
2 3
4 4
2 3
1 4
3 4
1 2
3 3
1 2
2 3
3 1
2 1
1 2
OUTPUT :
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
(+) 자바 코드
1. 리스트
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayList;
public class Main{
static ArrayList<Integer> arr[]; // 간선이 서로 연결되어있는지 확인하는 배열
static boolean[] visited; // 정점을 방문했는지 확인하는 배열
static int[] colored; // 각 정점의 색깔을 저장하는 배열
static int v, e, from, to;
static boolean flag;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int tc = Integer.parseInt(br.readLine());
// 테스트케이스 만큼 돌리기
for(int i=0; i<tc; i++){
st = new StringTokenizer(br.readLine(), " ");
// 정점이랑 간선 갯수 입력받기
v = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
// 필요한 배열들 만들기
arr = new ArrayList[v+1];
for(int j=0; j<=v; j++){
arr[j] = new ArrayList<Integer>();
}
visited = new boolean[v+1];
colored = new int[v+1];
// 간선 입력받기
for(int j=0; j<e; j++){
st = new StringTokenizer(br.readLine(), " ");
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
// 양방향
arr[from].add(to);
arr[to].add(from);
}
// 이분 그래프인지 확인을 해줌
// 왜 모든 정점에 대해서 함수를 돌리냐면 정점들이 연결이 안 될 경우도 있을거라서
for(int j=1; j<=v; j++){
if(!visited[j] && !flag){
isBinaryTree(j,1);
}
else if(flag)
break;
}
if(flag) sb.append("NO").append("\n");
else sb.append("YES").append("\n");
// 초기화
flag = false;
}
System.out.println(sb);
return;
}
// 1 : 검정, 2 : 빨강
public static void isBinaryTree(int node, int color){
for(int next : arr[node]){
if(!visited[next]){
visited[next]=true;
colored[next]=3-color;
isBinaryTree(next, 3-color);
}
else {
if(colored[next]==color){
flag = true;
}
}
}
}
}
|
cs |
2차원 배열로 풀었더니 메모리 초과남..
'백준 2 > 그래프' 카테고리의 다른 글
| [백준 7569] 토마토 (C++/Python) (0) | 2020.12.08 |
|---|---|
| [백준 7576] 토마토 (C++/Python) (0) | 2020.12.08 |
| [백준 10451] 순열 사이클 (0) | 2020.12.08 |
| [백준 11724] 연결 요소의 개수 (C++/Java) (0) | 2020.12.08 |
| [백준 1260] DFS와 BFS (C++/Python) (0) | 2020.12.08 |
