[BOJ/백준] 1260 DFS와 BFS

● [문제번호 1260] DFS와 BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

● 알아야 할 것

: DFS(재귀, 비재귀), BFS

: vector 자료구조와 메소드

: stack 자료구조와 메소드

: queue 자료구조와 메소드

 

● 풀이 과정

: 아래 코드는 구현방법3 을 적용했다. (코드는 구현방법1, 2, 3 모두 있다)

구현방법1 (오름차순 → DFS 선택1 → 방문기록 초기화 → BFS)

구현방법2 (오름차순 → DFS 선택2 → 방문기록 초기화 → BFS)

구현방법3 (내림차순 → DFS 선택3 → 오름차순 → 방문기록 초기화 → BFS)

 

: #DFS 선택1 {DFS_재귀}

기본적인 작성 형태로 어렵지 않게 구현할 수 있다.

 

: #DFS 선택2 {DFS_비재귀_vertex 오름차순}

stack을 이용해서 구현하는데 출력지점을 어떻게 해야할지 고민하다가 구글링을 했다.

 

기존 DFS_비재귀 작성 형식은 아래와 같다.

1. 출발점 체크인 + stack.push

2. while(스택이 빌 때 까지)

2-1. stack.top 기억

2-2. stack.pop

2-3. 기억한 stack.top에 연결된 모든 정점 탐색

2-3-1. 방문하지 않은 정점인 경우

2-3-2. 정점 체크인

2-3-3. stack.push

 

그러나 그러면 출력 순서가 원하는 대로 안나온다.

왜냐하면 문제에서 DFS는 방문할 수 있는 정점이 여러 개인 경우 작은 정점 번호부터 방문해야하는데,

stack에서 쌓는 순서와 위에서 뽑았을 때 정점 번호를 생각해보면 원하는 대로 순서가 결정되지 않는다.

