[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 8회차 과제 에디토리얼

8회차 - BFS, DFS

 

---

</1260> DFS와 BFS

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

DFS, BFS 기본 문제입니다. 각 방식을 구현하고 방문하는 노드를 출력하면 됩니다.

주의할 점 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 택해야 한다는 것입니다. 따라서 저는 입력을 받은 후 각 정점에 연결된 정점들에 대해 정렬을 한 번씩 진행해주었습니다.

주의할 점 2. 탐색 여부 배열을 공유한다면 초기화가 필요합니다.

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

vector<bool> vst;
vector<vector<int>> g;

void dfs(int cur) {
    vst[cur] = true;
    cout << cur << ' ';
    for (int nxt: g[cur]) {
        if (!vst[nxt]) dfs(nxt);
    }
}

void bfs(int cur) {
    queue<int> q;
    q.push(cur);
    vst[cur] = true;
    while (!q.empty()) {
        cur = q.front();
        q.pop();
        cout << cur << ' ';
        for (int nxt: g[cur]) {
            if (!vst[nxt]) {
                q.push(nxt);
                vst[nxt] = true;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, v;
    cin >> n >> m >> v;

    vst = vector<bool>(n + 1, false);
    g = vector<vector<int>>(n + 1);

    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // 작은 정점부터 방문하기 위해 정렬
    for (int i = 0; i < n + 1; i++) sort(g[i].begin(), g[i].end());

    dfs(v);
    cout << '\n';

    // 방문 여부 배열 초기화
    fill(vst.begin(), vst.end(), false);

    bfs(v);
    cout << '\n';
}

 

---

</1389> 케빈 베이컨의 6단계 법칙

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

언뜻 보면 최단 경로 알고리즘을 사용해야 할 것 같고, 태그에도 플로이드-워셜이 달려있지만, BFS만으로도 풀 수 있는 문제입니다.

그래프에서 모든 간선의 가중치가 1이기 때문입니다. 따라서 BFS는 가중치가 동일한 그래프에서 최단 경로를 보장합니다.

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);    
    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int mink = (int) 10e9; // 최소 케빈 베이컨의 수
    int ans = 0; // 최소 케빈 베이컨의 수를 가진 사람의 번호

    queue<pair<int, int>> q;

    for (int s = 1; s < n + 1; s++) {
        int cnt = 0;
        vector<bool> vst(n + 1, false);
        q.emplace(s, 0);
        vst[s] = true;
        while (!q.empty()) {
            int cur = q.front().first;
            int cnttmp = q.front().second;
            q.pop();
            cnt += cnttmp;
            for (int nxt: g[cur]) {
                if (!vst[nxt]) {
                    q.emplace(nxt, cnttmp + 1);
                    vst[nxt] = true;
                }
            }
        }

        // 갱신
        if (cnt < mink) {
            mink = cnt;
            ans = s;
        }
    }

    cout << ans << '\n';
}

 

---

</2178> 미로 탐색

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

이 문제도 케빈 베이컨의 6단계 법칙 문제와 비슷하게 최단 거리를 구해야 하나 모든 간선의 가중치가 1이므로 BFS로 해결할 수 있습니다. 다만 그 문제와는 다르게 그래프 연결 관계가 주어진 게 아니라 격자에서 상하좌우로 자유롭게 이동할 수 있습니다.

저는 이런 문제에서 dx 배열과 dy 배열을 맨위에 선언해두고 for (int k = 0; k < 4; k++) 이렇게 네번 반복해서 상하좌우로 움직이는 것을 구현합니다.

주의할 점은 움직일 때마다 좌표가 유효한 좌표인지(격자 내에 존재하는 좌표인지)와 이동할 수 있는 좌표인지(그 좌표에 적힌 수가 1인지) 확인해야 한다는 것입니다.

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

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<string> maze(n);
    vector<vector<bool>> vst(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++) cin >> maze[i];

    queue<vector<int>> q;
    q.push({0, 0, 1});
    vst[0][0] = true;

    int ans;
    while (!q.empty()) {
        int curx = q.front()[0];
        int cury = q.front()[1];
        int cnt = q.front()[2];
        q.pop();
        if (curx == n - 1 && cury == m - 1) ans = cnt;

        for (int k = 0; k < 4; k++) {
            int nxtx = curx + dx[k];
            int nxty = cury + dy[k];
            if (nxtx >= 0 && nxtx < n && nxty >= 0 && nxty < m && maze[nxtx][nxty] == '1' && !vst[nxtx][nxty]) {
                q.push({nxtx, nxty, cnt + 1});
                vst[nxtx][nxty] = true;
            }
        }
    }

    cout << ans << '\n';
}

 

---

</7576> 토마토

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

하루에 토마토가 주변을 한 칸씩 익게 만들기 때문에 BFS로 풀 수 있는 문제입니다. 그래서 저는 queue에 익은 토마토를 전부 넣은 다음, BFS를 돌리면서 해당 칸이 익는 데에 걸리는 일수를 의미하는 ans 배열을 채워주었습니다.

BFS는 방문 여부를 체크하는 visited 배열이 필요한데, 여기서는 box[ni][nj] = 1; 을 통해서 방문 여부를 표시했습니다.

 

이 문제는 시작점이 여러개라는 점에서 multi source BFS라고 볼 수 있습니다.

multi source BFS도 시작점이 단일인 BFS와 동일하게 올바르게 작동하는 이유를 설명하는 방식에는 여러가지가 있을 수 있습니다. 그 중 제가 느끼기에 가장 직관적이었던 방식을 간략히 정리해보면 여러 시작점과 연결된 하나의 가상의 시작점을 가정하는 것입니다. 즉 하나의 가상의 시작점이 있다고 생각하고 그 시작점에서 여러 점으로 아무 비용 없이 이동할 수 있다고 생각하는 것입니다.

 

아, 그리고 이 문제의 3차원 버전인 토마토 문제도 있습니다. 관심 있으신 분들은 이 문제도 같이 풀어보세요!

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

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
vector<vector<int>> box;
vector<vector<int>> ans;
int m, n;

void bfs() {
    queue<pair<int, int>> q;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (box[i][j] == 1) {
                q.emplace(i, j);
                ans[i][j] = 0;
            }
        }
    }

    while (!q.empty()) {
        int curi = q.front().first;
        int curj = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int ni = curi + dx[k];
            int nj = curj + dy[k];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m && box[ni][nj] == 0) {
                q.emplace(ni, nj);
                box[ni][nj] = 1;
                ans[ni][nj] = ans[curi][curj] + 1;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> m >> n;
    box = vector<vector<int>>(n, vector<int>(m));
    ans = vector<vector<int>>(n, vector<int>(m, -1));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> box[i][j];
        }
    }

    bfs();

    int maxa = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (box[i][j] == -1) continue;
            if (ans[i][j] == -1) {
                cout << -1 << '\n';
                return 0;
            } else {
                maxa = max(maxa, ans[i][j]);
            }
        }
    }

    cout << maxa << '\n';
}

 

