Computer Science & Engineering

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

이 문제는 BFS와 DFS모두 풀 수 있는 문제이다. 문제 알고리즘 분류는 깊이 우선 탐색이지만 글쓴이는 BFS를 이용하여 풀었다. 문제는 인접행렬이 주어졌을 때 2-친구의 수가 가장 많은 사람을 구하는 것이다. 2-친구는 두 사람이 친구이거나 한 사람을 건너서 친구인 친구를 말한다. 즉 깊이가 2 이하로 알고 있는 친구의 수이다. 코드는 다음과 같다.

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

const int MN = 51;

vector<int> g[MN]; //인접 리스트
bool vst[MN]; //방문배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int rst = 0;
    int N; cin >> N;
    for(int i = 0; i < N; i++) {
        string s; cin >> s; //한 줄씩 string으로 입력 받음
        for(int j = 0; j < s.size(); j++) {
            if(s[j] == 'Y') { //친구인 경우 인접리스트에 추가
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    for(int i = 0; i < N; i++) { //0번부터 N-1번까지 2-친구의 수 구하기
        queue<int> q; //BFS에 이용할 큐
        memset(vst, 0, sizeof(vst)); //방문배열 초기화
        vst[i] = true; //자기 자신 방문 체크
        int cnt = 0;
        for(int e : g[i]) { //자기 자신의 친구 체크
            if(!vst[e]) {
                vst[e] = 1;
                cnt++;
                q.push(e);
            }
        }
        while(!q.empty()) { //자기 자신의 친구의 친구들만 확인
            int now = q.front(); q.pop();
            for(int e : g[now]) {
                if(!vst[e]) { //친구가 아닌 경우. 즉 친구의 친구인 경우
                    vst[e] = 1;
                    cnt++;
                }
            }
        }
        rst = max(rst, cnt); //2-친구가 가장 많은 사람의 2-친구 수 갱신
    }
    cout << rst;
}

이 문제는 깊이를 확인할 필요 없이 깊이가 2까지만 탐색하면 되므로 0번부터 N-1번까지의 친구를 큐에 넣고 수를 세고 큐가 빌 때까지 그 친구들의 친구의 수만 세주면 된다. 이때 친구의 친구를 발견할 경우 큐에 넣지 않으면 깊이가 2인 친구까지만 탐색할 수 있다. 그렇게 구한 2-친구의 수의 최대값을 출력하면 간단히 답을 구할 수 있다.

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한다.

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