Computer Science & Engineering

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

이 문제는 비 방향성 그래프의 간선이 주어졌을 때 V번 정점부터 시작하여 DFS로 탐색한 결과와 BFS로 탐색한 결과를 각각 출력하는 기본적인 그래프 탐색 문제이다. 입력은 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V와 M개의 간선들로 이루어진다. 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MN = 1001;

vector<int> g[MN]; //인접 리스트
bool vst[MN]; //방문 여부
void dfs(int N) { //DFS
    vst[N] = true; //방문 체크
    cout << N << ' '; //방문한 노드 번호 출력
    for(int e : g[N]) { //방문한 노드로부터 인접 리스트를 확인
        if(!vst[e]) dfs(e); //방문하지 않은 노드 방문
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, V; cin >> N >> M >> V;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //인접리스트 추가
        g[v].push_back(u);
    }
    for(int i = 1; i <= N; i++) { //정점 번호 오름차순으로 정렬
        sort(g[i].begin(), g[i].end());
    }
    dfs(V); //V번 정점부터 DFS
    cout << "\n" << V; //DFS출력 마지막을 나타내는 개행 후 BFS 시작정점 V출력
    queue<int> q; //BFS에 사용할 queue
    memset(vst, 0, sizeof(vst)); //방문 배열 초기화
    q.push(V); //시작 정점 queue에 추가
    vst[V] = true; //시작 정점 방문 체크
    while(!q.empty()) { //모든 정점을 방문할 때까지
        int now = q.front(); q.pop(); //queue의 첫 번째 pop
        for(int e : g[now]) { //인접리스트 확인
            if(!vst[e]) { //방문하지 않은 노드 발견할 경우
                cout << ' ' << e; //정점 출력
                vst[e] = 1; //방문 체크
                q.push(e); //queue에 추가
            }
        }
    }
}

방문하는 정점은 번호가 작은 것부터 우선적으로 방문해야하므로 우선 각 정점의 인접리스트를 오름차순으로 정렬한다.

    DFS를 우선적으로 출력하기 때문에 방문하지 않은 노드를 발견할 경우 곧바로 DFS로 탐색하여 정점을 출력하고 방문체크를 한다. 그 다음 그 노드로부터 인접리스트를 확인하여 더 탐색할 수 있는 정점이 있는지 확인한다. 있을 경우 재귀적으로 탐색한다.

    BFS는 queue를 이용한다. 방문한 노드를 체크하고 큐에 넣는다. 큐는 FIFO(First In First Out)이기 때문에 방문한 노드를 순서대로 확인할 수 있다. 시작정점 V를 큐에 넣고 방문 체크를 한다. 반복문은 큐가 빌때까지 반복한다. 큐의 첫 번째 원소를 pop한 후 그 원소의 인접 리스트를 확인한다. 방문하지 않은 노드를 발견할 경우 그 정점을 출력하고 방문체크를하고 큐에 push한다.

    백준에서는 개행이나 공백이 한 두개 더 출력되더라도 오답처리를 하지 않기 때문에 마지막일 경우 뒤에 공백이나 개행을 넣지 않기 위한 예외를 처리하지 않아도 된다.

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

이 문제는 BFS와 DFS 모두 풀 수 있는 문제이다. 글쓴이는 DFS를 이용하여 이 문제를 풀어보았다. 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stdbool.h>
#include <vector>
#include <cstring>

using namespace std;

const int MN = 51;

