[삼성역량테스트PRO] Linked List

 

연결리스트 라고도 한다.

 

전공자라면 대학교 1,2학년때쯤 자료구조 과목에서 배우는 과목이지만, 

 

코딩테스트에서 상황에 맞춰 바로 써먹기는 어려울 수 있다.

 

특히 역량테스트에서는 Adv보다 Pro 등급에서 필수적으로 알아야 하는 개념이다.

 

 

---

 

 

구조

 

https://opentutorials.org/module/1335/8821

 

List는 노드들의 모임이다.

 

이 노드들은 기본적으로 값(Data field) 과 다음노드의 주소(Link field)를 가지고 있어서

연결된 값의 모임을 만들 수 있다.

 

다음노드의 주소는 아는데 첫 노드의 주소는 어떻게 알까? -> HEAD

 

 

---

 

 

종류

 

1. 단방향 연결리스트 _ Singly Linked List

• 단순히 한쪽 방향으로만 연결되어 있는 연결리스트이다.

 

2. 양방향(이중) 연결리스트 _ Doubly Linked List

• 양쪽 방향으로 연결된 양방향 연결리스트이다.
• 노드가 생성되고 이전 노드의 포인터는 새로 생성된 포인터를 가리킨다.

 

3. 원형 연결리스트 _ Circular Linked List

• 처음과 끝이 연결되어 있는 연결리스트이다.

 

---

 

활용

 

STL - List 구조 자체가 Linked List 인걸 활용할 수 있다.

 

이는 vector, deque와 다르게 멤버함수에서 정렬(sort, merge), 이어붙이기(splice)가 있다.

 

원소를 탐색할때, 임의 접근(at(), [])은 불가능하고, 양방향 반복자 (++ --) 를 이용해서 탐색한다.

#include<list>
using namespace std;

//선언
list<int> lt1;
list<char> lt2; 
list<string> lt3;
list<int> lt4(5); //int형의 default(0)으로 초기화된 원소 5개를 가진 list 생성
list lt; //비어있는 list 컨테이너 lt
list lt(10); //0으로 초기화된 원소 10개를 가진 list 생성
list lt(3,2); //2로 초기화 된 원소 3개를 가진 list 생성

//추가 및 삭제
lt1.push_front(5) //가장 앞 노드에 5를 넣는다
lt1.pop_front(); //앞 노드에서 꺼낸다
lt1.push_back(5); //가장 뒤 노드에 5를 넣는다
lt1.pop_back(); //뒤 노드에서 꺼낸다
lt1.insert(begin_iter, 2); //iterator가 가리키는 부분 앞에 원소를 추가
lt1.erase(end_iter); //iterator가 가리키는 부분에 원소를 삭제
lt1.clear(); //리스트비우기
lt1.unique(); //연속하는 중복된 원소 제거

//반복자
list<int>::iterator begin_iter = lt1.begin();
list<int>::iterator end_iter = lt1.end();
begin_iter++;
end_iter--;

//조회
lt1.empty(); //비어있는지 여부 확인
lt1.front(); //가장 앞 원소 
lt1.back(); //가장 뒤 원소
lt1.size(); //사이즈를 반환한다.

//정렬
lt1.sort(); //리스트 정렬하기 (오름차순)
	- 정렬을 한 후 unique를 쓰면 중복된 원소 모두 제거 가능함
lt1.sort(greater<int>()); // 리스트 정렬하기 (내림차순)
lt1.reverse() //리스트 뒤집기

//전체 출력하기
lt1<int>::iter Iter = lt1.begin();
while(Iter != lt1.end()){
	cout<<*(Iter++)<<" ";
}

//잘라붙이기 (lt1의 end 위치에 lt2 를 붙임
lt1.splice(lt1.end(), lt2, lt2.begin(), lt2.end());

 

하지만 linked list 는 배열, vector 등의 자료구조로 구현 가능하다.

 

---

문제

2606번: 바이러스

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

7
6
1 2
2 3
1 5
5 2
5 6
4 7

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

4

 

풀이 1

 

이 문제는 linked list를 사용하지 않고 기본적인 탐색만 해도 풀리는 문제지만 linked list를 굳이 사용해보자.

 

문제의 그림에 그래프가 그려져있다. 결국은 1과 연결되어있는 요소들을 탐색을 통해 찾아야 한다.

 

