기초 자료구조 정리(리스트, 그래프, 트리)

리스트(List)

• 연결 리스트와 같이 순서가 있는 자료구조
• C에선 구조체를 이용해 구현 가능
• C++에선 #include <list> 를 통해 사용 가능
• 상황에 따라 배열보다 효율적으로 문제를 풀 수 있음
• std::list<T>
• std::list<T>::iterator

#include <stdio.h>
#include <list>
using namespace std;

int main(){
	list<int> lt;
	list<int>::iterator iter = lt.begin();
	int n, m;
	scanf("%d %d", &n, &m);

	for(int i=1;i<=n;i++)
		lt.push_back(i);
	iter++;
	printf("<");
	while(lt.size() != 1){
		if(iter == lt.end()) iter = lt.begin();
		for(int i=1;i<m;i++){
			iter++;
			if(iter == lt.end()) iter = lt.begin();
		}
		printf("%d, ", *iter);
		iter = lt.erase(iter);
	}
	
	printf("%d>", *lt.begin());
}

BOJ 1158 조세퍼스 문제

 

#include <stdio.h>
#include <list>
#include <utility>
#define N 1002
using namespace std;

int main(){
	list<int> lt;
	list<int>::iterator iter;
	pair<int, int> num[N];
	int n, tmp;

	scanf("%d", &n);
	for(int i=1;i<=n;i++){
		int a;
		scanf("%d", &a);
		lt.push_back(a);
	}

	iter = lt.begin();
	for(int i=1;i<=n;i++){
		num[i].first = i;
		num[i].second = *iter;
		iter++;
	}

	iter = lt.begin();

	while(lt.size() != 0){
		tmp = *iter;

		for(int i=1;i<=n;i++){
			if(num[i].second == *iter) {
				printf("%d ", num[i].first);
				num[i].first = 0;
				num[i].second = 0;
				break;
			}
		}

		iter = lt.erase(iter);

		if(tmp > 0){
			if(iter == lt.end()) iter = lt.begin();
			for(int i=1;i<tmp;i++) {
				iter++;
				if(iter == lt.end()) iter = lt.begin();
			}
		} else {
			for(int i=tmp;i<0;i++) {
				if(iter == lt.begin()) iter = lt.end();
				iter--;
			}
		}
	}
	return 0;
}

BOJ 2346 풍선 터뜨리기 (돌아가긴 하지만 해결 못함)

 

그래프(Graph)

• 정점(Vertex, Node)와 간선(Edge)로 구성
• 방향성 / 비방향성
• 인접 행렬 / 인접 리스트
• 비방향성 그래프를 인접 행렬로 표현할 경우, 대칭으로 나타남.

#include <stdio.h>
#include <queue>
#define N 1001
#define M 10001
using namespace std;

bool visited[N] = {};
int adj[N][M] = {};

int dfs(int x);
int bfs(int x);
int main(){
	int n, m, v;
	scanf("%d %d %d", &n,&m,&v);

	for(int i=0;i<m;i++){
		int a, b;
		scanf("%d %d", &a, &b);
		adj[a][b]++;
		adj[b][a]++;
	}

	dfs(v);
	puts("");
	fill(visited, visited+N, 0);
	bfs(v);

}

int dfs(int x){
	visited[x] = true;
	printf("%d", x);
	for(int j=1;j<M;j++){
		if(adj[x][j] != 0){
			if(!visited[j]){
				printf(" ");
				dfs(j);
			}
		}
	}
}

int bfs(int x){
	queue<int> q;
	visited[x] = true;
	q.push(x);
	
	while(!q.empty()){
		for(int i=1;i<M;i++){
			if(adj[q.front()][i] != 0 && !visited[i]){
				q.push(i);
				visited[i] = true;
			}
		}
		printf("%d ", q.front());
		q.pop();
	}
}

BOJ 1260 DFS와 BFS (인접 행렬)

 

트리(Tree)

• Cycle(순환)이 없는 연결 그래프
• n개의 정점, n-1개의 간선
• 각 정점간의 경로 유일

#include <stdio.h>
#include <vector>
#define N 100002
using namespace std;

vector<int> v[N];
int p[N];
bool visited[N] = {};

int dfs(int x){
	visited[x] = true;
	for(auto to : v[x]){
		if(to != 0){
			if(!visited[to]){
				p[to] = x;
				dfs(to);
			}
		}
	}
}

int main(){
	int n;
	scanf("%d", &n);
	for(int i=1;i<n;i++){
		int a,b;
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1);

	for(int i=2;i<=n;i++){
		printf("%d\n", p[i]);
	}
}

BOJ 11725 트리의 부모 찾기 (인접 리스트)