플레티넘으로 가는 길 - 네번째(BFS)

인사

오늘은 제가 공부하면서 자주 활용했던 알고리즘 중 하나인 BFS(Breadth-First Search) 에 대해 이야기해보려고 합니다.

BFS를 선택한 이유

사실 저는 DFS(Depth-First Search) 도 굉장히 좋아합니다. 탐색을 단순하게 구현하거나 백트래킹 문제를 풀 때는 DFS가 훨씬 직관적일 때가 많죠.

하지만 구조를 짜거나 성능적인 측면에서 살펴보면, BFS가 DFS보다 더 유리한 경우가 많습니다. 특히 최단 거리 탐색이나 레벨 단위 탐색이 필요한 문제에서는 BFS가 거의 정답에 가까운 선택지가 되곤 합니다.

물론 DFS가 반드시 필요한 상황도 존재하지만, 제가 경험해온 대부분의 문제에서 BFS가 더 좋은 해답을 제공했던 것 같습니다.

오늘의 주제: BFS 알고리즘 문제

이번 글에서는 BFS 알고리즘을 직접 문제를 통해 다뤄보겠습니다. 문제를 풀어가며 BFS의 장점과 동작 방식을 다시 한번 정리해보고, 실제로 어떤 상황에서 활용되는지 살펴보려 합니다.

다음 글에서는 문제 풀이 과정을 코드와 함께 구체적으로 설명할 예정이니, 관심 있는 분들은 함께 따라와 주시면 좋겠습니다.

BFS 문제 소개: 백준 16952번 체스판 여행 2

이번에 소개할 문제는 백준 16952번, 체스판 여행 2입니다. 난이도는 플레티넘 4로 분류되어 있으며, 단순한 BFS 문제가 아니라 경우의 수를 꼼꼼하게 고려하고, 중복을 세심하게 관리해야 하는 문제입니다.

문제 요약

문제를 정리하면 다음과 같습니다.

체스 말은 나이트, 비숍, 룩 중 하나를 선택하여 1번 위치에서 시작한다.
입력값 N에 따라 체스판에는 1 → 2 → 3 → … → N^2까지의 번호가 있으며, 반드시 1번부터 순서대로 방문해야 한다.
이동 경로 중간에 다른 번호의 칸을 거쳐갈 수는 있지만, 반드시 순서를 지켜야 한다.
말은 1초 동안 이동하거나, 다른 말로 교체할 수 있다.
목표는 N^2까지 가는 최소 시간을 구하는 것이며, 같은 최소 시간이라면 교체 횟수가 더 적은 경우를 선택해야 한다.

문제의 핵심

체스말의 이동 규칙(나이트, 비숍, 룩) 은 실제 체스판과 동일하다.
따라서 BFS 과정에서 단순히 위치만 탐색하는 것이 아니라, 말의 종류와 현재까지 방문한 번호도 함께 고려해야 한다.
BFS의 탐색 상태는 다음과 같은 요소를 포함해야 한다.
- 현재 위치 (x, y)
- 현재 말의 종류 (Knight / Bishop / Rook)
- 현재까지 방문한 번호
- 걸린 시간, 교체 횟수

즉, 단순한 BFS보다 훨씬 많은 상태를 관리해야 한다는 점에서 이 문제를 더 까다롭게 해줍니다.

예시 입력과 출력

입력 예시:

출력 예시:

12 1

예시 풀이 시나리오

나이트로 시작
(3,2) 이동 → 2 방문
(1,3) 이동 → 3 방문
다시 (3,2) 이동
말을 룩으로 교체
(3,1) 이동 → 4 방문
(3,3) 이동 → 5 방문
(3,2) 이동
(2,2) 이동 → 6 방문
(2,3) 이동 → 7 방문
(2,1) 이동 → 8 방문
(1,1) 이동
(1,2) 이동 → 9 방문

다음 글에서는 이 문제를 해결하기 위해 제가 실제로 구현한 BFS 알고리즘 코드와 설계 과정을 단계별로 정리해보겠습니다.

전체 풀이

플레티넘 4 난이도의 백준 16952: 체스판 여행 2를 BFS로 해결한 전체 풀이입니다. 이 문제는 단순한 위치 탐색이 아니라 말의 종류(나이트/비숍/룩) 와 다음에 방문해야 할 번호까지 함께 관리해야 하므로, 상태 설계와 방문 관리가 핵심입니다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