linked list 를 직접 만들어서 풀어보자.

 

코드의 구성은 아래와 같다.

1. node struct 생성
2. node 생성 함수 구현
3. branch 생성 함수 구현
4. bfs 탐색 구현

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct node { // node struct 생성
	int number;
	struct node* next;
}node;

struct node* new_node(int num) { // node 생성함수 구현
	struct node* n = (struct node*) malloc(sizeof(struct node)); //메모리할당
	if (n != NULL) { //malloc 성공시에만 
		n->next = NULL; 
		n->number = num;
	}
	return n;
}

void add_edge(int v1, int v2, struct node* vertex_array) { //branch 생성함수
	struct node* v2_node = new_node(v2); // v2_node 이름의 node를 생성한다.
	struct node* ptr = (struct node*)malloc(sizeof(struct node)); // branch를 만들기위한 메모리
	if (vertex_array[v1].next == NULL) { //비어있다면
		vertex_array[v1].next = v2_node; //연결시켜준다.
	}
	else { //차있다면
		if (ptr != NULL) {
			ptr->next = vertex_array[v1].next; // vertex[v1]의 next 연결 요소 할당 
			while (ptr->next->next != NULL)//ptr의 다음 요소가 없을 때까지 계속 next 
			{
				ptr->next = ptr->next->next;
			}
			ptr->next->next = v2_node;
		}
	}
}

void bfs_virus(int n, struct node* vertex) { //그래프를 bfs로 탐색
	int infected = 0;
	queue <int> q;
	bool* visited = new bool[n + 1]; //방문여부 배열 생성
	for (int i = 0; i < n + 1; i++) //방문여부 false 로 초기화
		visited[i] = false;
	struct node* ptr = (struct node*)malloc(sizeof(struct node));
	q.push(1);
	while (!q.empty())
	{
		int value = q.front();;
		ptr = vertex[value].next;
		while (ptr != NULL) //value와 연결되어 있는 요소 queue에 추가
		{
			if (visited[ptr->number] == false) //방문하지 않은 경우만 push
				q.push(ptr->number);
			ptr = ptr->next;
		}
		visited[value] = true; // 방문 true로 변경
		q.pop();
	}

	for (int i = 2; i <= n; i++) {
		if (visited[i] == true) infected++;
	}
	cout << infected;
}

int main() {
	int n, m;
	cin >> n;
	cin >> m;
	struct node* vertex = new struct node[n + 1];
	for (int i = 0; i <= n; i++) {
		vertex[i].next = NULL;
		vertex[i].number = i + 1;
	}
	for (int i = 0; i < m; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		add_edge(v1, v2, vertex);
		add_edge(v2, v1, vertex); //무방향 그래프이므로 각 노드에 따로 추가해줌
	}
	bfs_virus(n, vertex);
	return 0;
}

---

 

풀이 2

 

STL을 사용할 수 있는 코딩테스트라면 Linked List 를 풀이1과 같이 일일히 구현할 필요는 없다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
vector<int> a[1001];
bool visited[1001];
int infected = 0;

void bfs(int start) {
    queue<int> q;
    memset(visited, false, sizeof(visited));
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int i = 0; i < a[node].size(); i++) {
            int next = a[node][i];
            if (visited[next] == false) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    bfs(1);
    cout << infected << "\n";
    return 0;
}

 

 

---

 

풀이 3

 

배열을 써서 풀이가가능하다.

 

#include <iostream>
#include <queue>
using namespace std;

int V, E;
const int MAX = 101;
int new_map[MAX][MAX] = {0, };
bool visited[MAX] = {0, };
int ans = 0;
queue<int> q;

void bfs(int v){
    visited[v] = true;
    q.push(v);
    while(!q.empty()){
    	v=q.front();
        q.pop();
        for(int i=1; i<=v; i++){
        	if(visited[i] == 0 && new_map[v][i] == 1){
            	q.push(i);
                visited[i] = true;
                ans++;
            }
        }
    }
}

int main(){
	cin >> V >> E;
    int a,b;
    for(int i=0; i<E; i++){
        cin >> a>> b;
        new_map[a][b] = 1;
        new_map[b][a] = 1;
    }
    bfs(1);
    cout << ans;
}