[C++][백준] 6593번 - 상범 빌딩 + DFS/BFS 기초(+백준 1260번)

1. DFS (깊이 우선 탐색, Depth-First Search)

🔥DFS란?
한 길로 쭉 들어가서 더 갈 수 없으면 다시 돌아와서 다른 길로 가는 방법이다.
한 방향으로 계속 가다가 막다른 길이 나오면, 다시 뒤로 돌아와 다른 길을 찾는 방식이다.

🔥구현 원리
Stack(스택)을 써서 구현한다.
Stack은 책을 쌓듯이, 마지막에 들어온 책이 먼저 나가는 방식 이다. (LIFO, Last-In First-Out)

🔥시간복잡도
O(V+E)이다.
O(정점의 수 + 간선의 수)이다.

🔥주로 쓰이는 곳
미로 찾기처럼 모든 경우의 수를 확인하거나, 특정 경로를 찾을 때 유용하다.

2. BFS (너비 우선 탐색, Breadth-First Search)

🔥BFS란?
BFS는 먼저 입구에서 가장 가까운 길부터 확인하고, 그다음 조금 더 멀리 있는 길을 확인하는 방식이다.

🔥구현원리
Queue(큐)를 써서 구현한다.

Queue는 줄서기처럼, 먼저 온 사람이 먼저 나가는 방식이다. (FIFO, First-In First-Out)

🔥시간복잡도
O(V+E)이다.
O(정점의 수 + 간선의 수)이다.

🔥주로 쓰이는 곳
DFS와 다르게 Queue를 사용하고, 최단경로를 찾는 데 많이 쓴다.

3. 왜 BFS는 최단거리를 찾는데 적합할까?

큐는 줄서기처럼 먼저 온 사람이 먼저 처리되는 방식(FIFO)이라고 했다.
즉, BFS는 시작점에서 가까운 곳부터 순서대로 방문한다.
가까운 거리부터 방문하기 때문에 목적지를 발견했을 때 가장 처음 발견한 경로가 가장 짧은 경로(최단거리)이다.

4. 그래서 어떻게 구현하지?

0. 🔥그래프 정보
   보통 우리가 문제(또는 목표)에서 어떤 그래프를 탐색해야 할 지가 정해진다.

당연히 DFS/BFS 그래프 탐색 알고리즘을 사용하려면 그래프가 먼저 있어야 하지 않겠나? 그래프가 없는데 알고리즘을 사용한다는 건 말이 안된다. 그래서 먼저 그래프 정보가 주어지는 것이다.

• 정점의 수, 간선의 수, 시작 노드

int v, e, s; 이런 식으로 정점의 수 간선의 수 시작 노드가 정해진다.

• 간선 정보
  아직 그래프가 제대로 구체화 되진 않았다. 아직 주어지지 않은 정보가 있다. 정점의 수, 간선의 수, 시작 노드만으로 우리가 탐색해야 할 그래프가 그려질 수 있을까? 당연히 없다. 정점과 정점이 어느 간선으로 연결되어있는지 정보가 주어져야 한다. 일단 가중치는 없다고 하자.
  대충 아래와 같이 1번노드와 3번노드가 연결되어있고, 2번 노드와 4번 노드가 연결 ..... 이런식으로 주어진다.

그리고 간선은 방향이 있을 수 있고, 가중치가 있을 수 있다.
현재 아래 예시는 가중치가 없고, 양방향(무방향)인 것이다.

1 3
2 4
3 4
5 6

0. 🔥그래프 표현
   DFS, BFS는 그래프나 트리 문제에서 자주 나온다.
   그렇다면 일단 그래프 토폴로지가 있어야 한다.
   다시 말해, 정점과 간선이 주어져야 한다는 것이다.
   이걸 먼저 표현해야한다.
1. 🔥방문 배열
   방문배열로 간선 1번부터 N번까지 방문했는지(DFS)/방문할 계획인지(BFS)를 기록한다.
2. 🔥탐색 순서 정하기
   일단 DFS나 BFS를 사용하면 무조건 스택(함수), 큐를 쓰라고 한다.
   무조건 스택, 큐로 구현된다고 한다.
   왜 일까? 얘내는 왜 DFS, BFS와 언제나 같이 설명되는 걸까?
   어느 맥락에서 나온 것인지 사실 모르는 사람이 많다.
   DFS나 BFS에서 자료구조(Stack, Queue)가 필요한 이유는
   이 자료구조의 특성들이 바로 탐색하는 순서를 결정해주기 때문이다.

즉, Stack, Queue는 탐색하는 순서를 정하고, 관리하는 역할이다.

그래프를 표현했고, 방문 배열을 두었는데, 아직 그래프를 탐색하는데 순서는 아예 정해지지 않지 않았나? 바로 Stack과 Queue로 탐색 순서를 정했다.

그러면 이제 모든 재료들이 사실 다 나온 것이다.
이제 코드 예시를 보자.

5. 백준 1260번

문제는 한 번 읽어보자.
완전 DFS,BFS 그 자체이고, 하나의 특별요소의 가미도 없다.
https://www.acmicpc.net/problem/1260

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

