2주차 그래프이론, DFS, BFS

출처 : https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C

10주완성 C++ 코딩테스트 | 알고리즘 IT취업 - 인프런 | 강의

강의를 듣고 정리한 글 입니다.

자세한 설명은 여기로 → [알고리즘 강의] 2주차. 그래프이론, 인접행.. : 네이버블로그 (naver.com)

[알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회

 

그래프

정점(vertex, 노드라고도 불림) 과 간선으로 이루어진 집합

• 간선의 가중치는 관계,경로, 비용등이 될 수 있다.
• indegree 간선(들어오는 간선), outdegree 간선(나가는 간선)
• 단방향 간선, 양방향 간선
• 그래프의 구조 중에는 트리가 있다.

 

트리

• 자식노드와 부모노드로 이루어진 계층구조를 가진다.
• 무방향 그래프이다.
• 사이클이 없는 자료구조이다.
• 간선수 V = 노드수 E - 1
• 루트노드(맨 위에 있는 노드, 탐색시 주요 사용), 내부노드(루트와 리프사이), 리프노드(자식이 없는 노드)

• 깊이: 노드마다 다름, 루트 노드에서 특정 노드까지 최단거리로 갔을 때의 거리
  • 4번 노드의 깊이는 2
• 높이: 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리, 위 트리의 높이는 3
• 레벨: 보통 깊이와 같은 의미, 문제에서 1번 노드를 0레벨 또는 1레벨이라고 할 수 있음
• 서브트리: 트리 내의 하위 집합
• 숲: 트리로 이루어진 집합

 

이진 트리

• 자식노드의 수가 2개 이하로 구성되어있는 트리
• 정이진 트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리
• 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리, 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.
• 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리를 의미합니다.
• 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리를 의미합니다.
• 균형 이진 트리(balanced binary tree): 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리입니다. map, set을 구성하는 레드블랙트리는 균형이진트리 중 하나입니다.

 

 

이진 탐색 트리 (BST)

• 이진트리, 노드의 오른쪽 하위 트리에는 "노드의 값보다 큰 값"이 있는 노드만 포함되고 왼쪽 하위트리에는 "노드의 값보다 작은값"이 들어있는 트리
• 균형 이진트리라면 탐색, 삽입, 삭제, 수정 모두 O(logN)의 시간복잡도를 가진다.
  • AVL트리, 레드블랙트리가 있다.
    • map은 레드블랙트리를 기반으로 구현되어있다.
      • 이유: 트리의 균형을 다시 잡는 작업(re-balancing)이 RB Tree는 O(1), AVL tree는 O(log N)에 동작하기 때문에 현재 map은 RB Tree를 사용한다. https://suhwanc.tistory.com/197?category=730826
  • 검색이 용이하다.

레드 블랙 트리란?

 

인접행렬

• 정점과 간선의 관계를 나타내는 bool 타입(0,1)의 정사각형 행렬

 

문제

1번.

정점은 0번 부터 9번까지 10개의 노드가 있다. 1 - 2 / 1 - 3 / 3 - 4 라는 경로가 있다. (1번과 2번, 1번과 3번, 3번과 4번은 연결되어있다.)

이를 이를 인접행렬로 표현한다면?

​

2번.

0번부터 방문안한 노드를 찾고 해당 노드부터 방문, 연결된 노드를 이어서 방문해서 출력하는 재귀함수를 만들고 싶다면 어떻게 해야할까? 또한, 정점을 방문하고 다시 방문하지 않게 만드려면 어떻게 해야할까?

 

정답​

#include<bits/stdc++.h>
using namespace std; 
const int V = 10;
bool a[V][V], visited[V];
void go(int from){ 
	visited[from] = 1; //방문 표시 
	cout << from << '\n';
	for(int i = 0; i < V; i++){
		if(visited[i]) continue; //방문된 노드는 pass
		//from과 연결된 간선중 방문하지않은 노드가 있다면 방문 
		if(a[from][i]){ 
			go(i);
		}
	}
	return;
}
int main(){
	a[1][2] = 1; a[1][3] = 1; a[3][4] = 1;
	a[2][1] = 1; a[3][1] = 1; a[4][3] = 1;
	for(int i = 0;i < V; i++){
		for(int j = 0; j < V; j++){
			//차례대로 탐색, 방문하지않은 노드가 있다면 방문 
			if(a[i][j] && visited[i] == 0){
				go(i); 
			}
		}
	} 
}

• 방문했을때 간선 배열(a)를 수정하는 것이 아닌 정점배열(visited)을 수정(표시)한다.
• go 재귀함수에서 종료조건은 명확하게 나와있지 않지만, 간선으로 연결된 모든 노드가 방문되었을때 종료될 것임을 알 수 있다. (말하자면 dfs) 
  • 만약 모든 노드가 연결되어있다면 main함수에서 for문 2개대신 go(0)만 호출해도 모든 노드를 방문할 것이다.

1번노드를 제일 먼저 방문하고, 그 이후로 2-4-3 순으로 방문한다.

 

인접리스트

 

그래프에서 정점과 간선의 관계를 나타내는 연결리스트

코드

#include <bits/stdc++.h>
using namespace std;
const int V = 4;
vector<int> adj[V]; //인접리스트 

int main(){
	adj[0].push_back(1);
	adj[0].push_back(2);
	adj[0].push_back(3);
	
	adj[1].push_back(0);
	adj[1].push_back(2);
	
	adj[3].push_back(0);
	//원소마다 출력 
	for(int i=0;i<4;i++){
		cout << i << "::";
		for(there: adj[i]){
			cout << there << " ";
		}
		cout << "\n";
	}
}

 

인접리스트를 벡터로 구현한 이유 : 

n번째 요소 참조시 시간복잡도가 더 적기 때문이다.

	연결리스트	인접행렬
n번째 인덱스에 삽입, 삭제	O(1)	O(n)
마지막 요소에 삽입, 삭제	O(1)	O(1)
특정요소 탐색	O(n)	O(n)
n번째 요소 참조	O(n)	O(1)

 

문제

Q. 인접리스트를 기반으로 탐색하기

​

1번.

정점은 0번 부터 9번까지 10개의 노드가 있다. 1 - 2 / 1 - 3 / 3 - 4 라는 경로가 있다. (1번과 2번, 1번과 3번, 3번과 4번은 연결되어있다.)

이를 인접리스트로 표현한다면?

​

2번.

0번부터 방문안한 노드를 찾고 해당 노드부터 방문, 연결된 노드를 이어서 방문해서 출력하는 재귀함수를 만들고 싶다면 어떻게 해야할까? 또한, 정점을 방문하고 다시 방문하지 않게 만드려면 어떻게 해야할까?

 

내가 짠 코드

#include <bits/stdc++.h>
using namespace std;
const int V=10;
vector<int> adj[V];
int visited[V];

void go(int from){
	visited[from]=1;
	cout << from << "을 방문\n";
	
	for(int i:adj[from]){
		if(visited[i]==0) go(i);
	}
	return;
}

int main(){
	adj[1].push_back(1);
	adj[1].push_back(3);
	
	adj[2].push_back(1);
	
	adj[3].push_back(1);
	adj[3].push_back(4);
	
	adj[4].push_back(3);
	
	for(int i=0;i<V;i++){
		if(adj[i].size() && visited[i]==0) go(i);
	}
}

 

선생님 코드랑 거의 같아서 pass

 

인접리스트와 인접행렬의 차이

공간복잡도

- 인접행렬 : O(V^2) -> 정점 개수만큼 2차원 배열(표)

- 인접리스트 : O(V + E) ->정점 개수에 간선 개수만큼 공간 차지

// 인접행렬
bool adj[V][V];
// 인접리스트
vector<int> adj[V];

 

시간복잡도 : 간선 한개 찾기

- 인접행렬 : O(1) -> a[i][j]

- 인접리스트 : O(V) (O(E)도 가능하지만 최악의 경우 모든 정점과 연결된 간선 존재)

for(int j = 0; j < adj[i].size(); j++){
	cout << adj[i][j] << " ";
}

 

시간복잡도 : 모든 간선찾기

- 인접행렬 : O(V^2)

- 인접리스트 : O(V + E)

​

• 그래프가 희소(sparse)할 때는 인접리스트, 조밀(dense)할때는 인접행렬이 좋다.
  • 그래프가 희소하여 간선이 얼마 없다면, 인접행렬 사용시 공간낭비가 가능하다.
  • 그래프가 조밀하다면 인접행렬을 사용하는 것이 원소 접근시 속도가 빠르다.
• 알고리즘 문제에서 보통 인접리스트를 사용하는 것이 좋지만, 문제에서 인접행렬이 주어진다면 인접행렬로 그대로 푸는 것이 좋다.

 

방향 벡터

어떠한 y, x가 주어졌을 때 y, x를 중심으로 상하좌우 4가지 방향으로 탐색하는 방법 구하기

(그래프가 주어졌을때 간선이 주어지지않고, 4 또는 8방향으로 갈 수 있음)

• dy, dx 배열(변화치)을 구해서, for문으로 ny, nx 구하기
• (y,x)을 기준으로 함

Q1. {0, 0} 좌표에서 dy, dx를 만들어 4방향(위, 오른쪽, 아래, 왼쪽)을 탐색하며 좌표를 출력하시오.

 

• dy, dx 배열 구하기(외워도 됨)
• ny, nx 구하기

#include <bits/stdc++.h>
using namespace std;

const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};

