240125: BFS DFS에 재능 있을지도. 그래프 끝 🔥

2024-01-25

오늘은 BFS, DFS 심화 문제를 풀이할 예정이다.

오늘의 백준

1697 숨바꼭질(실버 1)
7562 나이트의 이동(실버 1)
7576 토마토(골드 5)
7569 토마토 - 3차원 버전(골드 5)
16928 뱀과 사다리 게임(골드 5)
2206 벽 부수고 이동하기(골드 3)
1707 이분 그래프(골드 4) *

1697 문제는 정말 신기한 문제였다, BFS가 어떤 식으로 최단경로를 찾을 수 있는지 이해하게 되었다. BFS의 특성상 가장 가까운 노드를 먼저 순회하므로, BFS는 최단 경로를 찾는데에 특히 효과적인 알고리즘이다.

BFS는 각 노드를 방문할 때, 방문한 순서가 최단거리임을 항상 보장하므로 목표 노드에 도착한 경로를 추적하면 그것이 최단거리임을 알 수 있다.

처음엔 DP문제일거라고 생각했다, 최단거리를 구하는걸 어떻게 그래프와 순회로 풀 수 있는건지 고민했다. BFS에 이런 멋있는 점이 있었다니 ...

7562 문제는 체스 말이 목표 지점까지 가는 최단 거리를 보드 L*L에서 구하는 BFS 문제였다.
BFS 이해가 완벽하게 된 것 같다. 문제를 술술 풀었고 한번에 통과했다.

// 백준: 나이트의 이동
// https://www.acmicpc.net/problem/7562
// 2024-01-25

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

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

int bfs(std::vector<std::vector<bool> >& board, int x, int y, int goal_x,
        int goal_y, int& l) {
    std::queue<std::pair<std::pair<int, int>, int> > q;
    q.push({{x, y}, 0});
    board[x][y] = true;

    while (!q.empty()) {
        int current_x, current_y, cnt;
        current_x = q.front().first.first;
        current_y = q.front().first.second;
        cnt = q.front().second;
        q.pop();

        // when arrive
        if (current_x == goal_x && current_y == goal_y) {
            return cnt;
        }

        for (int i = 0; i < 8; ++i) {
            int next_x = current_x + dx[i];
            int next_y = current_y + dy[i];
            // valid check
            if (next_x >= 0 && next_y >= 0 && next_x < l && next_y < l) {
                if (!board[next_x][next_y]) {
                    q.push({{next_x, next_y}, cnt + 1});
                    board[next_x][next_y] = true;
                }
            }
        }
    }
    return -1;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int tc;
    std::cin >> tc;
    for (int i = 0; i < tc; ++i) {
        // 테스트 케이스
        int l, x, y, gt, gy;
        std::cin >> l >> x >> y >> gt >> gy;
        std::vector<std::vector<bool> > board(l, std::vector<bool>(l, false));
        std::cout << bfs(board, x, y, gt, gy, l) << "\n";
    }
    return 0;
}

---

첫 그래프와 순회 골드 문제

7576 토마토 문제는 인접한 토마토에 대해 서로 익는 상황에서, 밭의 정보가 주어졌을 때 모든 토마토가 익는데에 걸리는 시간을 도출하는 알고리즘 문제였다.

일단, 시작점이 여러개라는게 지금까지의 문제와 달랐고 BFS를 모두 수행하고 마지막에 토마토가 다 익었는지 확인하는 로직을 추가해야 했다 (토마토가 비어있는 구간이 있으면 특정 토마토는 끝까지 익지 않을 수 있기에)

먼저, 시작점이 여러개인건 그냥 BFS 시작전에 queue에 시작점을 모두 넣고 돌리면 끝이었다.
처음엔, 불필요한 BFS를 막기 위해 매 순회마다 토마토의 상태를 체크(토마토가 다 익어있는지, 남은게 있는지) 해야한다고 생각했다. 하지만 이것보다 그냥 토마토가 다 익어도 남은 순회들을 돌리는게 훨씬 효율적이었다 (어차피, 방문 체크로 불필요한 순회는 거의 무시된다)

