백준 1600 / CPP / BFS

https://www.acmicpc.net/problem/1600

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

int arr[200][200];
bool visited[200][200][31] = { false }; // visited[row][col][사용한 말 이동 횟수]
int dx[4] = { 0, 0, -1, 1 };            // 상하좌우 이동
int dy[4] = { 1, -1, 0, 0 };
int hx[8] = { -2, -2, 2, 2, -1, -1, 1, 1 }; // 말(나이트) 이동
int hy[8] = { 1, -1, 1, -1, 2, -2, 2, -2 };

int main() {
    int k, w, h;
    cin >> k >> w >> h;
    // h행, w열의 배열 입력 (문제에서 h가 행의 개수, w가 열의 개수임)
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> arr[i][j];
        }
    }

    // (현재 행, 현재 열)와 (이동 횟수, 사용한 말 이동 횟수)
    queue< pair< pair<int, int>, pair<int, int> > > bfsQ;
    bfsQ.push({ {0, 0}, {0, 0} });
    visited[0][0][0] = true;

    int minMoves = -1;
    while (!bfsQ.empty()) {
        pair< pair<int, int>, pair<int, int> > cur = bfsQ.front();
        bfsQ.pop();
        int x = cur.first.first;
        int y = cur.first.second;
        int moveCount = cur.second.first;
        int horseUsed = cur.second.second;

        // 목적지: (h-1, w-1)
        if (x == h - 1 && y == w - 1) {
            minMoves = moveCount;
            break;
        }

        // 4방향 이동 (상, 하, 좌, 우)
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                continue;
            if (arr[nx][ny] == 1)
                continue;
            if (!visited[nx][ny][horseUsed]) {
                visited[nx][ny][horseUsed] = true;
                bfsQ.push({ {nx, ny}, {moveCount + 1, horseUsed} });
            }
        }

        // 말 이동 (나이트 이동) 처리 (남은 말 이동 횟수가 있을 경우)
        if (horseUsed < k) {
            for (int i = 0; i < 8; i++) {
                int nx = x + hx[i];
                int ny = y + hy[i];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                    continue;
                if (arr[nx][ny] == 1)
                    continue;
                if (!visited[nx][ny][horseUsed + 1]) {
                    visited[nx][ny][horseUsed + 1] = true;
                    bfsQ.push({ {nx, ny}, {moveCount + 1, horseUsed + 1} });
                }
            }
        }
    }

    cout << minMoves;
    return 0;
}

 

이 문제는 조금 어려운 BFS 였다 어렵다기 보다는 isVisited를 선언할 때 3차원 배열로 할수 있음이 있었다
즉 말움직임을 k번사용해서 방문했을 때의 대한 값을 저장해놓았다 그리고 해당 문제는 bfs 이기에 먼저 도착했을 경우 해당 값은 이미 방문처리가 되었기 때문에 방문 최소 횟수 를 저장해놓을 필요는 없는 문제였다