int main(){
	int y=0,x=0;
	for(int i=0;i<4;i++){
		int ny = y+dy[i];
		int nx = x+dx[i];
		cout << ny << " : " << nx << "\n";
	}
	return 0;
}

 

Q2. {0, 0}좌표에서 dy, dx를 만들어 8방향(위, 오른쪽, 아래, 왼쪽 및 대각선방향포함)을 탐색하며 좌표를 출력하시오.

8방향일때(대각선 포함)

#include <bits/stdc++.h>
using namespace std;

const int dy[]={-1,-1,0,1,1,1,0,-1};
const int dx[]={0,1,1,1,0,-1,-1,-1};
int main(){
	int y=0, x=0;
	for(int i=0;i<8;i++){
		int ny = y+dy[i];
		int nx = x+dx[i];
		cout << ny << " : " << nx << "\n";
	}
	return 0;
}

 

Q. 3 * 3 맵을 입력받아야 함. 이 맵은 1과 0으로 이루어져있고 {0, 0}은 무조건 1임을 보장한다. {0, 0}부터 4방향을 기준으로 한칸씩 탐색해나가며 방문한 정점은 다시 방문하지 않으며(visited 배열 떠올라야함) 방문하는 좌표를 출력하는 코드를 구현하시오. 0은 갈 수 없는 지역. 1은 갈 수 있는 지역이다.

