1707 이분 그래프

1707 이분 그래프

문제 (1111)

풀이코드

#include #include #include #include using namespace std; // 1707 이분 그래프 const int MAX = 20000; // v : 정점의 개수 // e : 간선의 개수 int v, e; // 인접 리스트 vector adjList[MAX + 1]; // color[i] : color[i] 가 0이면 방문 안함. 1이면 1번 그룹. -1 면 2번 그룹 int color[MAX + 1]; // dfs(현재 노드, 현재 노드의 색) bool dfs(int currentNode, int c){ color[currentNode] = c; for(int i = 0; i < adjList[currentNode].size(); i++){ int nextNode = adjList[currentNode][i]; // 다음 노드를 방문하지 않았다면 if(color[nextNode] == 0){ // 다음 노드로 이어나갔을 때, 하나라도 이분 그래프가 아니면 false // 다음 노드는 현재 노드의 그룹과 반대여야 하므로 c * -1 이 다음 노드의 그룹 if(dfs(nextNode, c * -1) == false){ return false; } } // 다음 노드와 현재 노드의 그룹이 같으면 false else if(color[currentNode] == color[nextNode]){ return false; } } return true; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int k; cin >> k; while(k--){ cin >> v >> e; // 테스트 케이스 마다 color 와 adjList 초기화 fill_n(color, MAX+1, 0); for(int i = 1; i <= v; i++) adjList[i].clear(); // 입력 for(int i = 0; i < e; i++){ int from, to; cin >> from >> to; adjList[from].push_back(to); adjList[to].push_back(from); } // 모든 node 에서 시작해본다. bool ok = true; for(int i = 1; i <= v; i++){ if(color[i] == 0){ if(dfs(i, 1) == false){ ok = false; } } } if(ok){ cout << "YES" << '

'; } else{ cout << "NO" << '

'; } } }

풀이코드 (틀림)

더보기 #include #include #include #include using namespace std; // 1707 이분 그래프 const int MAX = 20000; // v : 정점의 개수 // e : 간선의 개수 int v, e; // 인접 리스트 vector adjList[MAX + 1]; // color[i] : color[i] 가 0이면 방문 안함. 1이면 1번 그룹. -1 면 2번 그룹 int color[MAX + 1]; bool dfs(int currentNode, int prevNode){ // 첫 시작이면, 1번 그룹 if(prevNode == 0){ color[currentNode] = 1; } // 그룹이 정해져있으면 그대로 else if(color[currentNode] != 0){ color[currentNode] = color[currentNode]; } // 방문하지 않았고, 그룹이 정해져있지 않으면 이전 노드의 반대 그룹 else{ color[currentNode] = color[prevNode] * - 1; } for(int i = 0; i < adjList[currentNode].size(); i++){ int nextNode = adjList[currentNode][i]; if(color[currentNode] * color[nextNode] == 1) return false; // 다음 노드를 방문했었다면, 생략 if(color[nextNode] != 0) continue; dfs(nextNode, currentNode); } return true; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int k; cin >> k; while(k--){ cin >> v >> e; fill_n(color, MAX+1, 0); for(int i = 0; i < e; i++){ int from, to; cin >> from >> to; adjList[from].push_back(to); adjList[to].push_back(from); } for(int i = 1; i <= v; i++){ sort(adjList[i].begin(), adjList[i].end()); } if(dfs(1, 0)){ cout << "YES" << '

'; } else{ cout << "NO" << '

'; } } }

해설

적용한 레시피 / 방법론 + 접근법

풀이

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 처음 문제에 접근하였을 때, dfs 함수가 false 를 리턴하는 경우를 단순하게만 생각하였음.

- 현재 노드와 다음 노드가 다른 그룹일 때만, false 를 리턴하였었다.

- 강의의 코드를 보면, 현재 노드에서 다음 노드로 이어져나갈 때, 어디 하나라도 false 가 나오면 다시 false 를 리턴하도록 한다.

2. 테스트 케이스마다 초기화 시키지 않았다.

3. 모든 노드에서 시작해보지 않았었다.

4. 노트에 더 고민해보지 않고 코딩에 돌입했다.

- 알고리즘을 공책 속에 명확히 그려두고 실제 코딩에 돌입했어야 했다. 처음 했던 코드 처럼, 추상적이고 난잡한 논리만으로 코드를 짜게 되면 분명히 헷갈리게 되고 실수가 발생한다.

from http://private-k.tistory.com/136 by ccl(A) rewrite - 2021-10-02 19:26:29