---

</1707> 이분 그래프

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

이 문제를 풀기 위해서는 이분 그래프의 정의를 잘 이해해야 합니다. 하지만 문제에 적힌 내용만으로는 명확히 이해하기 어려울 수도 있어서 정리를 해보겠습니다.

 

이분 그래프는 그래프의 정점을 두 개의 그룹으로 나눌 수 있으며, 같은 그룹에 속한 정점끼리는 서로 연결되지 않는 그래프를 말합니다.

즉, 어떤 그래프에서 모든 간선이 "서로 다른 두 그룹"을 연결하는 형태라면, 그 그래프는 이분 그래프입니다. 이분 그래프는 1) 같은 그룹 내의 정점끼리는 직접 연결될 수 없고, 2) 반드시 다른 그룹의 정점과만 연결되어야 합니다.

 

그래서 보통 이분 그래프 문제에서 두 그룹으로 나누는 걸 직관적으로 보이기 위해 두 색으로 그래프의 정점들을 칠하는 것으로 비유를 많이 하는데요, 저도 color라는 배열을 만들고 색을 0 아니면 1로 해서 그룹을 구분하였습니다.

 

자, 그러면 이분 그래프인지 아닌지는 어떻게 판별해야 할까요? 원리만 간단히 말하자면 이렇습니다.

우선 DFS를 진행합니다. 첫 번째 노드는 임의의 색으로 칠해주면 됩니다.

만약 현재 정점이 이전에 방문한 적 없는 정점이라면, 새롭게 색을 칠해줘야 합니다. 이 때 직전 정점의 색과는 다른 색으로 칠해야 합니다.

만약 현재 정점이 이전에 방문한 적 있는 정점이라면, 직전 정점의 색이랑 동일한지 아닌지 체크해주어야 합니다. 동일하다면 이분 그래프인거죠!

이렇게 모든 정점에 대해서 DFS를 호출하면 됩니다. 모든 정점에 대해서 해야 하는 이유는 그래프가 꼭 모든 정점이 연결되어 있다고 보장되어 있지 않기 때문입니다.

 

