백준 9204 G5 체스

Date/Lastmod: 04-15/25
Section: PS

Title: 백준 9204 G5 체스
Ps-Tags: 그래프
Solved: 04-16/25

#¹ 접근

격자 형태의 그래프 탐색 문제에서 보통 인접하다의 정의는 상, 하, 좌, 우인 경우가 많으나, 이 문제는 인접하다 의 정의가 조금 다른 것이 특징이다.

체스 기물 비숍의 경우 상하좌우 대각선으로 한 칸만 이동할 수 있는게 아니라, 몇 칸이든 이동할 수 있으므로, 해당 칸들이 모두 현재 위치와 인접하다고 평가할 수 있다.

이를 이용해 경로를 저장하는 BFS 를 사용하면, 비숍이 시작 지점부터 끝 점까지 특정 이동 횟수 내로, 최소한만 이동하여 도달할 수 있는지의 여부를 판단할 수 있다.

BFS 관련 일반적인 내용에 대한 정리는 아래의 게시물을 참고한다.

너비 우선 탐색(BFS)

#¹ 알고리즘

빠른 종료
시작점과 끝점이 이미 같은 경우, 출력하고 종료한다.
시작점과 끝점의 색이 다른 경우, 아무리 노력해도 도달할 수 없으므로 출력하고 종료한다.
BFS 탐색 시도
BFS 초기화 단계
위 두가지 케이스가 아닌 경우 BFS 탐색이 필요한 경우이다:
BFS 큐에 더해, 시작점부터 거리를 저장한 dists 배열과 경로 부모 노드를 저장할 parent 배열을 초기화한다.
큐에 시작 정점을 넣고, dists와 parent를 시작 정점에 대해 초기화한다.
도착점을 찾았는지 관리하는 found 부울 변수를 선언하고, false로 초기화한다.
BFS 실행 단계
현재 정점 처리 단계
큐에서 정점을 하나 꺼낸다.
만일 현재 처리중인 정점까지 거리가 4 초과면, 네번 초과 이동한 것이므로 문제 조건에 어긋난다. 따라서 넘어간다.
꺼낸 정점이 도착점이면 도착점까지의 최단 경로를 확인한 것이므로 found를 true로 만들고, BFS를 종료한다.
인접 정점 탐색 단계
현재 정점에 대해 비숍의 모든 인접 정점을 구하고 각 인접 정점에 대해서:
인접 정접의 거리(dists)가 이미 계산되어 있으면 넘어간다.
계산되어 있지 않으면, dists를 계산하고 부모 경로 노드도 업데이트하고, 현재 인접 정점을 큐에 넣는다.
출력
found가 참이면:
parent를 거꾸로 출력한다
거짓이면:
경로를 찾을 수 없다고 출력한다.

경로를 구해야 하는 경우 경로 부모 노드 배열을 관리해야 한다.

#¹ 헷갈렸던 부분

BFS는 Single Source to All Destination 알고리즘으로, 그래프 내 기준점에서 다른 모든 노드까지의 최단 경로를 계산한다.

다시 표현하면 BFS를 어느 한 시작점에 대해 돌리는 경우 목표로 하는 점 외의 다른 모든 점 까지 최단 경로 정보도 갱신된다는 뜻이다.

때문에 parent나 dists의 최초 갱신은 시작 점으로부터 해당 노드까지의 완전한 최단 경로 정보의 갱신이다.

때문에 유망하지 않은 분기라 하더라도 해당 정보를 지울 필요가 없으며 백 트래킹처럼 상태를 추가/복원할 필요 자체가 없다.

#¹ 코드

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

#define IMPOSSIBLE "Impossible"s
#define B_SIZE 8
#define NO_PARENT pair<int, int>(-1, -1)

int main() {
  int T; cin >> T;
  for (int tc = 0; tc < T; ++tc) {
    char Xv, Yv;
    int Xh, Yh;
    cin >> Xv >> Xh >> Yv >> Yh;

    const pair<int, int> start{Xv - 'A', Xh - 1};
    const pair<int, int> end{Yv - 'A', Yh - 1};

    // 1. 시작점과 끝점이 같은 경우
    if (start == end) {
      cout << 0 << ' ' << static_cast<char>(start.first + 'A') << ' ' << start.second + 1 << '\n';
      continue;
    }

    // 2. 시작점과 끝점의 색깔이 다른 경우
    if ((start.first + start.second) % 2 != (end.first + end.second) % 2) {
        cout << IMPOSSIBLE << "\n";
        continue;
    }

    // 3. 탐색이 필요한 경우

    queue<pair<int, int>> to_visit;
    to_visit.push(start);
    vector<vector<pair<int, int>>> parent(B_SIZE, vector<pair<int, int>>(B_SIZE, NO_PARENT));
    vector<vector<int>> dists(B_SIZE, vector<int>(B_SIZE, INT_MAX));

    parent[start.first][start.second] = NO_PARENT;
    dists[start.first][start.second] = 0;

    auto get_adj_poss = [](const pair<int, int>& pos) {
      vector<pair<int, int>> ret;
      auto is_valid = [](int v, int h) {
        return v >= 0 && v < B_SIZE && h >= 0 && h < B_SIZE;
      };
      // 오른쪽 아래 대각선
      for (int off = 1; is_valid(pos.first + off, pos.second + off); ++off) {
        ret.push_back({pos.first + off, pos.second + off});
      }
      // 왼쪽 아래 대각선
      for (int off = 1; is_valid(pos.first - off, pos.second + off); ++off) {
        ret.push_back({pos.first - off, pos.second + off});
      }
      // 오른쪽 위 대각선
      for (int off = 1; is_valid(pos.first + off, pos.second - off); ++off) {
        ret.push_back({pos.first + off, pos.second - off});
      }
      // 왼쪽 위 대각선
      for (int off = 1; is_valid(pos.first - off, pos.second - off); ++off) {
        ret.push_back({pos.first - off, pos.second - off});
      }
      return ret;
    };

    // 4. BFS 시작
    bool found = false;
    while (!to_visit.empty()) {
      pair<int, int> cv = to_visit.front();
      to_visit.pop();

      if (cv == end) {
        found = true;
        break;
      }

      if (dists[cv.first][cv.second] >= 4) {
        continue;
      }

      // 인접 위치 탐색
      for (const pair<int, int>& av: get_adj_poss(cv)) {
        if (dists[av.first][av.second] != INT_MAX) {
          continue;
        }

        dists[av.first][av.second] = dists[cv.first][cv.second] + 1;
        parent[av.first][av.second] = cv;

        to_visit.push(av);
      }
    }

    // 5. 결과 출력
    if (found) {
      // 경로 뒤집기
      vector<pair<int, int>> path;
      pair<int, int> curr = end;
      while (curr != NO_PARENT) {
          path.push_back(curr);
          curr = parent[curr.first][curr.second];
      }
      reverse(path.begin(), path.end());

      cout << path.size() - 1 << ' ';
      for (int i = 0; i < path.size(); ++i) {
        const auto& [v, h] = path[i];
        cout << static_cast<char>(v + 'A') << ' ';
        cout << h + 1;
        if (i < path.size() - 1) { 
          cout << ' ';
        }
      }
      cout << '\n';
    } else {
      cout << IMPOSSIBLE << "\n";
    }
  }
  return 0;
}

백준 9204 G5 체스

#1 접근

#1 알고리즘

#1 헷갈렸던 부분

#1 코드

#¹ 접근

#¹ 알고리즘

#¹ 헷갈렸던 부분

#¹ 코드