(쌓는 순서와 뽑는 방법을 유지하려면 vertex 정점 배열을 내림차순으로 정렬하면됨 → #선택3)

 

그래서 중간에 flag를 이용하여,

from 정점에서 연결된 방문하지 않은 정점이 없을 때 까지

{from 정점에서 연결된 방문하지 않은 정점을 stack에 1개 쌓고

방금 쌓은 정점(from이 바뀜) 기준으로 다시 연결된 정점 탐색} 을 하고

from 정점을 stack에서 pop 한다.

→ 이해를 위한 그림 필요

 

 

: #선택3 {DFS_비재귀_vertex 내림차순}

기본적인 작성 형태에서 체크인의 위치만 수정하여 구현할 수 있다.

DFS는 방문할 수 있는 정점이 여러 개인 경우 작은 정점 번호부터 방문하기 위해

각 vertext 정점 배열을 내림차순으로 미리 정렬해야한다.

 

: BFS

기본적인 작성 형태로 어렵지 않게 구현할 수 있다.

 

● 주의 할 것

: DFS → 방문기록(visited) 초기화 → BFS 해야한다.

 

: 방문할 수 있는 정점이 여러 개인 경우에 정점 번호를 작은 것을 먼저 방문하기 위해 정렬을 먼저 해야한다.

(오름차순으로 할 건지, 내림차순으로 할 건지 본인 선택)

 

● 참고 할 것

: DFS (비재귀_오름차순) 구현 참고

https://ldgeao99.tistory.com/387

 

: DFS (비재귀_내림차순) 구현 참고 

https://blog.encrypted.gg/908?category=773649

(BarrrrrrrrkingDog 블로그 → 그래프(구) → 58 슬라이드)

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// vertex : 각 index 정점의 연결된 정점집합
// visited : 정점의 방문기록
vector<int> vertex[1001];
vector<bool> visited;
int N, M, V;

// DFS_비재귀_각 vertex 배열 내림차순으로 만들기 위해
bool compare(int a, int b)
{
    return a > b;
}

// ### 선택 1 ###
// DFS_재귀
void dfs_recursive(int from)
{
    // 정점 체크인 + 출력
    visited[from] = true;
    cout << from << " ";
    
    // 연결된 정점 탐색
    for(int i = 0; i < vertex[from].size(); i++)
    {
        int to = vertex[from][i];
        
        // 연결된 정점 중 방문X 인 경우
        if(!visited[to])
            dfs_recursive(to);
    }
}

// ### 선택 2 ###
// DFS_비재귀_각 vertex 배열 오름차순인 경우
// (출력을 위해 일반적 DFS_비재귀 구현 형태에서 수정됨)
void dfs(int start)
{
    stack<int> s;
    
    // 시작 정점 체크인 + stack 저장 + 출력
    visited[start] = true;
    s.push(start);
    cout << start << " ";
    
    // stack 이 빌 때 까지 반복
    while(!s.empty())
    {
        int from = s.top();
        
        // from 정점에서 방문하지 않은 정점이 있는 지 확인
        bool flag = false;
        
        // from 정점에 연결된 정점 탐색
        for(int i = 0; i < vertex[from].size(); i++)
        {
            int to = vertex[from][i];
            
            // from 정점에 연결된 방문하지 않은 정점인 경우
            if(!visited[to])
            {
                // 1. 정점 체크인
                // 2. stack에 정점 저장
                // 3. 출력
                // 4. from 정점에서 방문하지 않은 정점이 있다고 신호
                // 5. 해당 정점으로 이동하기 위해 break;
                visited[to] = true;
                s.push(to);
                cout << to << " ";
                flag = true;
                break;
            }
        }
        
        // from 정점에 연결된 정점이 모두 방문된 경우
        if(!flag)
            s.pop();
    }
}

// ### 선택 3 ###
// DFS_비재귀_각 vertex 배열 내림차순인 경우
// (일반적 DFS_비재귀 구현 형태 + 체크인 위치 수정)
void dfs_compare(int start)
{
    stack<int> s;
    
    s.push(start);
    
    // stack 이 빌 때 까지
    while(!s.empty())
    {
        int from = s.top();
        s.pop();
        
        // 방문한 정점인 경우
        // (없으면 무한루프)
        if(visited[from])
            continue;
        
        // 체크인 + 출력
        visited[from] = true;
        cout << from << " ";
        
        // 연결된 모든 정점 탐색
        for(int i = 0; i < vertex[from].size(); i++)
        {
            int to = vertex[from][i];
            
            // 방문하지 않은 정점인 경우
            if(!visited[to])
                s.push(to);
        }
    }
}

// BFS (전형적으로 구현형태)
void bfs(int start)
{
    queue<int> q;
    
    // 정점 체크인 + queue 저장
    visited[start] = true;
    q.push(start);
    
    // queue 가 빌 때 까지 반복
    while(!q.empty())
    {
        // 맨 앞 정점 출력
        int from = q.front();
        q.pop();
        cout << from << " ";
        
        // 맨 앞 정점에 연결된 모든 정점 탐색
        for(int i = 0; i < vertex[from].size(); i++)
        {
            int to = vertex[from][i];
            
            // 맨 앞 정점에 연결된 방문하지 않은 정점이 있는 경우
            if(!visited[to])
            {
                // 1. 방문 체크인
                // 2. queue 저장
                visited[to] = true;
                q.push(to);
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M >> V;

    // 양방향 간선 저장
    for(int m = 0; m < M; m++)
    {
        int a, b;
        cin >> a >> b;
        
        vertex[a].push_back(b);
        vertex[b].push_back(a);
    }
    
    // 방문할 수 있는 정점이 여러 개인 경우에
    // 정점 번호가 작은 것을 먼저 방문하기 위해 정렬
    // (compare 함수를 이용하여 내림차순으로 정렬)
    for(int n = 1; n <= N; n++)
        sort(vertex[n].begin(), vertex[n].end(), compare);
    
    // 방문기록 초기화 → DFS → 방문기록 제거
    visited.assign(1001, false);
    dfs_compare(V);
    visited.clear();
    
    cout << "\n";
    
    // 방문할 수 있는 정점이 여러 개인 경우에
    // 정점 번호가 작은 것을 먼저 방문하기 위해 정렬
    for(int n = 1; n <= N; n++)
        sort(vertex[n].begin(), vertex[n].end());
    
    // 방문기록 초기화 → BFS → 방문기록 제거
    visited.assign(1001, false);
    bfs(V);
    visited.clear();
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [600 - 그래프 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	13023	ABCDE	https://pirateturtle.tistory.com/269
2	1260	DFS와 BFS	https://pirateturtle.tistory.com/270
3	11724	연결 요소의 개수	https://pirateturtle.tistory.com/271
4	1707	이분 그래프	https://pirateturtle.tistory.com/272
5	2667	단지번호붙이기	https://pirateturtle.tistory.com/273
6	4963	섬의 개수	https://pirateturtle.tistory.com/274
7	2178	미로 탐색	https://pirateturtle.tistory.com/275
8	7576	토마토	https://pirateturtle.tistory.com/276
9	7562	나이트의 이동	https://pirateturtle.tistory.com/277