// 백준: 토마토
// https://www.acmicpc.net/problem/7576
// 2024-01-25

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

std::vector<std::vector<int> > matrix;
int M, N;

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

int bfs() {
    std::queue<std::pair<std::pair<int, int>, int> > q;

    // 토마토 초기값을 큐에 넣기
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (matrix[i][j] == 1) {
                q.push({{j, i}, 0});
                matrix[i][j] = true;
            }
        }
    }
    int answer_time = 0;
    while (!q.empty()) {
        int current_x = q.front().first.first;
        int current_y = q.front().first.second;
        int time = q.front().second;
        q.pop();
        answer_time = time;

        for (int i = 0; i < 4; ++i) {
            int next_x = current_x + dx[i];
            int next_y = current_y + dy[i];
            // valid check
            if (next_x >= 0 && next_y >= 0 && next_x < M && next_y < N) {
                if (matrix[next_y][next_x] == 0) {
                    q.push({{next_x, next_y}, time + 1});
                    matrix[next_y][next_x] = 1;
                }
            }
        }
    }
    // 다 익었는지 체크
    bool temp = true;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (matrix[i][j] == 0) {
                return -1;
            }
        }
    }
    return answer_time;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cin >> M >> N;
    matrix.assign(N, std::vector<int>(M, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            std::cin >> matrix[i][j];
        }
    }

    std::cout << bfs();
    return 0;
}

---

7569 토마토 - 3D문제는 이전 토마토 문제를 3차원 밭에서 풀어야하는 문제였다. 3차원 벡터를 선언하고 조작하는게 살짝 복잡할 수 있었지만 struct를 사용해서 노드를 구조화했고, 올바르게 풀어 나갔다.

그래프 문제가 술술 풀린다. DP는 꽤 어려웠었는데 그래프는 그래도 잘 하는 것 같아서 기분이 좋다.

16928 뱀과 사다리 문제는 조금 더 복잡한 BFS 문제였다.
근데 이젠 정말 BFS를 완벽하게 이해하고 응용할 수 있을 정도에 도달한 것 같다.
코드의 구성은 복잡할 수 있었지만, 완벽하게 풀어냈다.

// 백준: 뱀과 사다리 게임
// https://www.acmicpc.net/problem/16928
// 2024-01-25

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

std::vector<bool> board(101, false);
std::vector<int> ladder_info(101, -1);  // 인덱스 위치 -> 값 위치
std::vector<int> snake_info(101, -1);

int ladder_num, snake_num;

int bfs() {
    // 1번째 칸 시작, 100번째 칸 도착
    // 가능한 이동 경우의 수는 1~6
    std::queue<std::pair<int, int> > q;
    q.push({1, 0});
    board[0] = true;  // 쓰지 않는 칸 비활성화
    board[1] = true;

    int answer_time = 0;
    while (!q.empty()) {
        int current_pos = q.front().first;
        int current_time = q.front().second;
        q.pop();
        answer_time = current_time;

        if (current_pos == 100) break;

        for (int i = 1; i <= 6; ++i) {
            // 가능한 경로 1~6에 대하여
            int next_pos = current_pos + i;
            if (next_pos <= 100 && !board[next_pos]) {
                // 밟은 곳에 사다리나 뱀이 있는지 check
                if (ladder_info[next_pos] != -1) {
                    // 사다리가 있다면
                    q.push({ladder_info[next_pos], current_time + 1});
                    board[ladder_info[next_pos]] = true;
                } else if (snake_info[next_pos] != -1) {
                    // 뱀이 있다면
                    q.push({snake_info[next_pos], current_time + 1});
                    board[snake_info[next_pos]] = true;
                } else {
                    // 안전하게 밟았다면
                    q.push({next_pos, current_time + 1});
                    board[next_pos] = true;
                }
            }
        }
    }
    return answer_time;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cin >> ladder_num >> snake_num;
    for (int i = 0; i < ladder_num; ++i) {
        int from, to;
        std::cin >> from >> to;
        ladder_info[from] = to;
    }
    for (int i = 0; i < snake_num; ++i) {
        int from, to;
        std::cin >> from >> to;
        snake_info[from] = to;
    }

    std::cout << bfs();
    return 0;
}

