BOJ 2606 : 바이러스 (Linked List)

삼성 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

 

삼성 SW A형 입문으로 대부분 풀어보게 되는 바이러스 문제를 Linked List로 풀어보자.

N이 작기 때문에 보통 100 x 100 2차원 배열을 선언해서 그래프를 만들지만,

B형 연습을 위해 Linked List를 만들어 보자.

 

Linked List는 메모리 풀 방법으로 만들어야 한다.

 

먼저 예제 입력을 보자. 

7 /* 총 7개의 head가 존재 */
6 /* 6번의 입력 */
1 2 /* 1번과 2번 node 연결 */
2 3
1 5
5 2
5 6
4 7

연결이 양방향이므로 연결해야하는 링크는 총 6 x 2 = 12가 된다.

 

NODE는 아래와 같이 구성하고 HEAD와 POOL을 선언하자.

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

NODE HEAD[110]; 
NODE POOL[110 * 110]; 
int pcnt; 

이러면 모든 HEAD들은 최초에 0(NULL)을 가르키게 된다.

 

다음으로 예제 입력의 3, 4번째 줄의 1 2 와 2 3을 연결해보자.

 

1 2를 입력하면, HEAD의 1에 node 2가 연결되고,

양방향 연결이므로 HEAD의 2에 node 1이 연결된다.

 

이 상태에서 2 3 을 입력하면,

HEAD 2에 3이 추가되어 1 3이 만들어지고

HEAD 3에는 2가 추가된다.

 

최종적으로 노드는 아래와 같을 것이다.

 

하지만, 이렇게 구현하는 것은 귀찮다.

왜냐하면, HEAD의 가장 끝에 node를 연결해줘야 하는 것은,

HEAD의 가장 끝 node를 저장해둬야 한다는 것을 뜻한다.

여러 Linked List 구현 코드를 보면 TAIL을 두어서 TAIL에 node를 붙이는데, 

어짜피 특정 HEAD만 완전 탐색을 하는 것이 목표이기 때문에 순서를 지킬 필요가 없다.

 

실제로 구현은 아래면 충분하다.

 

1) node를 하나 pool에서 가져오고, 값을 입력한다.

2) node의 next를 head가 가르키는 곳에 연결한다.

3) head를 새로운 node에 연결한다.

 

실제 node를 연결해주는 구현 코드를 보자.

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

위 방식대로 하면 1 2 입력, 2 3 입력이 아래 처럼 바뀐다.

HEAD 2에 새로 들어올 node 3이

HEAD 2가 처음 가르키고 있던 1을 연결하고

( HEAD 2 -> node 1 / node 3 -> node 1 의 상태가 된다.)

다시 HEAD 2가 새로운 node를 가르키게 하면

( HEAD 2 -> node 3 / node 3 -> node 1 의 상태가 된다.)

 

순서는 거꾸로지만, 문제를 푸는데는 전혀 지장이 없고, 구현도 간단하다.

 

최종적으로 왼쪽이 아닌, 오른쪽 방식대로 Link가 만들어 진다.

 

실제 output 함수를 만들어서 연결이 제대로 되었는지 확인해보자.

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

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

 

for (NODE *p = HEAD[head].next; p; p = p->next)

 

NODE *p = HEAD[head].next → 최초의 node를 가져온다.

p → p가 NULL이면 종료.

p = p->next → p가 NULL이 아니면 p = p->next로 다음 node로 이동.

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

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

NODE HEAD[110]; 
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++) visit[i] = 0;
    
    ANSWER = 0;
}

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

	nd->next = HEAD[p].next;
	HEAD[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;
}

 

링크드 리스트 순서를 지켜야하는 경우, 즉 TAIL을 사용하면 코드가 복잡해지는데,

순서를 유지해야 하는 경우가 아니라면 위의 구현이 훨씬 간단하고 성능도 좋다.