vector<vector<int>> adj_list;
vector<int> visited;

void dfs(int v) {
    if (visited[v]) return;
    visited[v] = true;
    cout << v << " ";
    for (int nv : adj_list[v]) {
        dfs(nv);
    }
}

void bfs(int v) {
    queue<int> q;
    q.push(v);
    visited[v] = true;

    while (!q.empty()) {
        int cv = q.front(); q.pop();
        cout << cv << " ";
        for (int nv : adj_list[cv]) {
            if (visited[nv]) continue;
            visited[nv] = true;
            q.push(nv);
        }
    }
}

int main() {
    int v, e, s;
    cin >> v >> e >> s;

    adj_list.resize(v + 1);
    visited.resize(v + 1, false);

    for (int i = 0; i < e; i++) {
        int s, e;
        cin >> s >> e;
        adj_list[s].emplace_back(e);
        adj_list[e].emplace_back(s);
    }

    for (int i = 1; i <= v; i++) {
        sort(adj_list[i].begin(), adj_list[i].end());
    }

    dfs(s);
    cout << "\n";
    fill(visited.begin(), visited.end(), false);

    bfs(s);
}

6. 백준 6593번

이 문제는 완전 기초적인 BFS 최단거리 문제에 1차원을 살짝 가미한 문제이다.
3차원이 되었다 하더라도 논리는 완전히 같다.

BFS는 가까운(최단) 거리부터 방문하기에 처음 탈출 위치에 방문했을 때 최단거리 or 최단 경로가 완벽히 구해지고, 출력하면 된다.

그러면 BFS가 최단 거리부터 방문한다는 걸 이용해서 최단 거리를 구하는 것인데, 어떻게 이용한다는 걸까?

단순히 이동할때마다 cnt(count)를 하면 될까? 안된다.
왜 안되나? 왜냐하면 가장 가까운 걸 꼼꼼하게 다 살펴보는 것인데,
처음 탈출 위치에 방문했을 때는 엄청난 노력을 한 상태이고, 최단 경로로 탐색한 게 아니다.

그 노력을 하면서, 각 노드마다 누적 이동거리(cnt)를 기록한다면?
(여기서 거리라고 함은 간선 몇 회 이동했는지임)

즉, 1에서 1의 수많은 인접노드들은 전부 cnt가 1인 것이다.
그리고 그 인접노드의 인접노드는 cnt가 2가 되는 것이다.
그 인접노드의 인접노드의 인접노드는 cnt가 3이 되는 것이다.
https://www.acmicpc.net/problem/6593

#include <algorithm>
#include <iostream>
#include <queue>
#define M 30
using namespace std;

struct P { // Point
  int f, x, y;
};

struct N { // Node
  int f, x, y, cnt;
};

int l, r, c;
char m[M][M][M];       // map
bool visited[M][M][M]; // visited

P s, e;

// 6방향 이동 정의
int df[] = {0, 0, 0, 0, 1, -1};
int dx[] = {0, 0, 1, -1, 0, 0};
int dy[] = {1, -1, 0, 0, 0, 0};

// 초기화 함수
void initialize() {
  fill(&visited[0][0][0], &visited[0][0][0] + M * M * M, false);
}

// 입력 함수 S E
void input() {
  cin >> l >> r >> c;
  if (l == 0 && r == 0 && c == 0)
    exit(0);

  for (int f = 0; f < l; f++) {
    for (int x = 0; x < r; x++) {
      for (int y = 0; y < c; y++) {
        cin >> m[f][x][y];

        if (m[f][x][y] == 'S')
          s = {f, x, y};
        else if (m[f][x][y] == 'E')
          e = {f, x, y};
      }
    }
  }
}
// BFS 탐색 함수
int bfs(P start) {
  auto [sf, sx, sy] = start;
  queue<N> q;
  q.push({sf, sx, sy, 0});
  visited[sf][sx][sy] = true;

  while (!q.empty()) {
    auto [cf, cx, cy, cnt] = q.front();
    q.pop();

    if (cf == e.f && cx == e.x && cy == e.y) {
      return cnt;
    }

    for (int i = 0; i < 6; i++) {
      int nf = cf + df[i];
      int nx = cx + dx[i];
      int ny = cy + dy[i];
      // l r c
      if (nf < 0 || nf >= l || nx < 0 || nx >= r || ny < 0 || ny >= c) {
        continue;
      }

      if (m[nf][nx][ny] == '#' || visited[nf][nx][ny]) {
        continue;
      }

      visited[nf][nx][ny] = true;
      q.push({nf, nx, ny, cnt + 1});
    }
  }
  return -1;
}
// Solution 함수 (결과 출력)
void Solution() {
  int result = bfs(s);

  if (result == -1)
    cout << "Trapped!" << "\n";
  else
    cout << "Escaped in " << result << " minute(s)." << "\n";
}

// Solve 함수 (전체 과정 반복)
void Solve() {
  while (true) {
    initialize();
    input();
    Solution();
  }
}

// main 함수
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  Solve();

  return 0;
}