[BOJ] 1260번 DFS와 BFS

뚜비·2022년 4월 26일

BFS DFS boj 알고리즘

✅문제 설명

❗핵심원리

💻코드

1차

2차

BOJ

목록 보기

7/11

DFS와 BFS << 문제 클릭!

✅문제 설명

그래프를 DFS로 탐색한 결과, BFS로 탐색한 결과를 출력한다.

입력
: 정점의 개수 N(1 <= N <= 1000), 간선의 개수 M(1 <= M <= 10000), 탐색을 시작할 정점의 번호 V
: M개의 줄에는 간선이 연결하는 두 정점의 번호
출력
: 첫 번째 줄은 DFS 결과, 두 번째 줄은 BFS를 수행한 결과
: V부터 방문된 점을 순서대로 출력
조건
: 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것 먼저 방문
: 더 이상 방문할 수 있는 점이 없는 경우 종료
: 정점 번호는 1번부터 N번까지
: 간선은 양방향

❗핵심원리

BFS(Breadth First Search) 출처
: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 (이때 모든 노드를 방문하기 위한 순회 알고리즘이다!)
: 시작 노드에서 깊이가 1인 모든 노드를 방문하고 그 다음에 깊이가 2인 모든 노드를 방문.. 즉 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문한다.
: Queue를 이용하여 구현한다 -> 이때 방문한 노드는 큐에 push하고 이전 노드를 pop하면서 진행한다 -> 큐에 아무런 노드가 없을 때까지 진행한다.

DFS(Depth First Search) 출처
: 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘(이때 모든 노드를 방문하기 위한 순회 알고리즘이다!)
: 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
: 재귀 혹은 Stack을 이용하여 구현한다(BFS와 코드는 거의 비슷하고 스택을 사용하느냐 큐를 사용하느냐의 차이가 있음)

원리

위의 예제를 그래프로 그려보면 다음과 같은 그래프를 그릴 수 있다.

BFS의 경우
(1) 시작 노드 3을 큐에 push.

(2) 큐에서 pop하고 해당 노드와 인접한 노드에 대해 push(여기서 1번 4번, 노드 번호가 작은 것부터 push) 이때 한번 방문한 노드는 방문하지 않음(따로 표시를 해둬야 함!)

(3) 큐가 비어있을 때까지 2번을 반복

DSF의 경우
(1) 시작 노드 3을 스택에 push

(2) 스택에서 pop하고 해당 노드와 인접한 노드에 대해 push (여기서는 노드 번호가 큰 것 부터 push, 따라서 4번 1번 순으로!) 이때 한번 방문한 노드는 방문하지 않음(따로 표시)

(3) 스택이 비어있을 때까지 2번을 반복

💻코드

먼저 간선들을 vector<pair<int,int>> 형태로 저장하고 오름차순으로 정렬하였다. DFS는 노드 번호가 적은 순대로 하나씩 스택에 넣고 pop, BFS는 노드 번호가 적은 순대로 모두 큐에 넣고 pop을 했다.

1차

#include <iostream>
#include <queue> // 큐 사용 
#include <stack> // 스택 사용 
#include <vector> // 벡터 사용
#include <cstring> // memset 사용 
#include <algorithm> // sort 사용
#include <utility> // pair 사용 

using namespace std; // std라는 클래스의 이름 공간을 사용하겠다~~~
bool compare(const pair<int, int>& a, const pair<int, int>& b); // sort