void InputArr(int N, int** arr, pair<int, int>& init) {
  for ( int i = 0; i < N; i++ ) {
    arr[i] = new int [N];
    for ( int j = 0, value; j < N; j++ ) {
      cin >> value; arr[i][j] = value;
      if ( value == 1 ) {
        init.first = i;
        init.second = j;
      }
    }
  }
}

void Setting(
queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
vector<vector<vector<vector<pair<int, int>>>>>& checks, 
const int type, const int x, const int y
) {
  pair<int, int> init(x, y);
  const int target = 2; pair<int, int> current(0, 0);
  tuple<int, pair<int, int>, int, pair<int, int>> node(type, init, target, current);
  que.push(node);
  checks[type][x][y][1] = current;
}

void SetQueue(
queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
vector<vector<vector<vector<pair<int, int>>>>>& checks, 
pair<int, int>& init,
const int knightPone = 0, const int bishopPone = 1, const int rookPone = 2
) {
  const int x = init.first; const int y = init.second;
  Setting(que, checks, knightPone, x, y);
  Setting(que, checks, bishopPone, x, y);
  Setting(que, checks, rookPone, x, y);
}

bool CheckXY(
const int N, const int x, const int y
) {
  if ( x < 0 || x >= N ) return false;
  
  if ( y < 0 || y >= N ) return false;
  
  return true;
}

bool ArriveBool(
int** arr, const int x, const int y, const int target
) {
  if ( arr[x][y] == target ) return true;
  return false;
}

void ArriveBfsfunc(
  const int N,
  queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
  vector<vector<vector<vector<pair<int, int>>>>>& checks, 
  const int newX, const int newY,
  const int type, const int prevX, const int prevY, const int target, const int value, const int count
) {
    pair<int,int>& cur = checks[type][newX][newY][target];
    const int curV = cur.first, curC = cur.second;
    const int M = N * N;
    const int newTarget = target + 1;

    if (curV == -1 || curV > value + 1 || (curV == value + 1 && curC > count)) {
        cur = {value + 1, count};


        if (newTarget <= M) {
            pair<int,int>& nxt = checks[type][newX][newY][newTarget];
            if (nxt.first == -1 || nxt.first > value + 1 || (nxt.first == value + 1 && nxt.second > count)) {
                nxt = {value + 1, count};
                que.emplace(type, pair<int,int>(newX,newY), newTarget, pair<int,int>(value + 1, count));
            }
        }
    }
}

void INGfunc(
  queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
  vector<vector<vector<vector<pair<int, int>>>>>& checks,
  const int prevX, const int prevY,
  const int newType, const int value, const int count, const int target
) {
    pair<int,int>& cell = checks[newType][prevX][prevY][target];
    int cv = cell.first, cc = cell.second;

    if (cv == -1 || cv > value + 1 || (cv == value + 1 && cc > count + 1)) {
        cell = {value + 1, count + 1}; 
        que.emplace(newType, pair<int,int>(prevX,prevY), target, pair<int,int>(value + 1, count + 1));
    }
}

void IngBfsfunc(
  int** arr,
  queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
  vector<vector<vector<vector<pair<int, int>>>>>& checks,
  const int newX, const int newY,
  const int prevX, const int prevY, const int type, const int value, const int count, const int target,
  const int newType1, const int newType2
) {
    pair<int,int>& here = checks[type][newX][newY][target];
    int hv = here.first, hc = here.second;

    if (hv == -1 || hv > value + 1 || (hv == value + 1 && hc > count)) {
        here = {value + 1, count};
        que.emplace(type, pair<int,int>(newX,newY), target, pair<int,int>(value + 1, count));
    }

    INGfunc(que, checks, prevX, prevY, newType1, value, count, target);
    INGfunc(que, checks, prevX, prevY, newType2, value, count, target);
}


void BFSInterface(
int N, int** arr,
queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
vector<vector<vector<vector<pair<int, int>>>>>& checks, 
const int x, const int y, const int target, const int value, const int count,
const int type, const int newTyp1, const int newType2, const int newX, const int newY
) {
  if ( CheckXY(N, newX, newY) ) {
    if ( ArriveBool(arr, newX, newY, target) ) ArriveBfsfunc(N, que, checks, newX, newY, type, x, y, target, value, count);
    else IngBfsfunc(arr, que, checks, newX, newY, x, y, type, value, count, target, newTyp1, newType2);
  }
}

