[BOJ 8598 // C++] Zając

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 8598번 문제인 Zając이다.
문제는 아래 링크를 확인하자.

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

8598번: Zając

체스의 나이트와 같은 움직임을 하는 토끼가 굴에 들어가기 위해 필요한 점프의 최소 횟수를 구하는 문제이다. 이와 같은 유형의 문제는 BFS를 이용해 칸의 수에 비례한 시간복잡도로 해결할 수 있다.

 

아래의 dr과 dc와 같은 배열을 이용하면 토끼의 움직임을 보다 편하게 구현할 수 있다.

 

아래는 제출한 소스코드이다.

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

int R, C, sR, sC, eR, eC;
string board[1000];
int dist[1000][1000];
int dr[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dc[8] = {2, 1, -1, -2, -2, -1, 1, 2};

queue<pair<int, int>> que;
void bfs() {
    dist[sR][sC] = 1;
    que.push(make_pair(sR,sC));
    while (!que.empty()) {
        int r = que.front().first, c = que.front().second; que.pop();
        for (int i = 0; i < 8; i++) {
            int rr = r + dr[i], cc = c + dc[i];
            if (rr<0 || rr>=R || cc<0 || cc>=C || dist[rr][cc] || board[rr][cc] == 'x') continue;
            dist[rr][cc] = dist[r][c] + 1;
            que.push(make_pair(rr, cc));
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> R >> C;
    for (int r = 0; r < R; r++) cin >> board[r];
    
    for (int r = 0; r < R; r++){
        for (int c = 0; c < C; c++){
            if (board[r][c] == 'z') sR = r, sC = c;
            else if (board[r][c] == 'n') eR = r, eC = c;
        }
    }
    
    bfs();
    
    if (dist[eR][eC]) cout << dist[eR][eC] - 1;
    else cout << "NIE";
}