이 문제는 이분 그래프에 대해서 이해하고 있고 판별법을 알아야 풀 수 있으니까 약간 어렵게 느껴질 수도 있을 것 같습니다. 그러나 이분 그래프 입문 문제로 참 좋다고 생각합니다!

 

p.s. DFS 구현 팁

DFS를 구현할 때, 방문 처리를 언제 하느냐에 따라 두 가지 방식이 존재합니다.
1. 함수 호출 전에 방문 처리 (next 방문 처리)
다음 정점을 방문하기 전에(dfs 함수를 호출하기 전에) 방문 처리를 하는 방식입니다.

void dfs(int current) {
    for (int next : graph[current]) {
        if (!visited[next]) {
            visited[next] = true;  // 다음 노드를 방문하기 전에 처리
            dfs(next);
        }
    }
}

2. 함수 내부에서 방문 처리 (current 방문 처리)
현재 정점을 방문한 후에(dfs 함수를 호출한 후에) 방문 처리를 하는 방식입니다.

void dfs(int current) {
    visited[current] = true;  // 방문 처리를 현재 노드에서 수행

    for (int next : graph[current]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

둘 중 어떤 방법으로 구현하든 상관없지만, 중요한 점은 둘을 헷갈려서 혼동하거나 혼용하면 안 된다는 점입니다! 실수하기 쉬운 포인트라고 생각해서 주의하시면 좋을 것 같습니다. 참고로, 이 문제의 풀이에서는 두 번째 방법을 사용했습니다. 

 

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

int k, v, e;
vector<vector<int>> g;
vector<int> color; // 방문 여부 배열 + 색 기록 배열
bool isBipartite;

void dfs(int cur, int prec) {
    // curc: 현재 색 (이전 색과 다른 색으로 선택)
    int curc;
    if (prec == 0) curc = 1;
    else curc = 0;
    // color 배열에 방금 구한 현재 색 (curc) 기록
    color[cur] = curc;
    // cur과 인접한 정점 nxt들에 대해
    for (int nxt: g[cur]) {
        // nxt가 방문한 적 없는 정점이라면, dfs 호출
        if (color[nxt] == -1) dfs(nxt, curc);
        // nxt가 방문한 적 있는 정점이라면, 현재 색과 같은 색인지 체크
        else if (color[nxt] == curc) isBipartite = false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> k;
    while (k--) {
        cin >> v >> e;
        g = vector<vector<int>>(v + 1);
        color = vector<int>(v + 1, -1); // 방문하지 않았다는 의미로 -1으로 초기화

        for (int i = 0; i < e; i++) {
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
        }

        isBipartite = true; // true로 초기화
        for (int i = 1; i < v + 1; i++) {
            if (color[i] == -1) { // 아직 방문하지 않았다면
                dfs(i, 0);
            }
        }

        if (isBipartite) cout << "YES\n";
        else cout << "NO\n";
    }
}

 

---

</26153> 로하의 농사

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

살짝 빡센 구현을 곁들인 dfs이자 백트래킹 문제입니다.

이전 파이프 방향을 저장해두었다가 이전 파이프 방향과 현재 파이프 방향이 같은지 아닌지에 따라 남은 이동 가능 횟수(p)를 다르게 감소시키는 것이 핵심입니다.

상하좌우로 4방향을 탐색하며, 남은 이동 가능 횟수(p)가 남아 있다면 dfs를 실행하여 가능한 모든 경로를 탐색하도록 구현했습니다. 그 과정에서 ans에 최대 점수를 저장하였습니다.

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

int n, m, si, sj, p, ans;
vector<vector<int>> g;
vector<vector<bool>> vst;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
// 0: down, 1: up, 2: right, 3: left

void dfs(int curi, int curj, int pre, int res) {
    ans = max(ans, res);
    if (curi < 0 || curi >= n || curj < 0 || curj >= m) return;
    if (pre != -1 && vst[curi][curj]) return;

    for (int k = 0; k < 4; k++) {
        int nxti = curi + dx[k];
        int nxtj = curj + dy[k];

        int prevp = p;
        if (pre != -1) {
            if (pre == k) p -= 1;
            else p -= 2;
        }

        if (p >= 0) {
            vst[curi][curj] = true;
            dfs(nxti, nxtj, k, res + g[curi][curj]);
            vst[curi][curj] = false;
        }

        p = prevp; // 원상복구
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    g = vector<vector<int>>(n, vector<int>(m));
    vst = vector<vector<bool>>(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }

    cin >> si >> sj >> p;

    vst[si][sj] = true;
    dfs(si, sj, -1, 0);

    cout << ans << '\n';
}