[백준/C++] 16509번 장군

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

16509번: 장군

간단한 bfs 구현문제이다.

1. 상하좌우 중 한 방향으로 전진한다.

2. 전진한 방향 각각에 대해 대각선 탐색을 해준다.

3. 위쪽 방향은 {좌상, 우상}으로만 이동가능하고, 아래방향은 {좌하, 우하}로만 이동 가능하다. 왼쪽은 {좌상, 좌하}고

오른쪽은 {우상, 우하}다. 그게 바로 배열 dddx[]와 dddy[]이다!

해당 위치를 방문하였거나, 장기판 밖이 아닌 경우에만 큐에 좌표를 넣어주고 방문 처리해준다. 그리고 이동 횟수 역시 큐에 같이 저장해준다.

​

여기까지하면 문제가 끝인 줄 알았으나.. 예제 3번이 통과되지 않았다..!

이유를 살펴보니, 상의 이동 경로에 왕이 있다면 상은 해당 경로로 진행할 수 없는데 그 사실을 간과하고 푼 것이다..!

​

상은 상하좌우 한칸 이동하고 대각선을 같은 방향으로 2번 이동하므로 이를 이용해 해답을 살펴보자

1. 우선 상하좌우 한칸에 에 왕이 있으면 탐색을 중지한다.

2. 대각선 1칸 거리에 왕이 있으면 탐색을 중지한다. 대각선 1칸을 나타내는 배열이 바로 ddx[]와 ddy[]이다!

어차피 대각선 2칸을 같은 방향으로 이동하므로, 대각선 2칸에 대해 탐색하기 전에 체크해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <functional>
#include <complex>
#include <cmath>
#include <unordered_map>
#include <map>
typedef long long ll;
using namespace std;

int board[10][9];
int r1,c1, r2,c2,j,tmp;
queue<pair<pair<int,int>,int>> q;
bool visited[10][9];

// 상 하 좌 우
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

//대각 한칸
int ddx[] = {-1, -1, 1, 1};
int ddy[] = {-1, 1, -1, 1};

//좌상 우상 좌하 우하 -> 대각 2칸
int dddx[] = {-2, -2, 2, 2};
int dddy[] = {-2, 2, -2, 2};

bool Inboundary(int r, int c){
    if(r < 0 || c < 0 || r >9 || c > 8) return false;
    return true;
}

void bfs(){
    q.push({{r1,c1},0});
    visited[r1][c1] = true;

    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
        if(x==r2 && y == c2) {
            cout << cnt;
            return;
        }
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(board[nx][ny] == -2) continue; // 상하좌우에 왕 있으면 패스

            if(i == 0 || i==1){ // 위 or 아래
                if(i==0) {
                    j=0; tmp=0;
                }
                else {
                    j=2; tmp=2;
                }
                for(; j<2+tmp;j++){
                    int nnx = nx + ddx[j];
                    int nny = ny + ddy[j];
                    if(board[nnx][nny]==-2) continue; // 대각선 한칸에 왕있으면 패스

                    int nnnx = nx + dddx[j];
                    int nnny = ny + dddy[j];
                    if(Inboundary(nnnx, nnny) && !visited[nnnx][nnny]){
                        q.push({{nnnx, nnny}, cnt + 1});
                        visited[nnnx][nnny]= true;
                    }
                }
            }
            else{// 왼쪽 or 오른쪽
                if(i==2) j=0;
                else j=1;
                for(; j<4;j+=2){
                    int nnx = nx + ddx[j];
                    int nny = ny + ddy[j];
                    if(board[nnx][nny]==-2) continue;

                    int nnnx = nx + dddx[j];
                    int nnny = ny + dddy[j];
                    if(Inboundary(nnnx, nnny) && !visited[nnnx][nnny]){
                        q.push({{nnnx, nnny}, cnt + 1});
                        visited[nnnx][nnny]= true;
                    }
                }
            }
        }
    }
    cout << -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> r1 >> c1 >> r2 >> c2;

    board[r2][c2] = -2; // 왕 위치

    bfs();
}