void KngithBfsFunc(
int N, int** arr,
queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
vector<vector<vector<vector<pair<int, int>>>>>& checks, 
const int x, const int y, const int target, const int value, const int count,
const int knightPone, const int bishopPone, const int rookPone
) {
  
  const int newX1 = x - 2; const int newY1 = y + 1;
  BFSInterface(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone, newX1, newY1);
  
  const int newX2 = x - 1; const int newY2 = y + 2;
  BFSInterface(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone, newX2, newY2);
  
  const int newX3 = x + 1; const int newY3 = y + 2;
  BFSInterface(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone, newX3, newY3);
  
  const int newX4 = x + 2; const int newY4 = y + 1;
  BFSInterface(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone, newX4, newY4);
  
  const int newX5 = x + 2; const int newY5 = y - 1;
  BFSInterface(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone, newX5, newY5);
  
  const int newX6 = x + 1; const int newY6 = y - 2;
  BFSInterface(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone, newX6, newY6);
  
  const int newX7 = x - 1; const int newY7 = y - 2;
  BFSInterface(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone, newX7, newY7);
  
  const int newX8 = x - 2; const int newY8 = y - 1;
  BFSInterface(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone, newX8, newY8);
}

void BishopBfsFunc(
int N, int** arr,
queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
vector<vector<vector<vector<pair<int, int>>>>>& checks, 
const int x, const int y, const int target, const int value, const int count,
const int knightPone, const int bishopPone, const int rookPone
) {
  
  int newX1 = x - 1; int newY1 = y + 1;
  while ( (newX1 >= 0 && newX1 < N) && (newY1 >= 0 && newY1 < N) ) {
    BFSInterface(N, arr, que, checks, x, y, target, value, count, bishopPone, knightPone, rookPone, newX1, newY1);
    newX1 -= 1; newY1 += 1;
  }
  
  int newX2 = x + 1; int newY2 = y + 1;
  while ( (newX2 >= 0 && newX2 < N) && (newY2 >= 0 && newY2 < N) ) {
    BFSInterface(N, arr, que, checks, x, y, target, value, count, bishopPone, knightPone, rookPone, newX2, newY2);
    newX2 += 1; newY2 += 1;
  }
  
  int newX3 = x + 1; int newY3 = y - 1;
  while ( (newX3 >= 0 && newX3 < N) && (newY3 >= 0 && newY3 < N) ) {
    BFSInterface(N, arr, que, checks, x, y, target, value, count, bishopPone, knightPone, rookPone, newX3, newY3);
    newX3 += 1; newY3 -= 1;
  }
  
  int newX4 = x - 1; int newY4 = y - 1;
  while ( (newX4 >= 0 && newX4 < N) && (newY4 >= 0 && newY4 < N) ) {
    BFSInterface(N, arr, que, checks, x, y, target, value, count, bishopPone, knightPone, rookPone, newX4, newY4);
    newX4 -= 1; newY4 -= 1;
  }
}

void RookBfsFunc(
int N, int** arr,
queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
vector<vector<vector<vector<pair<int, int>>>>>& checks, 
const int x, const int y, const int target, const int value, const int count,
const int knightPone, const int bishopPone, const int rookPone
) {
  
  int newX1 = x - 1;
  while (newX1 >= 0 && newX1 < N) {
    BFSInterface(N, arr, que, checks, x, y, target, value, count, rookPone, bishopPone, knightPone, newX1, y);
    newX1 -= 1;
  }
  
  
  int newY1 = y + 1;
  while (newY1 >= 0 && newY1 < N) {
    BFSInterface(N, arr, que, checks, x, y, target, value, count, rookPone, bishopPone, knightPone, x, newY1);
    newY1 += 1;
  }
  
  int newX2 = x + 1;
  while (newX2 >= 0 && newX2 < N) {
    BFSInterface(N, arr, que, checks, x, y, target, value, count, rookPone, bishopPone, knightPone, newX2, y);
    newX2 += 1;
  }
  
  int newY2 = y - 1;
  while (newY2 >= 0 && newY2 < N) {
    BFSInterface(N, arr, que, checks, x, y, target, value, count, rookPone, bishopPone, knightPone, x, newY2);
    newY2 -= 1;
  }
}

void Answer(
  vector<vector<vector<pair<int,int>>>>& checks,
  const int N, const int fx, const int fy,
  pair<int,int>& answer
) {
  const int M = N * N;
  const auto& cur = checks[fx][fy][M];

  if (cur.first == -1) return;

  if (answer.first > cur.first ||
     (answer.first == cur.first && answer.second > cur.second)) {
    answer = cur;
  }
}

