백준 9204 G5 체스

문제: 체스

접근

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

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

붉은 칸을 기준으로, 푸른 칸은 붉은 칸에 인접한 칸들이다.

이를 이용해 경로를 저장하는 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의 최초 갱신은 시작 점으로부터 해당 노드까지의 완전한 최단 경로 정보의 갱신이다.

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

코드

#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;
}

← 글 목록