[dfs] 1707 이분 그래프

1707 이분 그래프

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 1707 이분 그래프

const int MAX = 20000;

// v : 정점의 개수 
// e : 간선의 개수
int v, e;

// 인접 리스트
vector<int> 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" << '\n';
		}
		else{
			cout << "NO" << '\n';
		}
	}
}

풀이코드 (틀림)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 1707 이분 그래프

const int MAX = 20000;

// v : 정점의 개수 
// e : 간선의 개수
int v, e;

// 인접 리스트
vector<int> 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" << '\n';
		}
		else{
			cout << "NO" << '\n';
		}
	}
}

해설

---

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

 

풀이

 

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

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

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

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

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

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

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

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