BOJ 1707 : 이분 그래프 (vector)

삼성 B형 전체 링크

 

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

 

 

메모리 풀을 이용하였던 이분 그래프 문제를 vector를 이용해 풀어보자.

 

메모리 풀을 위해 사용하였던 아래의 구조체와 HEAD, POOL, pcnt는 더이상 필요가 없다.

/* before */

typedef struct st
{
	int node;
	struct st *next;
}NODE;

NODE HEAD[20200];
NODE POOL[202000 * 2];
int pcnt;

 

NODE 구조체에 필요한 것은 정수 node였으므로, 아래의 head에 대한 vector들만 선언하면 된다.

/* after */

vector<int> HEAD[20200];

 

메모리 풀을 초기화하기 위해 pcnt는 0으로 만들었고, HEAD의 next를 NULL로 가르켜 초기화하였다.

그리고 check 변수를 초기화 하였다.

/* before */

void init()
{
	pcnt = 0; /* 메모리 풀 초기화 */
	for (int i = 1; i <= V;i++) HEAD[i].next = 0, check[i] = 0;
}

 

vector를 사용하기 때문에 pcnt를 초기화할 필요가 없고, clear() 메서드를 이용해 vector를 초기화하면 된다.

/* after */

void init()
{
	for (int i = 1; i <= V; i++) HEAD[i].clear(), check[i] = 0;
}

---

vector를 순회하기 위해서는 vector의 size() 메서드로 크기를 알면 된다.

그리고 배열처럼 순회하면 된다.

 

따라서 

 

for (NODE *p = HEAD[node].next; p; p = p->next) /* NULL이 될 때 까지 순회 */

→ for (int i = 0; i < HEAD[node].size(); i++) /* vector의 size 만큼 순회 */

 

로 바뀐다.

 

배열처럼 순회하면 되기 때문에 굳이 iterator를 사용할 필요가 없다.

또한 p->node는 각 vector의 i 번째 원소를 모두 순회하면 되므로,

 

p->node → HEAD[node][i] 

 

로 바꾸면 된다.

int DFS(int node, int color)
{
	check[node] = color;

	/* 
	before 
	for (NODE *p = HEAD[node].next; p; p = p->next)
	*/

	/* after */
	for (int i = 0; i < HEAD[node].size(); i++)
	{
		/* p->node => HEAD[node][i] */
		if (check[HEAD[node][i]] == color) return 0;
		if (!check[HEAD[node][i]])
		{
			if (!DFS(HEAD[node][i], 3 - color)) return 0;
		}
	}

	return 1;
}

 

조금 더 최적화를 하자면 아래의 size 변수에 vector.size()를 담아두는 것이 좋다.

for문을 순회할 때 마다, size()가 호출되기 때문이다.

int size = HEAD[node].size();
for (int i = 0; i < size; i++)
{ ... }

---

링크드 리스트를 연결하기 위해 Make 함수를 이용하였다.

/* before */

void Make(int p, int c)
{
	NODE *nd = &POOL[pcnt++];

	nd->node = c;

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

 

main에서 입력을 받으면서 각 node를 연결하였다.

/* before */

for (int i = 0; i < E;i++)
{
	int p, c;

	scanf("%d %d", &p, &c);
	Make(p, c);
	Make(c, p);
}

 

Make 함수가 하는 역할 자체가 vector의 push_back() 메서드이므로, 한 줄로 대체할 수 있다.

/* after */

for (int i = 0; i < E; i++)
{
	int p, c;

	scanf("%d %d", &p, &c);

	HEAD[p].push_back(c);
	HEAD[c].push_back(p);
}

 

최종 코드는 아래와 같다.

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int K, V, E;

vector<int> HEAD[20200];

int check[20200];

void init()
{
	for (int i = 1; i <= V; i++) HEAD[i].clear(), check[i] = 0;
}

int DFS(int node, int color)
{
	check[node] = color;

	int size = HEAD[node].size();
	for (int i = 0; i < size; i++)
	{
		/* p->node => HEAD[node][i] */
		if (check[HEAD[node][i]] == color) return 0;
		if (!check[HEAD[node][i]])
		{
			if (!DFS(HEAD[node][i], 3 - color)) return 0;
		}
	}

	return 1;
}

int main(void)
{
	scanf("%d", &K);

	for (int tc = 1; tc <= K; tc++)
	{
		int flag;
		scanf("%d %d", &V, &E);

		init();

		for (int i = 0; i < E; i++)
		{
			int p, c;

			scanf("%d %d", &p, &c);

			HEAD[p].push_back(c);
			HEAD[c].push_back(p);
		}

		flag = 0;
		for (int i = 1; i <= V; i++)
		{
			if (!check[i])
			{
				flag = DFS(i, 1);
				if (!flag) break;
			}
		}

		if (flag) printf("YES\n");
		else printf("NO\n");
	}

	return 0;
}