#include <bits/stdc++.h>
using namespace std;

const int V=3;
int a[V][V];
int visited[V][V];

const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};

void go(int y, int x){
	visited[y][x]=1; //방문 표시 
	cout << y << ":" << x << "방문\n";
	
	for(int i=0;i<4;i++){
		//갈 수 있는 위치 모두 탐색 
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(ny<0 || ny>=V ||nx<0 || ny>=V) continue; //배열 범위 먼저 확인(참조 오류 막기) 
		if(a[ny][nx]==0) continue; //연결되어있는지 확인 
		if(visited[ny][nx]) continue; //방문했는지 확인 
		go(ny, nx);
	}
	
	return;
}

int main(){
	for(int i=0;i<V;i++){
		for(int j=0;j<V;j++){
			cin >> a[i][j];
		}
	}
	go(0,0); //0,0 부터 시작 		
}

 

연결된 컴포넌트

연결된 하위그래프를 말하며 연결된 하나의 덩어리

 

연결된 컴포넌트에 속한 "모든 정점을 연결하는 경로가 있다."라는 특징을 가진다.

 

DFS(깊이우선탐색)

 pseudo code

DFS(u, adj)
    u.visited = true
    for each v ∈ adj[u]
        if v.visited == false
            DFS(v, adj)

 수도코드 기반 구현 코드

#include <bits/stdc++.h>
using namespace std;

const int V=6;
int visited[V];
vector<int> adj[V];

void dfs(int from){
	visited[from]=1;
	cout << from << "방문\n";
	for(int i:adj[from]){
		if(visited[i]==0) dfs(i);
	}
	return;
}