void DeleteArr(int N, int** arr) {
  for ( int i = 0; i < N; i++ ) delete[] arr[i];
  delete[] arr;
}

int main(void) {
  
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  // N 
  int N; cin >> N;
  
  // arr
  int** arr = new int* [N];
  pair<int, int> init;
  InputArr(N, arr, init);
  
  // que
  queue<tuple<int, pair<int, int>, int, pair<int, int>>> que; // type, (x, y), target, (value, count)
  vector<vector<vector<vector<pair<int, int>>>>> checks(
  3, vector<vector<vector<pair<int, int>>>>(
  N, vector<vector<pair<int, int>>>(
  N, vector<pair<int, int>>(N * N + 1, pair<int, int>(-1, -1)))));
  const int knightPone = 0; const int bishopPone = 1; const int rookPone = 2;
  
  SetQueue(que, checks, init, knightPone, bishopPone, rookPone); // set
  
  while ( !que.empty() ) {
    
    tuple<int, pair<int, int>, int, pair<int, int>> node = que.front(); que.pop();
    const int type = get<0>(node);
    pair<int, int> position = get<1>(node); const int x = position.first; const int y = position.second;
    const int target = get<2>(node);
    pair<int, int> current = get<3>(node); const int value = current.first; const int count = current.second;
    
    
    if (type == knightPone) KngithBfsFunc(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone );
    
    else if ( type == bishopPone ) BishopBfsFunc(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone);
    
    else RookBfsFunc(N, arr, que, checks, x, y, target, value, count, knightPone, bishopPone, rookPone);
  }
  
  // answer
  pair<int, int> answer(INT_MAX, INT_MAX);
  
  int M = N * N;
  int fx = -1, fy = -1;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (arr[i][j] == M) { fx = i; fy = j; }
    }
  }
  for ( int i = 0; i < 3; i++ ) Answer(checks[i], N, fx, fy, answer);
  
  cout << answer.first << " " << answer.second;
  
  // delete arr
  DeleteArr(N, arr);
  return 0;
}

핵심 아이디어

비용 모델: 이동 1초, 교체 1초. 모든 간선 비용이 동일하므로 BFS가 최단 시간(최소 초)을 보장합니다.
2차 최적화(타이브레이커): 최소 시간 동률이면 교체 횟수를 더 적게.
상태 정의:
$\text{state} = (\text{type}, x, y, \text{target})$

type ∈ {K(0), B(1), R(2)}
(x, y): 현재 좌표
target: 다음에 반드시 방문해야 할 번호(처음은 2)
각 상태에 대해 (time, switches)의 렉시코그래픽 최솟값을 저장

자료구조 설계

큐 원소: tuple<int, pair<int,int>, int, pair<int,int>>
- (type, (x,y), target, (time, switches))
방문/최적값 테이블:
checks[type][x][y][target] = pair<time, switches>

초기값 (-1, -1)
더 나은 (time, switches)로만 갱신 (time 우선, 같으면 switches 우선)

전이(Transition)

이동
- 현재 말 규칙에 따라 이웃 칸으로 이동 → time + 1
- 이동 도착 칸의 번호가 target이면,
  - (type, x', y', target)도 갱신
  - 동시에 (type, x', y', target+1)도 갱신하며 큐에 푸시
- 도착 칸이 target이 아니면,
  - (type, x', y', target)만 갱신하며 큐에 푸시
교체
- 같은 칸 (x, y)에서 type을 다른 두 말 중 하나로 변경 → time + 1, switches + 1
- (newType, x, y, target) 상태 갱신 및 푸시

이동과 교체 모두 1초이므로, BFS 한 레벨이 “1초 증가”를 의미합니다. 동률 타이브레이크는 (time, switches) 쌍의 렉시코그래픽 비교로 해결합니다.

구현 포인트

초기화: 1의 좌표에서 세 말 모두 시작 상태로 큐에 넣으면, “초기 말 선택”을 별도 분기 없이 자연스럽게 비교할 수 있습니다.
목표 번호 갱신: 도착 칸이 target일 때는 그 자리에 선 채로 target+1 상태도 함께 세팅해야 다음 번호를 바로 노릴 수 있습니다.
체스 이동 생성기:

나이트: 8방향 고정
비숍: 4대각선으로 끝까지
룩: 상하좌우로 끝까지
각 후보에 대해 BFSInterface로 경계 체크 → 목표 일치 여부 → 적절한 함수 호출의 공통 로직을 사용하여 중복을 줄였습니다.

