[C/C++ 8.6] 알고리즘 - 그래프(인접행렬) / DFS/ BFS

 

 

// 그래프의 화살표를 배열로 표시 !! 
// 행(col)은 (화살표가 가리키는 사람)
// 렬(row)는 화살표 몇개 받았는지 세는 데 씀 !!

 

 

단순 그래프 [인접행렬]

EX) 

// Level 28

// 1번					`// 인접행렬 ****
int main() {
	char names[5][10] = { "Amy","Bob","Chloe","Diane","Edger" };	
	// 화살표를 배열로 표시 !! (좋아하면 1 )
	// 행(col)은 내가 좋아하는 사람 (화살표 가리키는 사람)
	// 렬(row)는 화살표 몇개 받았는지 세는 데 씀 !!
	int arr[5][5] = {
		0,1,0,0,0,
		0,0,1,1,0,
		0,0,0,0,0,
		0,0,0,0,0,
		1,0,0,0,0
	};
	int maxidx = 0, count[5] = { 0 };	// 본인을 좋아하는 사람 수 셈
	// 2차 for문 돌리면서 check
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if (arr[i][j])	// 1이면,
				count[i]++;	// count[i] => 가로로 수를 셈
		}
		// 숫자 센 최댓값 꼬박꼬박 갱신
		if (count[maxidx] < count[i])
			maxidx = i;
	}
	cout << names[maxidx];

	return 0;
}

 

 

 

Tree 구조 [인접행렬]

EX)

// 3번							// Tree 구조 !! *********
int arr[8][8] = {
	// 쌍방 화살표		//  tree  특성상 col 마다 1(부모)은 한개씩 밖에 없음 !
	0,1,1,0,0,0,0,1,	//A		// A의 자식들을 표시  ***
	0,0,0,0,0,0,0,0,	//B
	0,0,0,1,1,0,1,0,	//C
	0,0,0,0,0,1,0,0,	//D
	0,0,0,0,0,0,0,0,	//E
	0,0,0,0,0,0,0,0,	//F
	0,0,0,0,0,0,0,0,	//G
	0,0,0,0,0,0,0,0		//H
};
int findParent(char name) {
	// 부모 찾기 *******************************************************************
	for (int i = 0; i < 8; i++) {
		if (arr[i][name - 'A'] == 1)
			return i;	// 부모 index 알려주기
	}
	return -1;		// 부모 없을 경우 -1
}
int main() {
	char name;
	cin >> name;
	// 부모 먼저 찾고,
	int parent = findParent(name);

	// i) 부모 없으면,
	if (parent == -1)
		cout << "없음";
	// ii) 부모 있으면,
	else {
		// 그 부모의 자식 찾기 (본인 제외) ***************************************
		for (int i = 0; i < 8; i++) {
			if ((arr[parent][i] == 1) && (i != name - 'A'))	// 자식들이고(1) && 본인이 아니고,
				cout << char('A' + i) << " ";
		}
	}
	return 0;
}

 

 

그래프 DFS 탐색 [재귀, 인접행렬]

EX)

// 4 번   ___ 답안코드					// 그래프 DFS 탐색 ___ 재귀.ver 
int map[10][10];
int n;
// 입력
void input(){
	cin >> n;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
		}
	}
}
// 이게 메인 !!!			// 재귀함수로 구현 !!!!!!
void run(int now)
{
	cout << now << " ";

	for (int i = 0; i < n; i++) {
		if (map[now][i] == 1) {	// 해당 가로줄 탐색
			run(i);
		}
	}
}
int main(){
	input();
	run(0);	// 루트를 그냥 처음부터 줘버림
	return 0;
}

 

 

그래프 Cycle 막기 [재귀]

EX)

// 2번 ___ 답안코드

// 그래프
int map[6][6] = {		// 1->3->5->1->3->5 루프 걸리기 딱좋음 !
	0, 0, 1, 0, 1, 1,
	1, 0, 0, 1, 0, 0,
	0, 0, 0, 0, 1, 0,
	1, 0, 0, 0, 0, 0,
	1, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0,
};
int a, b;
int used[10];
int mini = 21e8;				// 그냥 대충 큰 수

void dfs(int level, int now) {
	// 원하는 노드 도착 시 ->  최솟값 갱신
	if (now == b) {
		if (mini > level) 
        	mini = level;
		return;						
	}
	// 자식들 탐색
	for (int i = 0; i < 6; i++) {
		if (map[now][i] == 0) 
        	continue;
		if (used[i] == 1) 
        	continue;		// 전에 들렀던 노드면 out -> 무한 cycle 막음 !!! ***** used로 !
		// 재귀
		used[i] = 1;		// used 표시 !
		dfs(level + 1, i);	// 재귀
		used[i] = 0;		// return으로 다시 빠져나온 후 이므로, used를 원래대로 백업
	}
}

int main(){
	// 노드가 1 부터 시작하므로, index에 맞추기 위해 하나씩 줄여서 넣기 !!!
	cin >> a >> b;
	a-=1;
	b-=1;
	// main
	used[a] = 1;
	dfs(0, a);
	// 출력 보정
	if (mini == 21e8) 
    	mini = 0;
	cout << mini;
	return 0;
}

 

 

