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

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

2606번: 바이러스

 

풀이 핵심

1. 본 문제는 bfs 문제로 head 만을 이용한 linked list로 쉽게 풀 수 있다. 기본적으로 list의 들어오는 순서가 중요한 경우가 많으므로 이번엔 tail을 가지고 있는 linked list로 풀이해보고자 한다. 풀이에 대한 내용은 head만을 이용한 linked list 링크를 참조하자

 

2. head, tail을 가지고 있는 linked list 구조체

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

NODE HEAD[MAXN];
NODE TAIL[MAXN];
NODE POOL[MAXN * MAXN];

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

	if (HEAD[p].next == NULL && TAIL[p].next == NULL) {
		HEAD[p].next = TAIL[p].next = nd;
	}
	else {
		TAIL[p].next->next = nd;
		TAIL[p].next = nd;
	}
}

 

코드

#include <cstdio>
#define MAXN	101

int N, M, ans;
struct NODE {
	int node;
	NODE* next;
};

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

int visit[MAXN];

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

	if (HEAD[p].next == NULL && TAIL[p].next == NULL) {
		HEAD[p].next = TAIL[p].next = nd;
	}
	else {
		TAIL[p].next->next = nd;
		TAIL[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;
}