[Algorithm][C++] BOJ 2606: 바이러스 (head Linked List)

url: https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

풀이 핵심

1. bfs 문제

 

2. 문제는 매우 간단하지만 Pro 시험에서 Linked List 자료구조는 필수로 구현할 줄 알아야 하므로 Linked List를 이용해 풀이해보고자 한다.

 

3. Linked List는 추가 연결이 필요할 때 연결 끝 부분 (Tail) 에 추가해줘야 하는 경우, 즉 list의 연결 순서가 중요할 경우 tail을 알 수 있도록 해서 tail 다음에 추가로 노드 연결을 한다. (Head, Tail로 구현하기) 허나 이 문제는 추가 연결 시 끝 부분 (Tail) 에 연결할 필요가 없으므로 (순서가 중요하지 않으므로) 다음과 같이 구조체와 연결 함수 (make)를 만들면 된다.

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

NODE HEAD[MAXV];
NODE POOL[MAXE * 2];

void make(int p, int c) {
	NODE* nd = &POOL[pcnt++];
	nd->node = c;

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

일반적으로 사용하는 동적 할당 malloc을 사용하지 않은 이유는 delete 하는데 번거로움이 있기 때문이다. 위와 같이 사용할 메모리를 전역으로 미리 만들어 필요할때마다 가져오는 방식으로 사용하는 것이 더욱 효과적이다.

 

4. bfs 구현하는 것은 전체 코드를 참고하자.

 

코드

#include <cstdio>
#define MAXN	101

int N, M, ans;

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

NODE HEAD[MAXN];
NODE POOL[MAXN*MAXN];
int visit[MAXN];
int pcnt;

void make(int p, int c) {
	NODE* nd = &POOL[pcnt++];
	nd->node = c;
	
	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

int queue[MAXN*MAXN];
int fr, re;

void bfs() {
	int cur;

	fr = re = 0;

	queue[re++] = 1;
	visit[1] = 1;

	while (fr != re) {
		cur = queue[fr++];
		
		for (NODE* p = HEAD[cur].next; p; p = p->next) {
			if (visit[p->node] == 0) {
				ans++;
				queue[re++] = p->node;
				visit[p->node] = 1;
			}
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int p, c;
		scanf("%d %d", &p, &c);
		make(p, c);
		make(c, p);
	}
	bfs();
	printf("%d", ans);
	return 0;
}