복잡도 개괄

상태 수: 3 * N * N * (N^2) = O(N⁴)
간선 수: 말 이동에 따라 상태당 최대 O(N) (비숍/룩이 직선으로 끝까지)
대략 **O(N⁵)**까지 갈 수 있으나, 문제 제한(N)이 크지 않아 충분히 통과합니다.
실제 제출 측정: 36ms / 2428KB 수준

풀이 과정 1·2 — 초기 세팅과 상태 설계

이번 단계는 입력 파싱 → 시작 위치 캐싱 → 방문록(거리 테이블) 설계 → 큐 초기화까지의 준비 과정을 정리합니다.

코드 확인

void InputArr(int N, int** arr, pair<int, int>& init) {
  for ( int i = 0; i < N; i++ ) {
    arr[i] = new int [N];
    for ( int j = 0, value; j < N; j++ ) {
      cin >> value; arr[i][j] = value;
      if ( value == 1 ) {
        init.first = i;
        init.second = j;
      }
    }
  }
}

void Setting(
queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
vector<vector<vector<vector<pair<int, int>>>>>& checks, 
const int type, const int x, const int y
) {
  pair<int, int> init(x, y);
  const int target = 2; pair<int, int> current(0, 0);
  tuple<int, pair<int, int>, int, pair<int, int>> node(type, init, target, current);
  que.push(node);
  checks[type][x][y][1] = current;
}

void SetQueue(
queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
vector<vector<vector<vector<pair<int, int>>>>>& checks, 
pair<int, int>& init,
const int knightPone = 0, const int bishopPone = 1, const int rookPone = 2
) {
  const int x = init.first; const int y = init.second;
  Setting(que, checks, knightPone, x, y);
  Setting(que, checks, bishopPone, x, y);
  Setting(que, checks, rookPone, x, y);
}

1) 입력 파싱과 시작 위치 캐싱

체스판 번호 매트릭스는 탐색 동안 불변이므로, new/delete로 힙에 한 번만 올려 재사용합니다.
입력을 받으면서 번호 1의 좌표를 즉시 저장해 두면, 이후에 “시작지점 재탐색” 비용이 사라집니다

2) 방문록(거리 테이블) 구조

상태는 (말 타입, x, y, target)의 4차원으로 봅니다.
- 말 타입: 나이트=0, 비숍=1, 룩=2
- target: 다음에 반드시 방문해야 할 번호(초깃값 2)
각 상태에 대해 **(시간, 교체 횟수)**를 저장합니다.
- 초기값은 전부 (-1, -1)로 두고, 더 나은 해가 들어올 때만 갱신합니다.
최대 크기 예시(N=10 가정): 3 * 10 * 10 * (10^2 + 1) ≈ 3만 3천 원소 수준으로 충분히 여유 있습니다.

3) 큐 초기화 전략

큐 원소: (type, (x,y), target, (time, switches))
초기 세팅은 시작 좌표에서 세 말 모두를 동시에 넣습니다.
- (type, init, target=2, (time=0, switches=0)) 세 건
- 이렇게 하면 “처음 어떤 말을 고를지”도 BFS가 자연스럽게 비교해 최적을 찾아줍니다.
동시에 방문록에도 시작 상태를 기록합니다.

풀이 과정 3 — 체스 이동 생성과 분기(목표 일치 여부)

이번 단계는 세 말(나이트/비숍/룩)의 이동 후보를 생성하고, 각 후보가 보드 범위 내인지 검사한 뒤, 도착 칸이 다음 목표 번호(target)와 일치하는지에 따라 이후 처리를 두 갈래(4-1, 4-2) 로 분기하는 부분입니다.

1) 이동 후보 생성

나이트(Knight): 현재 (x, y)에서 8개의 고정 이동
- (x±2, y±1), (x±1, y±2)
비숍(Bishop): 4개 대각선으로 끝까지(연속 이동)
- (x−k, y+k), (x+k, y+k), (x+k, y−k), (x−k, y−k) (k ≥ 1)
룩(Rook): 상하좌우로 끝까지(연속 이동)
- (x−k, y), (x, y+k), (x+k, y), (x, y−k) (k ≥ 1)

각 후보는 공통 인터페이스(예: BFSInterface)로 전달해 범위 검사 → 목표 일치 분기를 수행합니다.
나이트는 8개 좌표를 바로 호출하고, 비숍/룩은 각 방향으로 k를 1씩 늘리며 보드 끝까지 호출합니다.

