[백준 16509번] 장군 (C++)

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

16509번: 장군

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321; 
const int MOD = 1000000;

int r1, c1, r2, c2;
int arr[10][9]; //방문체크겸 카운팅
int dy[8] = {-2, 2, 3, -3, 2, -2, -3, 3}; //이동방향
int dx[8] = {-3,-3,-2, -2, 3, 3, 2, 2}; 

bool check(int y,int x,int i) //이동방향 체크
{
    bool flag = 1;
    switch(i)
    {
        case 0: //-2, -3
            if((r2==y&&c2==x-1)||(r2==y-1&&c2==x-2)) flag = 0; 
            break;
        case 1: //2, -3
            if((r2==y&&c2==x-1)||(r2==y+1&&c2==x-2)) flag = 0;
            break;
        case 2: //3, -2
            if((r2==y+1&&c2==x)||(r2==y+2&&c2==x-1)) flag = 0;
            break;
        case 3: //-3, -2
            if((r2==y-1&&c2==x)||(r2==y-2&&c2==x-1)) flag = 0;
            break;
        case 4: //2, 3
            if((r2==y&&c2==x+1)||(r2==y+1&&c2==x+2)) flag = 0;
            break;
        case 5: //-2, 3
            if((r2==y&&c2==x+1)||(r2==y-1&&c2==x+2)) flag = 0;
            break;
        case 6: //-3, 2
            if((r2==y-1&&c2==x)||(r2==y-1&&c2==x+1)) flag = 0;
            break;
        case 7: //3, 2
            if((r2==y+1&&c2==x)||(r2==y+2&&c2==x+1)) flag = 0;
            break;
    }
    return flag;
}

int bfs()
{
    queue<pii>q;
    q.push({r1, c1});
    while(!q.empty())
    {
        auto [y, x] = q.front(); q.pop();
        if(y==r2 && x==c2) return arr[y][x];
        for(int i=0; i<8; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >=10 || nx >=9) continue; //범위조건
            if(arr[ny][nx] || !check(y, x, i)) continue; //방문여부 및 이동방향 체크
            q.push({ny, nx});
            arr[ny][nx] = arr[y][x] + 1; //카운팅+1
        }
    }
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> r1 >> c1 >> r2 >> c2; //출발, 도착
    cout << bfs();

    return 0;
}

 

기본적인 bfs 문제에서 상의 목표에 대한 이동방향 및 진행 방향을 고려한 문제이다.

우선 상의 목방향과 진행 방향은 다음과 같다.

<목표방향 : 진행 방향>
(-2, -3) : (0, -1), (-1, -2)
(2, -3) : (0, -1), (1, -2)
(3, -2) : (1, 0), (2, -1)
(-3, -2) : (0, 1), (1, 2)
(2, 3) : (0, 1), (1, 2)
(-2, 3) : (0, 1). (-1, 2)
(-3, 2) : (-1, 0), (-1, 1)
(3, 2) : (1, 0), (2, 1)

 

목표 방향으로 이동하던 중(진행 방향)에 상을 만나게되면 무사히 도착히 불가능한 경우이므로 이에 대해 체크해준다.

체크해주는 것은 범위조건 및 범위여부를 체크할때 같이 해주면 된다.

위 8가지 진행 방향에 대해 일일히 직접 케이스를 작성하여 체크를 해주었다.

이후 무사히 통과한다면 카운팅을 하나 추가하고 다음 값에 대해 탐색을 해주고, 목표 지점에 도달하면 카운팅을 반환하면 된다.

 

이번 문제의 경우 고려해야 될 방향이 8가지나 되고, 각각 직접 확인해서 맞는 방향을 써주어야 했다.

가짓수가 많고, 직접 적으면서 확인하다보니 실수가 상당히 많았었던 것 같다.

또한 x, y의 순서를 한번씩 헷갈려서 거꾸로 쓰는 바람에 틀린 이유를 찾는 데 시간을 상당히 허비했던 것 같다.

백준 제출 정답 자체는 한 번에 맞췄지만, 테스트케이스를 한참을 틀렸던 것 같다.