int map[MN][MN]; //인접행렬
bool vst[MN][MN]; //방문 여부
int di[8] = {1, 0, 0, -1, 1, -1, 1, -1}; //8가지 방향으로 이동을 나타냄
int dj[8] = {0, 1, -1, 0, 1, 1, -1, -1};
int w, h;
void dfs(int i, int j) {
    vst[i][j] = true; //방문 체크
    for(int d = 0; d < 8; d++) { //8가지 방향을 탐색
        int ni = i + di[d]; //다음 i좌표
        int nj = j + dj[d]; //다음 j좌표
        if(0 <= ni && ni < h && 0 <= nj && nj < w) { //지도를 벗어나는지 확인
            if(!vst[ni][nj] && map[ni][nj]) { //방문 여부와 땅인지 여부 확인
                dfs(ni, nj); //재귀로 DFS 탐색
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    while(true) { //0을 입력받을 때까지 반복
        cin >> w >> h;
        if(w == 0 && h == 0) break; //0이 두 개 입력될 경우 종료
        memset(map, 0, sizeof(map)); //테스트케이스마다 초기화
        memset(vst, 0, sizeof(vst)); //테스트케이스마다 초기화
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                cin >> map[i][j]; //지도 입력
            }
        }
        int cnt = 0;
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                if(map[i][j] && !vst[i][j]) { //땅이고 방문하지 않은 경우 DFS 탐색
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
    }
}

이 문제는 지도를 주어졌을 때 상하좌우 대각선으로 땅이 이어져 있다고 할 때 분리된 섬의 개수를 구하는 문제이다. 우리는 x, y좌표 형식으로 문제를 입력받기 때문에 위 코드의 di, dj 배열과 같이 8가지 방향을 나타낼 수 있다. 그림으로 나타내면 다음과 같이 나타낼 수 있다.

i, j에서 8가지 방향의 좌표를 더해 ni, nj 좌표를 구한다. 이때 지도를 벗어나는지를 확인해준다. 그렇지 않으면 Out of Bounds 에러가 발생할 수 있다.  그 다음 방문 여부와 땅인지의 여부를 확인하여 DFS 탐색을 계속한다. 이때 지도에서 땅인 부분의 DFS 횟수가 곧 섬의 개수인 것을 알 수 있다. 이전에 풀은 연결 요소의 개수와 구하는 방식이 비슷한 것을 알 수 있다. 차이점은 인접리스트 형식이 아니라 좌표형식으로 주어진 입력을 활용하여 좌표를 이동하며 DFS를 한다는 것이다.

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

이 문제는 방향이 없는 그래프를 주어졌을 때, 연결 요소의 개수를 구하는 문제이다. 즉 간선으로 연결되어 있는 집합의 개수가 총 몇 개인지를 출력하는 프로그램이다. bfs, dfs 모두 사용할 수 있는 문제지만 나는 dfs를 이용하였다. 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

bool visit[1001]; //방문 여부 판단
vector<int> g[1001]; //인접 리스트
void dfs(int n) { //DFS 함수
    visit[n] = 1;
    for(int nxt : g[n]) {
        if(!visit[nxt])
            dfs(nxt);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); //시간 감소
    int N, M; cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //비방향성 그래프이므로 인접 리스트에 u->v, v->u 모두 추가
        g[v].push_back(u);
    }
    int cnt = 0;
    for(int i = 1; i <= N; i++) { //1부터 N까지 dfs를 하며 연결 요소의 개수 카운트
        if(!visit[i]) { //방문하지 않은 번호에서만 dfs
            dfs(i);
            cnt++;
        }
    }
    cout << cnt;
}

이 문제는 가장 간단한 DFS 문제중 하나이다. 1번 노드부터 N번 노드까지 DFS를 이용해 전부 방문하고 나면 visit 배열을 통해 방문한 노드인지 확인할 수 있다. 그러므로 이미 방문한 DFS의 횟수를 통해 연결 요소의 개수를 셀 수 있다.

인접 행렬은 인접 리스트에 비해 많은 메모리를 소모하기 때문에 vector를 지원하는 C++에서는 인접 리스트를 사용하는 것이 굉장히 좋다. DFS에서 재귀를 이용해 탐색할 때 방문 여부를 언제 체크하냐에 따라 재귀의 횟수를 많이 줄일 수 있다. 위와 같이 재귀를 하기 전에 방문 여부를 확인할 경우가 있고 재귀를 들어가서 첫 줄에 방문했을 경우 return하는 방식으로 프로그램을 구현할 수 있다. 후자의 경우 불필요한 방문이 될 수 있으므로 위의 코드와 같이 전자 방식으로 구현하는 것이 더 효율적이다.