DFS + 가중치 + 그래프 

// 2번						DFS + 가중치
int graph[6][6] = {	// 가중치값 입력되어있음
	0,0,1,0,2,0,
	5,0,3,0,0,0,
	0,0,0,0,0,7,
	2,0,0,0,8,0,
	0,0,9,0,0,0,
	4,0,0,7,0,0
};
int used[6] = { 0 };
int weight = 0;
// weight가중치를 함수로 같이 전달할 시, return하면 weight 도 원상복귀 되기 때문에 전역변수로 써야함 !!!
// ex)  4->2->5->0->(5)->3 으로 5~0 구간에서 return으로 인해 다시 빠져나오는 구간인데,
//	    4->2->5->0->   ->3 으로 빠져나오는 구조에서
//		함수 인자 전달로 weight를 할 시에는 0 시점의 weight로 돌아와 가중치 값이 작아지므로,
//		그냥 중간과정에 return이 있던 말던 값 유지 되는 전역변수 사용하기
void DFS(int now) {
	cout << now <<" "<< weight<<endl;
	used[now] = 1;
	// 화살표 찾아가기(재귀)
	for (int i = 0; i < 6; i++) {
		if (graph[now][i] != 0) {
			// 이 used조건, 재귀 로 들어가고 난 뒤에 return하게 설계 하면 weight 값 변함 주의 ***
			if (used[i] == 0) {
				weight += graph[now][i];
				DFS(i);
			}
		}
	}
}
int main() {
	int K;
	cin >> K;
	DFS(K);
	return 0;
}

 

 

---

BFS

Queue 를 사용해 구현한다.

 

EX)  queue 직접 구현 ver

// 3번					_____ BFS (while 문 속 queue으로 구현)
int graph[6][6] = {
	0,1,0,0,1,0,
	0,0,1,0,0,1,
	0,0,0,1,0,0,
	0,0,0,0,0,0,
	0,0,0,0,0,0,
	0,0,0,0,0,0
};
int qu[6];					
int head = 0, tail = 1;		// head, tail 지정

int main() {
	int K;
	cin >> K;
	qu[head] = K;	// 큐 시작 번호 넣기

	// 큐에서 뽑아내기 - Head
	while (tail != head) {
		int j = qu[head];
		head++;

		// 큐 에 넣기 - Tail
		for (int i = 0; i < 6; i++) {
			if (graph[j][i] == 1) {
				qu[tail++] = i;
			}
		}
	}
	// 출력 (큐 입장 순서 = 트리 BFS 순서)
	for (int i = 0; i < tail; i++)	// 큐 쌓인데 까지만 출력
		cout << qu[i] << " ";
	return 0;
}

EX)  STL queue 사용 ver     *******************

// 3번			__ 답안코드   ____ queue 큐  (STL 사용) 로 구현
int MAP[6][6] = {
	0,1,0,0,1,0,
	0,0,1,0,0,1,
	0,0,0,1,0,0,
	0,0,0,0,0,0,
	0,0,0,0,0,0,
	0,0,0,0,0,0,
};
void bfs(int start) {
	queue<int>qu;			// queue<int> 이름;	
	qu.push(start);			// 큐.push(a)	: push함수		//qu[head] = K;

	while (!qu.empty()) {		// 큐.empty()	: empty여부 출력	//while (tail != head)로 대체가능
		int now = qu.front();	// 큐.front()	: 제일 앞에 있는것 출력	//int j = qu[head];
			qu.pop();	// 큐.pop()	: front데이터 삭제	//head++;
		cout << now << " ";
		for (int x = 0; x < 6; x++) {
			if (MAP[now][x] == 1)
				qu.push(x);			// qu[tail++] = i; 대체가능
		}
	}
}
int main(){
	int s;
	cin >> s;
	bfs(s);
	return 0;
}

 

BFS + used (STL queue ver)

EX)  

// 4번
int graph[6][6] = {
	0,0,0,0,1,0,
	1,0,1,0,0,1,
	1,0,0,1,0,0,
	1,1,0,0,0,0,
	0,1,0,1,0,1,
	0,0,1,1,0,0
};
queue<int> qu;
int used[6] = { 0 };
void BFS(int now) {
	// 시작준비
	qu.push(now);
	used[now] = 1;		// 여기도 미리 표시하기 !!

	while (qu.empty() == 0) {	// 큐가 비어있지 않을 동안	
		// 큐에 돌릴것 선택
		int j = qu.front();
		qu.pop();
		cout << j << endl;
		// 자식들 큐에 넣기
		for (int i = 0; i < 6; i++) {
			if (graph[j][i] == 1 && used[i] == 0) {
				qu.push(i);
				used[i] = 1;	// 꼭 큐에 넣자마자 used 표시해야함
                }
		}
	}
}
int main() {
	int st;
	cin >> st;
	BFS(st);
	return 0;
}

 

 

 

// 시간제한 1초 = 1억번 n = 10