[백준] 16509번 장군 c++

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

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을 출력한다.

 

문제접근 및 풀이

- BFS알고리즘으로 해결하였다.

 

BFS 탐색 과정 중 유의점

- 상이 움직일 수 있는 8가지를 탐색한다.

- 이때 움직이는 경로 중에 기물(왕)이 있으면 해당 경로로 이동하지 못한다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define VMAX 1000
#define INF 987654321

using namespace std;

pair<int,int> from;
pair<int,int> to;

int dx[8] = {3,3,2,-2,-3,-3,-2,2};
int dy[8] = {2,-2,-3,-3,-2,2,3,3};

bool check(int x,int y,int i){
  int tx = to.first;
  int ty = to.second;
  if(i==0)
    if((tx==x+1&&ty==y)||(tx==x+2&&ty==y+1)) return false;
  if(i==1)
    if((tx==x+1&&ty==y)||(tx==x+2&&ty==y-1)) return false;
  if(i==2)
    if((tx==x&&ty==y-1)||(tx==x+1&&ty==y-2)) return false;
  if(i==3)
    if((tx==x&&ty==y-1)||(tx==x-1&&ty==y-2)) return false;
  if(i==4)
    if((tx==x-1&&ty==y)||(tx==x-2&&ty==y-1)) return false;
  if(i==5)
    if((tx==x-1&&ty==y)||(tx==x-2&&ty==y+1)) return false;
  if(i==6)
    if((tx==x&&ty==y+1)||(tx==x-1&&ty==y+2)) return false;
  if(i==7){
    if((tx==x&&ty==y+1)||(tx==x+1&&ty==y+2)) return false;
    }
  return true;
}
int bfs(){
  int v[10][9]={0};
  queue<pair<pair<int,int>,int>> q;
  q.push({{from.first, from.second}, 0});
  v[from.first][from.second] = 1;
  while(!q.empty()){
    int x = q.front().first.first;
    int y = q.front().first.second;
    int c = q.front().second;
    q.pop();
    if(x==to.first && y==to.second){
      return c;
    }
    for(int i=0; i<8; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx>=0 && ny>=0 && nx < 10 && ny < 9 && v[nx][ny]==0){
        if(check(x,y,i)==true){
          //printf("x:%d, y:%d, c:%d, i:%d\n",x,y,c,i);
          v[nx][ny]=1;
          q.push({{nx,ny}, c+1});
        }
      }
    }

  }

  return -1;
}

int main(){
  cin >> from.first >> from.second;
  cin >> to.first >> to.second;

  cout << bfs();

  return 0;
}

 

느낀점

- 시뮬레이션 요소가 들어가 있어서 새롭게 다가온 BFS문제였다. 간단히 해결할 수 있을 거라고 생각해서 바로 코딩에 옮겼지만 8가지 경로에 대해 왕이 중간에 있는지 체크하는 것을 구현하느라 시간이 좀 걸렸다. 이 과정을 좀 정리한 후에 코딩했으면 더 순조롭게 풀렸을 것 같다.