[ BOJ / C++ ] 16509번 : 장군

[ BOJ ] 16509번 : 장군

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

---

[  문제  ]

오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다.

하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다.

호근이를 위해 상을 어떻게 써야 할지 도와주자.

 

위 그림은 10×9 크기의 장기판을 나타내며, 상은 (5, 4)에, 왕은 (1, 4)에 자리 잡고 있는 기물이다.

(0, 3)과 (2, 5)를 꼭짓점으로 하는 사각형과, (7, 3)과 (9, 5)를 꼭짓점으로 하는 사각형은 왕이 위치할 수 있는 궁성이라고 한다.

상은 위 그림과 같이 8가지 방법으로 움직일 수 있는데, 상, 하, 좌, 우로 한 칸을 이동한 후에 같은 방향 쪽 대각선으로 두 칸 이동한다.

 

 

만약 상이 이동하는 경로에 위 그림과 같이 다른 기물이 있다면 상은 그쪽으로 이동할 수 없다.

또한, 상이 장기판을 벗어날 수도 없다.

 

10×9 크기의 장기판 위에 상과 왕의 처음 위치가 주어졌을 때, 상이 왕에게 도달할 수 있는 최소 이동 횟수를 구하여라.

[  입력  ]

첫 번째 줄에는 상의 위치를 의미하는 정수 R1, C1이 주어진다.

두 번째 줄에는 왕의 위치를 의미하는 정수 R2, C2가 주어진다. 장기판에서 Ri (0 ≤ Ri ≤ 9)는 행을, Ci (0 ≤ Ci ≤ 8)는 열을 의미한다.

왕은 항상 궁성에 자리 잡고 있으며, 상과 왕의 위치는 겹치지 않는다.

[  출력  ]

상이 왕에게 도달할 수 있는 최소 이동 횟수를 출력한다. 만약 도달할 수 없다면 -1을 출력한다.

---

[  문제 접근 및 풀이  ]

이 판에 있는 기물은 왕과 상뿐이니 상이 도착하지 않고 움직이는 부분에서

왕과 만나면 continue만 해주었고 이를 위해서 BFS에서 움직이는 부분을 모두 각각 구했다.

 

장기판의 크기가 10*9이기에 시간복잡도는 생각하지 않고 편하게 한 점도 있다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
typedef struct Locate{
    int x,y,cnt;
}L;
int R1,C1,R2,C2;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int ddx[8]={-1,1,1,1,1,-1,-1,-1},ddy[8]={1,1,1,-1,-1,-1,-1,1};
int board[10][9],vis[10][9];
void Q_16509();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_16509();
}
void Q_16509(){
    cin >> R1 >> C1;
    cin >> R2 >> C2;
    board[R2][C2]=1;
    queue<L> q;
    q.push({R1,C1,0});
    while(!q.empty()){
        auto cur=q.front(); q.pop();
        for(int dir4=0;dir4<4;dir4++){
            int nx=cur.x+dx[dir4],ny=cur.y+dy[dir4];
            if(nx<0 || ny<0 || nx>=10 || ny>=9 || board[nx][ny]) continue;
            for(int dir8=dir4*2;dir8< dir4*2+2;dir8++){
                int nnx=nx+ddx[dir8],nny=ny+ddy[dir8];
                if(nnx<0 || nny<0 || nnx>=10 || nny>=9 || board[nnx][nny]) continue;
                nnx+=ddx[dir8],nny+=ddy[dir8];
                if(nnx<0 || nny<0 || nnx>=10 || nny>=9)continue;
                if(board[nnx][nny]) {
                    cout << cur.cnt+1;
                    return;
                }
                if(vis[nnx][nny]) continue;
                vis[nnx][nny]=cur.cnt+1;
                q.push({nnx,nny,cur.cnt+1});
            }
        }
    }
    cout << -1;
}

---

 

ps. 소스 코드 43번 줄에 있는 cout  <<  -1; 을 빼도 통과한다