이 문제는 처음 접근 방식이 중요하다.
결론부터 말하자면 BFS를 이용해 접근하는 것이 가장 효율적인 것으로 생각된다.
하지만 처음 접근할 때는 홈페이지에 있는 예시만 보고 접근했기 때문에 반례들을 생각 못하고 무작정 짰다.
내 가장 큰 습관 중 하나는, 문제를 보고 원리가 파악된다면 그걸 '그대로' 구현하려고 한다는 것이다.
예를 들어서, 줄 가장 뒤에 있는 아이를 맨 앞으로 보냈을 때 최종 순위가 어떻게 되는가? 하는 문제가 있다면
당연히 가장 뒤에 있는 아이를 앞에 아이와 SWAP을 모두 한 후 출력하면 된다고 접근할 것이다.
하지만 조금 더 빠른 동작을 위해서 각 아이들의 순위를 모두 +1하고 가장 뒤의 아이만 1로 만들어도 충분할 것이다.
먼저 생각해볼만한 것은,
1. 이분 그룹은 유일하지 않다. (서로 독립된 그룹이 있을 경우)
2. 모든 Node를 돌아봐야하고 하나의 케이스만 성립해도 된다.
정도인 것 같다.
독립적인 그룹이 있을 경우 이분 그룹은 유일하지 않다.
하지만 유일하지 않아도 크게 상관은 없다.
앞서 말한것처럼 가장 먼저 시도한 것은 원칙적인 접근이다.
int CheckNeighbor(int V,int nowidx, vector<int> Node[20001],int * Visited) {
vector<int> adjnode;
// 1 node 의 인접 node 를 구한다.
for (int i = 0; i < Node[nowidx].size(); i++) {
adjnode.push_back(Node[nowidx][i]);
Visited[Node[nowidx][i]];
}
// 인접 node들끼리 연결되어 있는지 확인한다.
for (int i = 0; i < adjnode.size(); i++) {
int node = adjnode[i];
Visited[node] = 1;
for (int j = 0; j < Node[node].size(); j++) {
int nextnode= Node[node][j];
if (Visited[nextnode]) return 0;
}
}
for (int i = 0; i < adjnode.size(); i++) {
int node = adjnode[i];
Visited[node] = 0;
}
//인접하지 않은 node 들끼리 연결되어있는가?
vector<int> notadj;
notadj.push_back(nowidx);
for (int i = 1; i <= V; i++) {
bool add = 1;
for (int j = 0; j < adjnode.size(); j++) {
if (adjnode[j] == i ) {
add = 0;
break;
}
}
if (add) {
notadj.push_back(i);
Visited[i] = 1;
}
}
for (int i = 0; i < notadj.size(); i++) {
int node = notadj[i];
for (int j = 0; j < Node[node].size(); j++) {
int nextnode = Node[node][j];
if (Visited[nextnode]) return 0;
}
}
return 1;
}
CheckNeighbor 함수를 만들었다.
1. 해당 node 에서 인접하는 그룹과 인접하지 않는 그룹으로 나눈다.
2. 각 그룹의 node끼리 서로 연결되어 있는지를 확인한 후 연결되면 0 아니면 1을 리턴한다.
3. node를 V까지 바꿔가며 수행한다.
모든 node에 있어 수행하기 때문에 답은 반드시 맞을 것으로 예상된다.
하지만!!
당연스럽게도 V= 20000, E=200000 의 케이스에서 시간초과가 걸리게 된다.
O(VE)의 횟수를 획기적으로 줄여야했다.
두 번째 접근 방법은 미리 이분화 시킨 그룹에 Node를 차례대로 넣는것이다.
첫 번째 Node 부터 시작하게 된다면 그룹 1에다가 Node 번호 1을 넣는다.
그 후 두 번째 Node를 그룹 1에다가 넣을 수 있는지 본다.(그룹 1에 인접하는 node가 있는지 본다.)
그룹 1에 넣을 수 있다면 넣은 후에 다음 Node를 본다.
만약 넣을 수 없다면 그룹 2에다가 넣을 수 있는지 본다.
그룹 2에 넣을 수 있다면 넣은 후에 다음 Node를 본다.
만약 넣을 수 없다면 이분 그래프를 그릴 수 없는 경우이므로 종료한다.
끝까지 수행했다면 이분 그래프를 완성시킨 경우이므로 1을 return한다.
int CheckGroup(vector<int> * Node,int* Group, int idx, int inputNode) {
for (int i = 0; i < Node[inputNode].size(); i++) {
for (int j = 0; j < idx; j++) {
if (Node[inputNode][i] == Group[j]) {
return 0;
}
}
}
return 1;
}
int Bi(int V, vector<int> Node[20001]) {
int Group1[20001] = { 0 }, Group2[20001] = { 0 };
int idx1 = 0, idx2 = 0;
for (int i = 1; i <= V; i++) {
//printf("INPUT NODE : %d ", i);
if (Node[i].size() == 0) {
Group1[idx1++] = i;
continue;
}
if (CheckGroup(Node,Group1, idx1,i)) {
Group1[idx1++] = i;
continue;
}
if (CheckGroup(Node,Group2, idx2,i)) {
Group2[idx2++] = i;
continue;
}
return 0;
}
return 1;
}CheckGroup함수는 지금 Node가 그룹에 인접하는 node가 있는지를 검사하는 함수이다.
Bi는 이분그래프를 만드는 함수로 Group1과 2에 넣는 역할을 한다.
만약 넣을 수 없는 Node가 있다면 0을 return, 무사히 수행되면 1을 return 한다.
연결되지 않고 혼자 독립적으로 있는 Node는 Group1에 넣는다.
하지만 이 경우 테스트 케이스(25%)에서 잘못된 결과를 내놨다.
(좀 편하게 가나했더니)
왜 틀렸는지는 아직 잘 모르겠다.
뭔가 잘못한게 분명한데, 나중에 더 찾아봐야겠다.
세 번째로 시도한 방법은 BFS를 이용한 방법이다.
BFS 특성상 시각마다 도착할 수 있는 지점이 모두 나오게 된다.
이 때 시각이 달라도 몇 번 더 도착할 수 있는 경우가 있는데 만약 인접한 노드와 도착 시간의 모순이 발생하게되면
어떤 경우에서도 이분 그래프를 그릴 수 없다.(그룹이 두 개밖에 없기 때문)
말이 조금 어려운데, 1 2 3 이 있을 경우 1->2 가 인접하고 2->3이 인접하고 3->1 이 인접한다면
1에서 2로 가는건 1번만에 갈 수도 2번만에 갈 수도 있기 때문에 인접한 경우도, 인접하지 않은 경우도 가능하다.
즉, 1-> 인접(3) -> 인접(2) = 비인접(2) 이어야하는데 1->인접(2) 이기 때문에 모순이 발생하여
1이 있는한 2는 어디 그룹에도 들어갈 수 없게 된다는 뜻이다.
1번 노드 기준으로 BFS 로 탐색하지 않은 노드가 있을 수 있다.
유일성이 만족하지 않기 때문에 연결되지 않은 노드들은 독립적인 그룹으로 생각하여 BFS탐색을 또 수행하면 된다.
int BFS(int V,int idx, vector<int > *Node, int visited[20001]) {
queue<pair<int, int >> q;
q.push(make_pair(idx, 0));
while (!q.empty()) {
int node = q.front().first;
int flag = q.front().second;
visited[node] = flag ;
q.pop();
for (int i = 0; i < Node[node].size(); i++) {
int nextnode = Node[node][i];
if (visited[nextnode]) {
if (flag % 2 == visited[nextnode] % 2)
return 0;
else continue;
}
q.push(make_pair(nextnode, flag+1));
}
}
return 1;
}
코드또한 훨씬 간단해졌다.
queue를 이용한 BFS를 수행하고 메인함수에서는 아직 방문하지 않은 노드들을 기준으로 계속 BFS를 수행하면된다.
물론 TEST CASE가 여러번 돌아야하므로 초기화 해주는 것도 잊지말자.
(사실 논리는 미리 이분한 그룹이랑 똑같은거 같은데 왜 위에건 틀렸지)
전체코드
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
int BFS(int V,int idx, vector<int > *Node, int visited[20001]) {
queue<pair<int, int >> q;
q.push(make_pair(idx, 0));
while (!q.empty()) {
int node = q.front().first;
int flag = q.front().second;
visited[node] = flag ;
q.pop();
for (int i = 0; i < Node[node].size(); i++) {
int nextnode = Node[node][i];
if (visited[nextnode]) {
if (flag % 2 == visited[nextnode] % 2)
return 0;
else continue;
}
q.push(make_pair(nextnode, flag+1));
}
}
return 1;
}
int main() {
// 테스트케이스 수
int k;
scanf("%d", &k);
for (int loop = 0; loop < k; loop++) {
vector<int> Node[20001] = {};
int visited[20001] = { 0 };
// Vertex 개수 Edge 개수
int V, E;
scanf("%d %d", &V, &E);
// Edge 입력
for (int i = 0; i < E; i++) {
int n1, n2;
scanf("%d %d", &n1, &n2);
Node[n1].push_back(n2);
Node[n2].push_back(n1);
}
//BFS
for (int i = 1; i <= V; i++) {
if (!visited[i]) {
if (!BFS(V, i, Node, visited)) {
printf("NO\n");
break;
}
}
if (i == V) {
printf("YES\n");
}
}
}
return 0;
}
'알고리즘' 카테고리의 다른 글
| 백준 9663 N-Queen - C언어 DFS (0) | 2021.03.05 |
|---|---|
| 백준 1405 미친 로봇 c++ 풀이 - DFS (0) | 2021.03.03 |
| 백준 11053 가장 긴 증가하는 부분 수열 C++ (0) | 2021.02.19 |
| 백준 14620 꽃길 - C++ DFS (0) | 2021.02.17 |
| 백준 2178 미로탐색 - C++ BFS (0) | 2021.02.12 |