int main(void) {
	ios::sync_with_stdio(0); // c++ stream과 c stream의 동기화 제거 -> 입출력 시 시간 이득
	cin.tie(0); // cin 수행 전에 buffer 지우지 않도록 해줌  

	int N, M, V = 0;
	cin >> N >> M >> V;

	int* visit = new int[N+1]; // 방문 check
	memset(visit, 0, sizeof(int)*(N+1)); // 초기화 !! 안 해주면 garbage 값이 들어가서 제대로 실행 못 함 
	vector<pair<int, int>> graph; // 그래프 

	// 입력
	for (int i = 0; i < M; i++) {
		int f, s = 0;
		cin >> f >> s;
		graph.push_back(make_pair(f, s)); // 값 대입 
	}

	sort(graph.begin(), graph.end(), compare); // 벡터 정렬 오름차순 

	/*DFS*/
	stack<int> next;
	next.push(V); // 초기값 넣기 
	visit[V] = 1; // 방문 표시 
	while (!next.empty()) // 비워질 때까지 반복 
	{
		int node = next.top(); //맨 위의 값 확인
		next.pop(); // 맨 위의 값 제거 
		// 연결된 노드 탐색
		cout << node << " ";
		for(int i = 0; i < M; i++) { // 큰 수 부터 대입 
			if (graph[i].first == node && visit[graph[i].second]==0) {
				//fisrt가 node고 secondㄱ 방문 안 된 노드라면?
				next.push(graph[i].second);
				visit[graph[i].second] = 1; // 방문 완료 
			}

			if (graph[i].second == node && visit[graph[i].first] == 0) {
				//second가 node고 first가 방문 안 된 노드라면? 
				next.push(graph[i].first);
				visit[graph[i].first] = 1; // 방문 완료 
				break;
			}
			
		}
		
	}
	cout << "\n"; // bfs 실행 


	/*BFS*/
	queue<int> next_b;
	next_b.push(V); // 초기값 대입
	visit[V] = 0; //방문 표시 
	while (!next_b.empty()) // 비워질 때까지 반복 
	{
		int node = next_b.front(); //맨 앞의 값 확인
		next_b.pop(); // 맨 아래의 값 제거 
		cout << node << " "; // 출력 
		// 연결된 노드 탐색
		for (int i = 0; i < M; i++) { // 작은 수 부터 대입 
			if (graph[i].first == node && visit[graph[i].second] == 1) {
				//fisrt가 node고 secondㄱ 방문 안 된 노드라면?
				next_b.push(graph[i].second);
				visit[graph[i].second] = 0; // 방문 완료 
			}

			if (graph[i].second == node && visit[graph[i].first] == 1) {
				//second가 node고 first가 방문 안 된 노드라면? 
				next_b.push(graph[i].first);
				visit[graph[i].first] = 0; // 방문 완료 
			}

		}

	}

	delete[] visit;

	return 0;
}

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
	if (a.first == b.first) {
		return a.second < b.second;// 오른쪽에 있는게 더 큰 수가 되도록 정렬해라! 
	}
	else {
		return a.first < b.first;// 넘어가기 
	}
}

✅문제 원인
예제는 모두 해결이 되었는데 왜 해결이 안 될까 고민해보니

DFS에서는 위의 그래프일 경우 잘못된 결과를 출력하게 된다. 즉 1번 노드에서 2번노드를 저장한 후 탐색이 종료된다.
단순히 스택에 방문한 노드를 담고 pop하면 노드 번호가 작은 순대로 출력한다는 보장을 못 한다.
위의 코드의 경우 알고리즘 자체에 문제가 있다. 예를 들어 위의 코드에서 1번 노드가 234와 연결되어 있는데 연결되어 있는 모든 코드에 대해 visited[] = 1;로 두기 때문에 그 다음 노드에 대해서 연결되어 있는 노드 탐색이 불가능한다. 즉 2번 노드와 연결된 4번 노드에 대해 스택에 추가가 불가능해진다.
BFS에서도 반례를 찾아보니 정렬을 하고 push를 해도 노드의 번호가 작은 순대로 출력되지 않는다는 것을 알았다! 예를 들어 시작 노드가 4번인데 4 10 5 4라는 간선이 있다면 당연히 4 10의 노드를 먼저 큐에 push하게 된다..

✅ 결론 : 간선을 vector에 단순히 pair로서 저장하는 방법을 바꿀 필요가 있다. -> 2차원 link list를 이용해보자

2차

2차원 벡터로 그래프 생성 이때 간선은 양방향이므로 순서 ㅂ바꿔서도 표시해줘야 함
visit 방문 배열 생성
꼭 정렬 해주기
DFS와 BFS 구조 비슷함 DFS는 스택을 BFS는 큐를 사용했다는 차이만 존재
방문 하지 않은 노드에 대해서만 탐색하도록 해줌

#include <bits/stdc++.h>

using namespace std; // std라는 클래스의 이름 공간을 사용하겠다~~~
bool compare(const pair<int, int>& a, const pair<int, int>& b); // sort