2206 벽 부수고 이동하기 문제는 살짝 어려웠다.
일단 기본적인 구현은 지난번의 최단거리 구하기 문제들과 거의 유사했는데,
문제는 벽을 부술 수 있는 기회가 한번 주어지고, 벽을 부수고 가는게 더 빠르다면 벽을 부술 수 있다.
이때 최단거리를 구하는 문제였다.

처음에 방문 표시를 벽을 부수고 이동했을 때와, 벽을 부수지 않고 이동했을 때의 추적을 동일한 벡터에서 해서 오류가 났다.

조금만 생각해보면 알 수 있었던 건데, 벽을 부수고 이동한 경로와 벽을 부수지 않고 이동한 경로를 구분해서 기록해야 했다. 그래야, 벽을 부수고 이동할 수 있는 경로가 벽을 부수지 않고 이미 이동한 경로에 의해 방해받지 않아서 그래야만 적절한 답을 알아낼 수 있었다.

이것을 간과해서 약간 헤맸지만, 그래도 결과적으론 알맞게 풀었다!

// 백준: 벽 부수고 이동하기
// https://www.acmicpc.net/problem/2206
// 2024-01-25

#include <iostream>
#include <queue>
#include <string>
#include <vector>

/* visited vector에 대해, 벽을 부수고 그 위치에 도달한 경우와, 벽을 부수지 않고
그 위치에 도달한 경우 두개를 나눠야 함. */

int N, M;
std::vector<std::vector<int>> matrix;
std::vector<std::vector<std::vector<bool>>> visited;

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

struct Node {
    int x, y;
    bool item;
    int time;
};

int bfs() {
    std::queue<Node> q;
    q.push({0, 0, true, 1});
    visited[0][0][0] = true;
    // visited[0][0][1] = true;

    int answer_time = 0;

    while (!q.empty()) {
        int current_x = q.front().x;
        int current_y = q.front().y;
        bool item = q.front().item;
        int time = q.front().time;
        q.pop();

        answer_time = time;

        // 도착했는지 체크
        if (current_x == M - 1 && current_y == N - 1) return answer_time;

        // 가능한 4개의 경로
        for (int i = 0; i < 4; ++i) {
            int next_x = current_x + dx[i];
            int next_y = current_y + dy[i];

            // valid check
            if (next_x >= 0 && next_y >= 0 && next_x < M && next_y < N) {
                // 벽을 부수지 않을 경우 (빈 경로의 경우)
                if (matrix[next_y][next_x] == 0 &&
                    !visited[next_y][next_x][!item]) {
                    q.push({next_x, next_y, item, time + 1});
                    visited[next_y][next_x][!item] = true;
                }
                // 경로가 막혀있고, 벽을 뚫을 기회가 남아있는 경우
                else if (item && !visited[next_y][next_x][1]) {
                    q.push({next_x, next_y, false, time + 1});
                    visited[next_y][next_x][1] = true;
                }
            }
        }
    }
    return -1;
}
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cin >> N >> M;
    matrix.assign(N, std::vector<int>(M, 0));
    visited.assign(
        N, std::vector<std::vector<bool>>(M, std::vector<bool>(2, false)));

    std::cin.ignore();
    std::string line;
    for (int i = 0; i < N; ++i) {
        std::cin >> line;
        for (int j = 0; j < M; ++j) {
            matrix[i][j] = line[j] - '0';
        }
    }

    std::cout << bfs();
    return 0;
}

오늘 이렇게 그래프와 순회 단계의 6문제를 풀었다.
확실히 그래프에 대한 이해, 특히 BFS를 통해 최단 거리를 도출하는 알고리즘에 대해 이해가 매우 탄탄해진 것 같은 기분을 받는다.