int main(){
	adj[1].push_back(2);
    adj[1].push_back(3); 
    adj[2].push_back(4);  
    adj[4].push_back(2);  
    adj[2].push_back(5);   
    dfs(1); 

}

 

 1. 정점을 방문하기 전에 방문했는지 확인하거나, 2. 방문했는지와 관계없이 그냥 go(방문)하며 탐색하는 방법이 있다.   

(두 방법 모두 알아두기!)

//1. 방문여부 확인 후 방문하기 
void dfs(int here){
	visited[here]=1;
	for(int there: adj[here]){
		if(visited[there]) continue;
		dfs(there);
	}
}
//2. 방문여부 상관없이 먼저 방문 
void dfs(int here){
	if(visited[here]) return;
	visited[here]=1
	for(int there:adj[here]) dfs(there);
}

문제

종화는 21세기 유명한 방구쟁이다. 종화는 방구를 낄 때 "이러다... 다 죽어!!" 를 외치며 방구를 뀌는데 이렇게 방귀를 뀌었을 때 방귀는 상하좌우 네방향으로 뻗어나가며 종화와 연결된 "육지"는 모두 다 오염된다. "바다"로는 방구가 갈 수 없다. 맵이 주어졌을 때 종화가 "이러다... 다 죽어!!"를 "최소한" 몇 번외쳐야 모든 육지를 오염시킬 수 있는지 말해보자. 1은 육지며 0은 바다를 가리킨다.

​

입력

맵의 세로길이 N과 가로길이 M 이 주어지고 이어서 N * M의 맵이 주어진다.

출력

"이러다... 다 죽어!!"를 몇 번외쳐야하는지 출력하라.

​

범위

1 <= N <= 100

1 <= M <= 100

​

예제입력

5 5 1 0 1 0 1 1 1 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0

예제출력

4

 

 

• 상하좌우로 간다는 점에서 방향벡터를 생각할 수 있고, 퍼진다고했으므로 DFS, BFS를 생각해볼 수 있다.

뻗어나간다, 퍼진다를 생각하면 DFS, BFS를 생각하기 

​

정답코드

#include <bits/stdc++.h>
using namespace std;

int n,m, a, x,y, ret;
bool visited[104][104];
int a[104][104];
const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};

void dfs(int y, int x){
	visited[y][x]=1;
	cout << y <<" : " << x << "방문\n";
	for(int i=0;i<4;i++){ //갈 수 있는 방향(위치) 모두 탐색
		int ny = y+dy[i];
		int nx = x+dx[i];
		if(ny<0 || ny>=n || nx<0 || nx>=m) continue;
		if(a[ny][nx]==0) continue; //간선이 없으면 pass
		if(visited[ny][nx]) continue; //이미 방문했으면 pass		
		dfs[ny][nx];
	}
	return;
}

int main(){
	//1. 입력받기 
	cin >> n >> m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin >> a[i][j];
		}
	}
	
	//2. dfs(0,0)이 아닌 모든 정점 확인하기(연결된 부분이 서로 떨어져있음) 
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j] && visited[i][j]==0){
				ret++;
				dfs(i,j);				
			} 
		}
	}
	cout << ret << "\n";
	return 0;		
}

 

BFS

BFS는 그래프를 탐색하는 알고리즘이며 어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘입니다. 같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰입니다.

레벨 별로 탐색한다. 방문한 정점은 방문하지 않는다.

=> 큐에 원소를 넣고 방문하면 pop, 연결된거 집어넣기

 

pseudo code

BFS(G, u)
    u.visited = 1
    q.push(u);
    while(q.size()) 
        u = q.front() 
        q.pop()
        for each v ∈ G.Adj[u]
            if v.visited == false
                v.visited = u.visited + 1
                q.push(v)

 

여기서 

v.visited = u.visited + 1

v.visited=1이 아닌 위의 방식으로 코드를 작성하면 방문 여부를 확인하면서도 값은 최단 거리를 가지는 배열이 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100];
int visited[100];
int nodeList[] ={10,12,14,16,18,20,22,24};

