연결리스트 라고도 한다.
전공자라면 대학교 1,2학년때쯤 자료구조 과목에서 배우는 과목이지만,
코딩테스트에서 상황에 맞춰 바로 써먹기는 어려울 수 있다.
특히 역량테스트에서는 Adv보다 Pro 등급에서 필수적으로 알아야 하는 개념이다.
구조
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번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 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 를 직접 만들어서 풀어보자.
코드의 구성은 아래와 같다.
- node struct 생성
- node 생성 함수 구현
- branch 생성 함수 구현
- 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;
}
'알고리즘 문제풀이 > 삼성역량테스트PRO' 카테고리의 다른 글
| [삼성역량테스트PRO] Binary Search (0) | 2022.04.15 |
|---|---|
| [삼성역량테스트PRO] 시험 (멀티캠퍼스 나들이) (0) | 2022.03.20 |
| [삼성역량테스트PRO] Pro시험 팁 (3) | 2022.03.18 |
| [삼성역량테스트PRO] 삼성코테란?+Pro준비 (3) | 2022.03.12 |
댓글