2) 보드 범위 검사

이동 후보 (nx, ny)가 보드 바깥이면 버리고, 안쪽이면 다음 단계로 넘어갑니다.

bool CheckXY(
const int N, const int x, const int y
) {
  if ( x < 0 || x >= N ) return false;
  
  if ( y < 0 || y >= N ) return false;
  
  return true;
}

3) 목표 번호 도착 여부 확인

다음 칸의 번호가 target과 같은지 확인합니다.

bool ArriveBool(
int** arr, const int x, const int y, const int target
) {
  if ( arr[x][y] == target ) return true;
  return false;
}

일치한다면 → 4-1 로직:
target 상태 및 그 자리에서 target+1 상태까지 갱신/푸시(다음 번호로의 승계).
일치하지 않는다면 → 4-2 로직:
현재 target을 유지한 채로 해당 칸 상태 갱신/푸시(경유).

이 분기가 최단 시간 + 교체 최소를 동시에 만족시키는 핵심입니다. 목표 칸 도착 시 그 자리에서 바로 다음 목표로 넘어갈 준비를 해두어야 이후 탐색이 낭비 없이 이어집니다.

4) 코드에서의 위치

후보 생성과 호출:
KnightBfsFunc, BishopBfsFunc, RookBfsFunc
공통 진입점(범위 검사 + 목표 분기):
BFSInterface
분기별 처리(4-1 / 4-2):

목표 일치: ArriveBfsfunc
목표 불일치: IngBfsfunc (내부에서 교체 전이 INGfunc도 함께 처리)

5) 한눈에 보는 흐름

현재 상태 (type, x, y, target, time, switches)
말 규칙에 맞춰 후보 (nx, ny) 생성
CheckXY(N, nx, ny)로 범위 확인
ArriveBool(arr, nx, ny, target)로 목표 번호 일치 여부 확인
- true → ArriveBfsfunc(...) // 4-1
- false → IngBfsfunc(...) // 4-2

풀이 과정 4-1 — 목표 칸에 도착했을 때의 갱신 규칙

이 단계는 도착 칸의 번호가 target과 일치할 때 수행하는 갱신 로직입니다. 핵심은 (시간, 교체횟수)의 렉시코그래픽 최소값을 유지하면서, 그 자리에서 target+1 상태까지 바로 승계해 주는 것입니다.

갱신 원칙

현재 상태가 (type, (x,y), target, (time=value, switches=count))이고, 이동 한 칸 (newX,newY)의 번호가 target일 때:

현재 target 상태 갱신
- checks[type][newX][newY][target]를 value+1, count로 갱신할지 결정
- 갱신 조건:
  - 저장값이 없음(time == -1) 또는
  - 기존 time > value+1 또는
  - 기존 time == value+1이면서 기존 switches > count
- 위 조건을 만족하면 갱신
target+1 상태 승계
- newTarget = target + 1
- newTarget <= N*N일 때만 처리 (경계 조건)
- 동일한 비교 규칙으로 checks[type][newX][newY][newTarget]를 (value+1, count)로 갱신하고
- 큐에 (type, (newX,newY), newTarget, (value+1, count)) 푸시

왜 newTarget <= N*N까지만?

최종 목표는 N^2 방문입니다. N^2+1은 존재하지 않는 번호이므로 그 이후 상태는 의미가 없습니다. 따라서 newTarget은 최대 N^2까지만 다룹니다.

코드와 매핑

아래 함수는 위 규칙을 그대로 구현합니다.

void ArriveBfsfunc(
  const int N,
  queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
  vector<vector<vector<vector<pair<int, int>>>>>& checks, 
  const int newX, const int newY,
  const int type, const int prevX, const int prevY, const int target, const int value, const int count
) {
    pair<int,int>& cur = checks[type][newX][newY][target];
    const int curV = cur.first, curC = cur.second;
    const int M = N * N;
    const int newTarget = target + 1;

    if (curV == -1 || curV > value + 1 || (curV == value + 1 && curC > count)) {
        cur = {value + 1, count};


        if (newTarget <= M) {
            pair<int,int>& nxt = checks[type][newX][newY][newTarget];
            if (nxt.first == -1 || nxt.first > value + 1 || (nxt.first == value + 1 && nxt.second > count)) {
                nxt = {value + 1, count};
                que.emplace(type, pair<int,int>(newX,newY), newTarget, pair<int,int>(value + 1, count));
            }
        }
    }
}

실수 방지 포인트

