BOJ 2606 : 바이러스 (Linked List Tail ver)

삼성 B형 전체 링크

삼성 C형 전체 링크

 

www.acmicpc.net/problem/2606

 

참고

- 메모리 풀 Memory Pool

- 메모리 풀 vs malloc 속도 비교

- 링크드 리스트 Linked List

- 링크드 리스트 Linked List Tail ver

- 더블 링크드 리스트 Double Linked List
- 더블 링크드 리스트 Double Linked List Tail ver

 

Linked List는 HEAD만으로도 충분하지만, 가~~~끔 들어온 순서를 고려해야하는 경우가 있다.

이 때는 TAIL을 써서 끝 node의 주소를 기억해두면 된다.

 

Make 함수를 보자.

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;
	}
}

 

HEAD만 필요할 때 간단했던 구현에서 if와 else가 추가되었다.

끝 node에 node를 이어줘야하는 경우는 최초의 node 인지 검사가 필요하다.

TAIL은 처음에 NULL을 가르키게 되기 때문이다.

 

따라서 신규 node가 들어오면 HEAD와 TAIL의 next는 신규 node를 가르키게 한다.

다음 새로운 신규 node가 들어오면 이 node는 

TAIL이 가르키고 있던 node의 다음에 연결해야 된다.

따라서 TAIL[p].next(TAIL이 가르키고 있던 node) -> next (의 다음 node) 는 새로운 node;

그리고 TAIL은 다시 새로운 node를 가르켜야 하므로 TAIL[p].next = nd; 가 된다.

 

output 함수로 결과를 확인하면 순서대로 잘 들어온 것을 확인 할 수 있다.

전체 코드는 아래와 같다.

#include <stdio.h>

int N, M, ANSWER;
typedef struct st
{
	int node;
	struct st *next;
}NODE;

NODE HEAD[110];
NODE TAIL[110]; /* 끝 주소를 저장할 TAIL 선언 */
NODE POOL[110 * 110];
int pcnt;

int visit[110];

void init(int n) /* 바이러스 문제에서 init은 필요 없지만, tc가 여러 개일 경우 필요 */
{
	pcnt = 0;
	for (int i = 1; i <= N;i++) HEAD[i].next = 0; /* 1부터 N head 초기화 */
    for (int i = 1; i <= N;i++) TAIL[i].next = 0; /* 1부터 N head 초기화 */
	for (int i = 1; i <= N;i++) visit[i] = 0;
	
	ANSWER = 0;
}

void Make(int p, int c)
{
	NODE *nd = &POOL[pcnt++]; /* POOL에서 메모리를 가져온다 */ 
	nd->node = c; /* node에 값을 설정. */

	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[110 * 110];
int wp, rp;

void BFS()
{
	int out;

	wp = rp = 0;

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

	while (wp > rp)
	{
		out = queue[rp++];

		for (NODE *p = HEAD[out].next; p; p = p->next)
		{
			if (visit[p->node] == 0)
			{
				visit[p->node] = 1;
				ANSWER++;
				queue[wp++] = p->node;
			}
		}
	}
}

void outputHead(int head)
{
	printf("head %d : ", head);

	for (NODE *p = HEAD[head].next; p; p = p->next) printf("%d ", p->node);
	putchar('\n');
}

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

	init(N); /* B형 tc가 여러 개인 경우 대비 */

	for (int i = 0; i < M; i++)
	{
		int p, c;
		scanf("%d %d", &p, &c);

		Make(p, c);
		Make(c, p);
	}

	//for (int i = 1; i <= N; i++) outputHead(i);

	BFS();

	printf("%d\n", ANSWER);

	return 0;
}

---

결론 

 

HEAD에서의 Make보다 구현량도 늘어나고, if else를 매번 체크해야하므로 성능도 떨어졌다.

void Make(int p, int c)
{
	NODE *nd = &POOL[pcnt++]; //노드를 하나 선언하고 MEMORY에서 당겨온다. 
	nd->node = c; //NODE에 값을 설정.

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

 

특히 TAIL[p].next->next = nd; 같은 코드는 포인터에 익숙하지 않으면 사용하기 힘들다.

또한 init에서 TAIL도 NULL로 초기화해주는 번거로움이 있다.

 

지금까지 B형에서 순서까지 지켜야 하는 경우는 딱 1번 봤다. 

순서를 지켜야하는 경우는 거의 없으므로 시간이 없다면 HEAD만 필요한 방법만 익혀두자.