void bfs(int here){
	queue<int> q;
	visited[here]=1; 
	q.push(here); //한번만 실행 
	while(q.size()){ //정점 수만큼 반복 
		int here = q.front(); q.pop();
		for(int there:adj[here]){ //인접한 정점 중에 
			if(visited[there]) continue; //방문한 거 제외 
			visited[there] = visited[here]+1; //최단거리+1 증가시키기(가중치를 정해준다음) 
			q.push(there); //큐에 집어넣기
		}
	}
}
int main(){
	adj[10].push_back(12);
    adj[10].push_back(14);
    adj[10].push_back(16);
    
    adj[12].push_back(18);
    adj[12].push_back(20);

    adj[20].push_back(22);
    adj[20].push_back(24);
    
    bfs(10); //정점 10부터 시작
	
	for(int i:nodeList){
		cout << i << " : " << visited[i] << "\n";
	}
	//루트노드가 거리 1부터 시작하므로 -1해주기
	cout << "10번부터 24번까지의 최단 거리는 : " << visited[24]-1 <<"\n"; 
	
	return 0;	
}

시작점이 여러개라면

#include <bits/stdc++.h>
using namespace std;

int visited[104];
vector<int> adj[104];
int nodeList[]={10,12,14,16,18,20,22,24};
void bfs(){
	queue<int> q;
	for(int i=1;i<=3;i++){ //큐에 출발점 모두 저장 
		q.push(i);
		visited[i]=1;
	}
	while(q.size()){
		int here=q.front(); q.pop();
		for(int there:adj[here]) {
			if(visited[there]) continue;
			visited[there] = visited[here]+1;
			q.push(there);
		}
	}
}
int main(){
	adj[10].push_back(12);
    adj[10].push_back(14);
    adj[10].push_back(16);
    
    adj[12].push_back(18);
    adj[12].push_back(20);

    adj[20].push_back(22);
    adj[20].push_back(24);
    bfs();
    
    for(int i:nodeList){
    	cout << i << ":" << visited[i] << "\n";
	}
	cout << "10번부터 24번까지 최단거리는:" << visited[24]-1 << "\n";
	return 0;
    
	
}

가중치가 다르다면

BFS, DFS 사용하지 않고 다른 알고리즘 사용하기 (벨만포드, 다익스트라)

 

 => 가중치가 같은 그래프에서 최단거리 알고리즘 : BFS,DFS

 

당근마켓 엔지니어 승원이

승원이는 당근을 좋아해서 당근마킷에 엔지니어로 취업했다. 당근을 매우좋아하기 때문에 차도 당근차를 샀다. 이 당근차는 한칸 움직일 때마다 당근을 내뿜으면서 간다. 즉, "한칸" 움직일 때 "당근한개"가 소모된다는 것이다. 승원이는 오늘도 아침 9시에 일어나 당근마킷으로 출근하고자 한다. 승원이는 최단거리로 당근마킷으로 향한다고 할 때 당근몇개를 소모해야 당근마킷에 갈 수 있는지 알아보자. 이 때 승원이는 육지로만 갈 수 있으며 바다로는 못간다. 맵의 1은 육지며 0은 바다를 가리킨다. 승원이는 상하좌우로만 갈 수 있다.

입력

맵의 세로길이 N과 가로길이 M 이 주어지고 이어서 N * M의 맵이 주어진다. 그 다음 줄에 승원이의 위치(y, x)와 당근마킷의 위치(y, x)가 주어진다.

출력

당근을 몇개 소모해야 하는지 출력하라.

범위

1 <= N <= 100

1 <= M <= 100

예제입력

5 5 0 0 4 4 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1

예제출력

9

해설

이 문제는 어떤 문제일까요? 바로 "가중치가 같은 그래프 내의 최단거리 알고리즘" 문제입니다. 한칸씩 이동할 때마다 당근 한개를 쓰기 때문에 가중치가 같은 그래프이며 여기서 최단거리를 구하는 알고리즘이기 때문이죠. 그렇다면 BFS를 통해 최단거리 배열을 만들어서 해야 합니다.

​

#include <bits/stdc++.h>
using namespace std;

const int max_n=104;
int x,y, n,m, sy,sx,cy,cx;
int a[max_n][max_n];
int visited[max_n][max_n];
const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};
queue<pair<int,int>> q;