시간과 교체횟수의 비교 순서를 반드시 지킵니다:
time가 우선, 동률이면 switches가 작은 쪽.
target+1 승계 누락 금지: target을 방문한 즉시, 같은 좌표/같은 말 타입에서 target+1 상태를 세팅해야 이후 탐색이 끊기지 않습니다.
경계 확인: newTarget <= N*N만 큐에 넣습니다. 불필요한 상태 확장은 금물입니다.

이로써 목표 칸 도달 시의 처리(4-1)가 정리되었습니다. 다음 단계에서는 목표가 아닌 칸에 도착했을 때(4-2) 의 갱신 규칙과 같은 칸에서의 말 교체 전이를 이어서 정리하겠습니다.

풀이 과정 4-2 — 목표가 아닌 칸에 도착했을 때(경유) + 말 교체 전이

이번 단계는 도착 칸의 번호가 target과 다를 때의 처리입니다. 핵심은 두 가지 전이를 함께 다루는 것입니다.

경유 이동 전이: 같은 말로 (newX, newY)에 도착하지만 target은 그대로 유지
말 교체 전이: 같은 칸 (prevX, prevY)에서 말을 바꾸고 target 유지

코드 보기

void INGfunc(
  queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
  vector<vector<vector<vector<pair<int, int>>>>>& checks,
  const int prevX, const int prevY,
  const int newType, const int value, const int count, const int target
) {
    pair<int,int>& cell = checks[newType][prevX][prevY][target];
    int cv = cell.first, cc = cell.second;

    if (cv == -1 || cv > value + 1 || (cv == value + 1 && cc > count + 1)) {
        cell = {value + 1, count + 1}; 
        que.emplace(newType, pair<int,int>(prevX,prevY), target, pair<int,int>(value + 1, count + 1));
    }
}

void IngBfsfunc(
  int** arr,
  queue<tuple<int, pair<int, int>, int, pair<int, int>>>& que,
  vector<vector<vector<vector<pair<int, int>>>>>& checks,
  const int newX, const int newY,
  const int prevX, const int prevY, const int type, const int value, const int count, const int target,
  const int newType1, const int newType2
) {
    pair<int,int>& here = checks[type][newX][newY][target];
    int hv = here.first, hc = here.second;

    if (hv == -1 || hv > value + 1 || (hv == value + 1 && hc > count)) {
        here = {value + 1, count};
        que.emplace(type, pair<int,int>(newX,newY), target, pair<int,int>(value + 1, count));
    }

    INGfunc(que, checks, prevX, prevY, newType1, value, count, target);
    INGfunc(que, checks, prevX, prevY, newType2, value, count, target);
}

1) 경유 이동 전이 (IngBfsfunc의 “here” 갱신)

현재 상태가 (type, (prevX,prevY), target, (time=value, switches=count))이고, 말 규칙에 따라 (newX,newY)로 1초 이동했지만 도착 칸 번호가 target이 아닌 경우:

방문록 checks[type][newX][newY][target]의 (time, switches) 를 (value+1, count) 와 비교하여 더 좋은 경우 갱신 및 큐 푸시
즉, target은 그대로 유지한 채 “경유”만 한 상태를 큐에 넣는다

2) 말 교체 전이 (INGfunc 호출 두 번)

경유 전이와 동시에, 현재 칸 (prevX, prevY)에서 말을 바꾸는 선택지를 열어둡니다.

newType1, newType2는 현재 type을 제외한 나머지 두 말
교체는 같은 칸에서 일어나며 1초 + 교체횟수 1 증가

3) 정확성 포인트

경유와 교체를 같은 단계에서 함께 시도: 이동과 교체가 모두 1초이므로, 같은 BFS 레벨에서 공정하게 경쟁시켜야 최단 시간 보장이 유지됩니다.
교체는 제자리에서: 이동이 아니므로 좌표가 바뀌지 않습니다. 이를 코드로 명확히 분리(경유는 (newX,newY), 교체는 (prevX,prevY)).
렉시코그래픽 비교: (time)가 우선, 동률이면 (switches)가 더 작은 상태만 유지.

4) 실수 방지 체크리스트

경유 전이에서 target을 증가시키지 않는다.
교체 전이는 현재 칸(prevX,prevY) 에서 수행한다.
이동/교체 모두 비용 1초이므로, 비교 조건은 동일하게 (time, switches)의 렉시코그래픽 최소로 처리한다.
방문록 초기값이 (-1, -1)이므로, “없음” 판정은 time(first)만 보면 충분하다.