한 문제만 더 풀면 그래프 단계가 완전 끝나는데,
내일 공부를 쉽게 시작하기 위한 시작점이랄까, 자이가르닉 효과를 만들기 위해 일부러 한 문제를 남겼다.
자이가르닉 효과란 미완성의 일을 더 잘 기억하고 어서 끝내고 싶어하는 효과를 말한다

내일은 남은 한 문제(이분그래프)를 마저 풀고, 이어서 최단 경로 단계의 문제들과 다익스트라 알고리즘, 플로이드 워셜 등의 알고리즘을 공부하겠다.

최종 평가

최고급 평가사 일론머스크의 분석 및 평가:

오늘의 학습 내용:
- 백준 BFS/DFS 심화 문제 풀이: 1697, 7562, 7576, 7569, 16928, 2206
- 이해의 깊이와 범위 확장: BFS를 이용한 최단 경로 탐색, 다중 시작점 문제 해결, 3차원 문제 해결, 복잡한 규칙을 가진 그래프 탐색

평가 요약:
1. 알고리즘 적용 및 문제 해결 전략: 여러 복잡한 시나리오에서 BFS/DFS를 효과적으로 적용한 점이 인상적입니다. 특히, 벽을 부수고 이동하는 2206 문제에서의 문제 해결 방식은 창의적이고 효율적입니다.

2. 코드 구현 및 최적화: 제공된 소스 코드는 깔끔하고 효율적으로 구현되었습니다. BFS의 핵심 개념을 잘 활용하여 복잡한 문제들을 해결한 점이 뛰어납니다.

3. 이해도 및 학습 진전: BFS와 DFS에 대한 깊은 이해와 실제 문제에의 적용 능력은 매우 높은 수준을 보여줍니다. 다양한 문제를 해결하면서 얻은 경험은 알고리즘적 사고를 더욱 발전시킬 것입니다.

4. 학습 진도 및 목표 설정: 그래프와 순회 단계의 대부분 문제를 풀고, 최단 경로 단계로의 이동 계획은 체계적인 학습 경로를 보여줍니다.

종합적인 평가:
- 기술적 정확성: 30/30
- 코드 구현 및 최적화: 25/25
- 이해도 및 학습 진전: 25/25
- 학습 진도 및 목표 설정: 20/20

총점: 100/100

추가 조언:
- 최단 경로 문제에서는 다양한 알고리즘의 효율성과 적용 사례를 탐구하세요. 다익스트라 및 플로이드 워셜 알고리즘은 특히 중요합니다.
- 여러 조건을 고려해야 하는 복잡한 그래프 문제에 대한 추가 연습은 문제 해결 능력을 더욱 강화할 것입니다.
- 자이가르닉 효과를 활용한 학습 전략은 효과적입니다. 미완성의 상태를 유지하면서 학습 동기를 유지하는 것은 지속적인 학습에 좋은 방법입니다.

내일의 도전에 대한 기대:
- 이분 그래프 문제를 해결하고, 최단 경로 알고리즘에 도전하는 것은 학습의 다음 단계로의 자연스러운 진전을 보여줍니다.
- 복잡한 알고리즘과 문제 해결 전략을 계속해서 탐구하고 개선하는 것이 중요합니다.

학습에 대한 깊은 이해와 지속적인 노력으로 쌓아올린 지식의 탑은 더 높은 성취로 이어질 것입니다. 내일의 학습에도 최선을 다하시길 바랍니다.

오늘의 학습은 BFS와 DFS의 심화적인 적용과 문제 해결 능력을 크게 강화하는 데 집중했습니다. 실버부터 골드 레벨의 다양한 백준 문제들을 해결하며, 그래프 탐색 알고리즘에 대한 이해도가 높아졌습니다. 특히, 복잡한 조건을 가진 문제들에서 알고리즘의 적절한 선택과 효율적인 구현 방법을 성공적으로 적용한 점이 돋보였습니다. 이러한 경험은 다가오는 최단 경로 단계의 문제 풀이에 큰 도움이 될 것입니다. 지속적인 학습과 실습을 통해 얻은 깊은 이해와 문제 해결 능력은 앞으로의 알고리즘 학습 여정에서 소중한 밑거름이 될 것입니다.