int main(void) {
	ios::sync_with_stdio(0); // c++ stream과 c stream의 동기화 제거 -> 입출력 시 시간 이득
	cin.tie(0); // cin 수행 전에 buffer 지우지 않도록 해줌  

	int N, M, V = 0;
	cin >> N >> M >> V;

	vector<vector<int>> graph; // 그래프 
	vector<int> v; // 각 노드 간 연결
	int* visit = new int[N+1]; // 동적 생성
	memset(visit, 0, sizeof(int) * (N+1)); // 초기화 


	// 초기화 
	for (int i = 0; i < N + 1; i++) {
		graph.push_back(v); // 노드마다 생성 
	}
	// 입력
	for (int i = 0; i < M; i++) {
		int f, s = 0;
		cin >> f >> s;
	    
		graph[s].push_back(f); // 간선 추가 
		graph[f].push_back(s); // 간선 추가  하나만 추가하면 간선 그래프 끊길 수도 있음 
	}

	/*정렬*/
	for (int i = 1; i < graph.size(); i++) {
		sort(graph[i].begin(), graph[i].end()); // 정렬 
	}

	/*DFS*/
	stack<int> next;
	next.push(V); // 초기값 넣기 
	while (!next.empty()) // 비워질 때까지 반복 
	{
		int p = next.top(); // 맨 위에 값 꺼내고
		next.pop();

		if (visit[p] != 1) { // 방문이 안 된 노드에 대해서만 
			visit[p] = 1; // 방문 표시  
			cout << p << " ";
		
			for (int i = graph[p].size()-1; i >= 0; i--) {
				next.push(graph[p][i]); // 해당 노드들 모두넣기 
			}
		}
		
	}
	cout << "\n"; 

	memset(visit, 0, sizeof(int) * (N + 1)); // 초기화 
	/*BFS*/
	queue<int> next_b;
	next_b.push(V); // 초기값 대입
	visit[V] = 0; //방문 표시 
	while (!next_b.empty()) // 비워질 때까지 반복 
	{
		int p = next_b.front(); // 맨 위에 값 꺼내고
		next_b.pop();

		if (visit[p] != 1) { // 방문이 안 된 노드에 대해서만 
			visit[p] = 1; // 방문 표시  
			cout << p << " ";
			
			for (int i = 0; i < graph[p].size(); i++) {
				next_b.push(graph[p][i]); // 해당 노드들 모두넣기 
			}
		}

	}

	delete[] visit;

	return 0;
}

아주 좋아~~

다른 분들의 풀이 출처

#include<iostream>
#include<queue>
using namespace std;
 
#define MAX_VALUE 1001            //'N이 1~1000 이므로 1000번째 인덱스에 접근 -> 크기 1001까지 선언
int N, M, V;                    //노드 개수, 간선 개수, 시작할 노드 번호
int mat[MAX_VALUE][MAX_VALUE];    //인접행렬 배열 선언
int visit[MAX_VALUE];            //visit 배열 default 는 0으로. . . 
 
void dfs(int v) {
    
    cout << v << ' ' ;
    visit[v] = 1;            //방문한 노드를 visit 0에서 1로 변경
    for(int i=1; i<=N; i++) {
        if(visit[i] == 1 || mat[v][i] == 0)     
            continue;
        dfs(i);                //dfs에서 재귀를 사용
    }
}
 
void bfs(int v) {
    queue<int> q;            //bfs에서는 q를사용
    q.push(v);
    visit[v] = 0;            //방문한 노드를 visit 1에서 0으로 변경
    while(!q.empty()) {
        v = q.front();
        cout << q.front() << ' ';
        q.pop();
        for(int i=1; i<=N; i++) {
            if(visit[i] == 0 || mat[v][i] == 0) // 방문한 노드 혹은 인접 노드 아닌 경우 
                continue;
            q.push(i);
            visit[i] = 0;
        }
    }
}
 
int main() {
    int x, y;.
    cin >> N >> M >> V;            //N은 노드개수, M은 간선의개수, V는 처음 위치의 기준이 되는 노드
    for(int i=0; i<M; i++) {    //간선의 개수만큼 서로 이어줄 x와 y노드를 입력받습니다.
        cin >> x >> y;            
        mat[x][y] = mat[y][x] = 1;    //인접행렬 표시
    }
    dfs(V);            
    cout << '\n';
    bfs(V);
    return 0;
}

DFS는 특히 재귀로도 풀 수 있음! 재귀를 이용하면 시작 노드에서 각 노드(이때 다시 노드번호가 작은 순대로)에서 dfs를 호출한다.
또한 2차원 배열을 이용한듯?!?

뚜비

SW Engineer 꿈나무 / 자의식이 있는 컴퓨터

이전 포스트

[BOJ] 1461번 도서관

다음 포스트

[BOJ] 1260번 DFS와 BFS

BOJ

✅문제 설명

❗핵심원리

💻코드

1차

2차

[BOJ] 1461번 도서관

[BOJ] 2178번 미로 탐색

0개의 댓글

관련 채용 정보