void bfs(){
	visited[sy][sx]=1; //한번만 실행 
	q.push({sy,sx});
	while(q.size()){
		tie(y,x) =q.front(); q.pop();
		for(int i=0;i<4;i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(nx<0 || ny <0 || ny>=n || nx>=m) continue;
			if(visited[ny][nx]) continue;
			if(a[ny][nx]) {
				visited[ny][nx] = visited[y][x]+1;
				q.push({ny,nx});				
			}		
		}	
	}
	return;
	
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	cin >> sy >> sx;
	cin >> cy >> cx;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin >> a[i][j];		
		}
	}
	bfs();
	cout << visited[cy][cx] << "\n"; //도착지까지 거리 
	cout << "\n";

	return 0;
}

 

DFS와 BFS비교

둘 다 시간복잡도는 인접리스트로 이루어졌다면 O(V + E)이고 인접행렬의 경우 O(V^2)가 되는 것은 동일하며 다음과 같은 차이가 있습니다.

이름	설명
DFS	메모리를 덜 씀. 절단점 등 구할 수 있음. 코드가 좀 더 짧으며 완전탐색의 경우에 많이 씀.
BFS	메모리를 더 씀(queue 필요). 가중치가 같은 그래프내에서 최단거리를 구할 수 있음. 코드가 더 김

 

퍼져나간다, 탐색한다 라고 한다면 DFS, BFS를 떠올리자,

DFS가 코드는 훨씬 짧기때문에 DFS를 주로 사용한다.

 

트리 순회

 

전위 순회

부모부터 방문

preorder( node )
    if (node.visited == false) //방문 안했다면
        node.visited = true //자신부터 방문
        preorder( node->left )
        preorder( node->right )

 

중위 순회

왼쪽 자식->부모->오른쪽 자식

inorder( node )
    if (node.visited == false) 
        inorder( node->left )
        node.visited = true
        inorder( node->right )

 

후위 순회

왼쪽자식 -> 오른쪽 자식-> 부모(자신)

postorder( node )
    if (node.visited == false) 
        postorder( node->left ) 
        postorder( node->right )
        node.visited = true

 

레벨 순회

BFS

 

Q. 아래의 그래프가 주어졌을 때 preorder, inorder, postorder를 구현하라.

구현 코드

#include <bits/stdc++.h>
using namespace std; 
vector<int> adj[1004]; 
int visited[1004];

//전위 순회
void preOrder(int here){  
    if(visited[here]==0){ //방문을 아직 안했다면
        visited[here]=1; // 자기부터 방문
        cout << here << " ";
        if(adj[here].size()==1) //자식 하나이면
        preOrder(adj[here][0]); //자식 방문
        if(adj[here].size()==2){ //자식 둘이면
            preOrder(adj[here][0]); //왼쪽 자식 방문
            preOrder(adj[here][1]); //오른쪽 자식 방문
        }
    }
} 
//중위 순회
void inOrder(int here){ 
    if(visited[here]==0){
        if(adj[here].size()==1) {
            inOrder(adj[here][0]);
            visited[here]=1;
            cout << here << " ";
        }
        else if(adj[here].size()==2){
            inOrder(adj[here][0]);
            visited[here]=1;
            cout << here << " ";
            inOrder(adj[here][1]);
        }
        else{ //중위순회는 부모부터 시작하므로 자식이 없을 수 있음
            visited[here]=1;
            cout << here << " ";
        }
    }
}  
//후위 순회
void postOrder(int here){   
    if(visited[here]==0){
        if(adj[here].size()==1) {
            postOrder(adj[here][0]);
        }
        if(adj[here].size()==2){
            postOrder(adj[here][0]);
            postOrder(adj[here][1]);
        }//공통, 자식 없을때도 실행
        visited[here]=1;
        cout << here << " ";
    } 

} 
int main(){
	adj[1].push_back(2);
	adj[1].push_back(3);
	adj[2].push_back(4);
	adj[2].push_back(5); 
	int root = 1;
    cout << "\n 트리순회 : postOrder \n";
    postOrder(root); memset(visited, 0, sizeof(visited)); //전위순회 후 visited배열 초기화
    cout << "\n 트리순회 : preOrder \n"; 
    preOrder(root); memset(visited, 0, sizeof(visited)); 
    cout << "\n 트리순회 : inOrder \n"; 
    inOrder(root); 
    return 0;
}