Baekjoon1707-이분 그래프

백준 사이트 1707 - 이분그래프 문제입니다.

1. 문제

https://www.acmicpc.net/problem/1707

---

2. Input , Output

---

3. 분류 및 난이도

BFS문제입니다.
백준에서는 Gold4난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 다 풀고 보니 기준을 뭘로하느냐에 따라 이 문제가 hell이 될 수 있고 eazy가 될 수 있습니다.
• 그래프 문제상 반례를 찾기 힘들어서 처음에 기준을 잘 잡아야합니다.
• 처음에는 방문처리를 위해 배열을 한 개 더 두었는데, 그거 때문에 틀렸습니다.
  • 게시판에 있는 반례 포함 다 돌아갔으나 왜 틀렸는 지 모름..
• 처음부터 다시해서 배열하나로 방문처리와 색에 대한 정보를 저장했습니다.
  • 대부분이 이렇게 풀었습니다. 저도 이렇게 푸니 맞긴 하던데.. 위의 코드는 왜 틀렸는지..

---

5. code

c++

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;


int map[20001] = { 0 };
int t, v, e;

bool BFS(int start, vector<int> vec[])
{
	queue<int> q;
	q.push(start);
	map[start] = 1;
	while (!q.empty())
	{
		int curr = q.front();
		q.pop();
		for (int i = 0; i < vec[curr].size(); ++i)
		{
			int ver = vec[curr][i];
			if (map[ver] != 0)//방문기록이 있음.
			{
				if (map[curr] == map[ver])//색이 같다.
				{
					return false;
				}
			}
			else
			{
				q.push(ver);
				map[ver] = 3 - map[curr];
			}
		}

	}
	return true;
}

void Input()
{
	cin >> t;
	for (int i = 0; i < t; ++i)
	{
		memset(map, 0, sizeof(map));
		bool result = true;
		vector<int> vec[20001];
		cin >> v >> e;
		int first = 0;
		int second = 0;
		for (int j = 0; j < e; ++j)
		{
			cin >> first >> second;
			vec[first].push_back(second);
			vec[second].push_back(first);
		}
		for (int i = 1; i <= v; ++i)
		{
			if (map[i] == 0)
			{
				result = BFS(i, vec);
				if (result == false)
				{
					cout << "NO\n";
					break;
				}
			}
		}
		if (result)
			cout << "YES\n";

	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();

	return 0;
}

python

from collections import deque
def BFS(start,li,mapz):
    queue = deque([start])
    mapz[start] = 1
    while queue:
        curr = queue.popleft()
        for i in range (0,len(li[curr])):
            ver = li[curr][i]
            if mapz[ver] != 0:
                if mapz[curr] == mapz[ver]:
                    return False
            else : 
                queue.append(ver)
                mapz[ver] = 3-mapz[curr]
    return True

t = int(input())

for i in range (0,t):
    mapz = [0] * 20001
    result = True
    li = []
    for j in range (0,20001):
        line = []
        li.append(line)

    v,e = map(int,input().split())
    for j in range (0,e):
        first,second = map(int,input().split())
        li[first].append(second)
        li[second].append(first)
        
    for i in range(1,v+1):
        if mapz[i] == 0 :
            result = BFS(i,li,mapz)
            if result == False :
                print("NO")
                break
    if result : 
        print("YES")

---

6. 후기

삽질을 너무 많이 한 문제입니다.