풀이 과정 5 — 정답 산출(최소 시간 → 최소 교체)

마지막 단계는 N²(최종 번호) 칸에서의 최적 도달값을 뽑아내는 작업입니다. 핵심은 시간을 1순위로, 교체 횟수를 2순위로 비교하는 렉시코그래픽 최소 비교입니다.

무엇을 비교하나?

상태 테이블 checks[type][x][y][target]에는 (time, switches)가 저장되어 있습니다.
최종 답은 N²를 방문 완료한 상태의 값이므로, 좌표 (fx, fy) = 번호 N²의 위치에서
checks[type][fx][fy][N*N]을 확인합니다.
세 말 타입 각각(K/B/R)에 대해 값을 비교해 가장 좋은 (time, switches) 를 선택합니다.

비교 규칙

time == -1이면 도달 불가이므로 스킵.
time이 작을수록 우선.
time이 같다면 switches가 작은 쪽을 선택.

코드 설명

void Answer(
  vector<vector<vector<pair<int,int>>>>& checks,
  const int N, const int fx, const int fy,
  pair<int,int>& answer
) {
  const int M = N * N;
  const auto& cur = checks[fx][fy][M];

  if (cur.first == -1) return;

  if (answer.first > cur.first ||
     (answer.first == cur.first && answer.second > cur.second)) {
    answer = cur;
  }
}

- checks는 단일 말 타입에 대한 3차원 슬라이스(x,y,target)입니다.

- cur.first == -1이면 해당 타입 경로는 유효하지 않으므로 제외.

- 전역 후보 answer와 비교하여 더 좋은 (time, switches)를 채택.

풀이 후기

이번 문제는 겉으로 보기에 시간 복잡도가 O(N⁴) 수준이라 매우 비효율적으로 느껴질 수 있습니다. 그러나 실제 입력 제한이 N ≤ 10이기 때문에, 2초 이내의 시간 제한을 넉넉히 충족할 수 있습니다. 실제 제출에서도 약 36ms 수준으로 통과가 가능했고, 메모리 사용량 역시 약 2428KB로, 제한인 512MB에 훨씬 못 미쳤습니다.

어려웠던 부분

방문록(거리 테이블) 정의:
단순히 좌표만 기록하는 것이 아니라,
말의 타입 · 현재 좌표 · 목표 번호(target) 까지 포함한 4차원 구조가 필요합니다.
이를 놓치면 상태가 중복되거나 잘못 병합되어 탐색이 꼬이게 됩니다.
큐에 넣는 조건:
(time, switches)를 꼼꼼히 비교하지 않으면

불필요한 상태가 큐에 계속 쌓여 오버플로우가 나거나
최소 조건을 놓쳐 정답을 구할 수 없게 됩니다.

문제의 성격

체스판 여행 2는 전형적인 BFS 문제지만,
- 상태 정의를 정교하게 해야 하고
- 큐에 들어가는 원소의 조건을 잘못 잡으면 오답으로 이어집니다.
따라서 이 문제를 풀며 BFS의 기본기를 다시 다지고,
복잡한 상태를 정확히 모델링하는 연습을 할 수 있었습니다.

👉 결론적으로, 이 문제는 **“상태 정의와 방문 관리의 중요성”**을 실감할 수 있는 BFS 문제였으며, 꼼꼼한 구현이 요구된다는 점에서 좋은 학습 경험이 되었습니다.

마무리

오늘은 오랜만에 플레티넘으로 가는 길 네 번째 포스팅을 정리했습니다. 이번 글을 통해 드디어 백준 저지에서 추천했던 문제들을 모두 해결할 수 있었고, 이제는 다음 단계로 넘어가려고 합니다.

앞으로는 solved.ac의 Class 문제들을 집중적으로 풀어볼 예정입니다. 난이도를 확인해보니 Class 4부터 진행하는 것이 적절하다고 판단했습니다. 특히 제가 목표하는 티어가 플레티넘이기 때문에, 이 단계에서는 골드 3 이상 난이도의 문제 4개를 먼저 해결할 계획입니다. (4개를 풀면 Class 4가 완성됩니다.)

그 후에는 Class 5의 문제들로 넘어가 또 다른 도전을 이어갈 예정입니다.

읽어주신 모든 분들께 감사드리며, 앞으로의 학습과 문제 풀이 과정도 꾸준히 공유드리겠습니다.
모두 각자의 자리에서 좋은 성과 이루시길 바랍니다.