#1260 DFS와 BFS

# 문제

# 입력 및 출력

# 풀이

이 문제를 이틀 전인가 그때 봤는데 도저히 어떻게 풀어야 할지 감이 안잡혀서 그냥 버리고 넘어갔었다ㅋㅋㅋ

진짜 각잡고 해보자 해서 다시 풀어보는데 좀 복잡해져도 배열이랑 자료구조 좀만 섞어 쓰면 풀 수 있을 것 같았다

그래서 아래 블로그 이론을 참고해서 코드를 작성해봤다

 

1) DFS

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

2) BFS

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

 

DFS, BFS 둘 다 사용하는 자원

방문했는지, 그래프가 연결되어있는지 확인하기 위해 정적 배열 2개를 선언했음

 

1) DFS 풀이 방법

DFS는 스택을 사용하려다가 굳이 필요없길래 그냥 정적 배열이랑 출력용 벡터를 하나씩 사용했음

DFS는 깊이 우선이므로 연결된 부분에서 계속 타고 들어가는 방식이기 때문에 반복문 안에서 재귀 호출 해준다

 

2) BFS 풀이 방법

BFS는 좀 코드가 복잡한데 일단 FIFO를 위해 큐를 사용했음

그리고 큐에 중복으로 값이 들어가는 것을 막기 위해 inQueue 배열을 하나 더 사용했음

그리고 큐에서 pop되기 전에 재귀호출되는 것을 막기 위해 값을 따로 저장해둔뒤 큐에서 값을 삭제하고 호출하는 방식으로 풀었음

BFS는 너비 우선이므로 큐에 연결된 노드를 다 저장해둔 뒤 한 턴이 끝나면 그때 호출하는 방식

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

vector<int> result; // 결과 출력용 벡터
queue<int> q; // BFS용 큐
int connect[1001][1001]; // 그래프 연결 여부 확인용 배열
int visit[1001]; // 노드 방문 여부 확인용 배열
int inQueue[1001]; // 큐에 중복 값 삽입 방지 배열
int n, m, v; // 문제에서 주어지는 N, M, V

void clear() { // 노드 방문 배열 초기화
	for (int i = 0; i <= 1000; i++) {
		visit[i] = 0;
	}
}

void dfs(int root) {
	visit[root] = 1; // 노드 방문
	result.push_back(root); // 결과 출력용 배열에 저장
	for (int i = 1; i <= n; i++) {
		if (!visit[i]) { // 방문하지 않았고
			if (connect[root][i]) { // 그래프가 연결된 노드
				dfs(i); // 해당 노드로 다시 dfs 진행(재귀호출)
			}
		}
	}
	while (!result.empty()) { // 결과 출력용 반복문
		cout << result.front() << " ";
		result.erase(result.begin());
	}
}

void bfs(int root) {
	visit[root] = 1; // 노드 방문
	result.push_back(root); // 결과 출력용 배열에 저장
	for (int i = 1; i <= n; i++) {
		if (!visit[i]) { // 방문하지 않았고
			if (connect[root][i]) { // 그래프가 연결되었고
				if (!inQueue[i]) { // 큐에 이미 들어있지 않은 노드
					inQueue[i] = 1; // 큐에 들어갔다고 표시
					q.push(i); // 큐에 넣기
				}	
			}
		}
	}
	while (!q.empty()) { // 큐가 빌때까지 반복
		int tmp = q.front(); // bfs 호출 전에 삭제를 먼저하기 위해 미리 값 저장
		q.pop(); // 값 하나 삭제
		bfs(tmp); // 다음 노드로 bfs 진행(재귀호출)
	}
	while (!result.empty()) { // 결과 출력용 반복문
		cout << result.front() << " ";
		result.erase(result.begin());
	}
}

int main() {
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		int s, e;
		cin >> s >> e;
		connect[s][e] = 1;
		connect[e][s] = 1; // 양방향
	}
    // 입력 완료

	dfs(v);
	clear();

	cout << endl;

	bfs(v);
	clear();
}

 

어찌저찌 해결 완료ㅋㅋ

간단한 코드 찾아봐야겠다

 

https://scarlettb.tistory.com/76

1260번 DFS와 BFS | Baekjoon BOJ 백준 1260 C++ 코드, 해설, 풀이

위 블로그를 참고했다

코드는 거의 비슷하고 그냥 결과 출력용 벡터를 삭제하고 함수 재귀호출 될 때 마다 바로 출력하는 방식으로 바꿈

코드가 좀 짧아지긴 했다ㅋㅋ

 

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

queue<int> q;
int connect[1001][1001];
int visit[1001];
int inQueue[1001];
int n, m, v;

void clear() {
	for (int i = 0; i <= 1000; i++) {
		visit[i] = 0;
	}
}

void dfs(int root) {
	visit[root] = 1;
	cout << root << " ";
	for (int i = 1; i <= n; i++) {
		if (!visit[i]) {
			if (connect[root][i]) {
				dfs(i);
			}
		}
	}
}

void bfs(int root) {
	visit[root] = 1;
	cout << root << " ";
	for (int i = 1; i <= n; i++) {
		int t = 0;
		if (!visit[i]) {
			if (connect[root][i]) {
				if (!inQueue[i]) {
					inQueue[i] = 1;
					q.push(i);
				}	
			}
		}
	}
	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		bfs(tmp);
	}
}

int main() {
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		int s, e;
		cin >> s >> e;
		connect[s][e] = 1;
		connect[e][s] = 1; // 양방향
	}

	dfs(v);
	clear();

	cout << endl;

	bfs(v);
	clear();
}

200바이트 정도 줄었음ㅋㅋ