16509번 장군

충남대학교 제 2회 생각하는 프로그래밍 대회 G번 문제

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

처음에 계속 '-1'이 나오길래, 어디가 잘 못 되었는지 보고있었는데

가는 '도중에' 기물(왕)이 있으면 안 되었다.

나는 도착 지점까지 체크하고 있었다. 

즉, isCan 함수 안에 for문이 2번 돌아야한다.(처음에 3으로 설정하였음.)

추가적으로 더 간단하게 코딩할 수 있다.

단순히 첫 번째 지점 검사와 두 번째 지점 검사를 dy dx처럼 배열을 활용하는 것이다.(첫 번째 코드)

<첫 번째 지점과 두 번째 지점 검사를 dy, dx처럼 배열 활용>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef struct info
{
    int y;
    int x;
    int count;
}info;
 
info Ho;
info King;
 
// 세 칸 이동(도착 지점)
int dy[8] = { -3, -2, 2, 3, 3, 2, -2, -3 };
int dx[8] = { -2, -3, -3, -2, 2, 3, 3, 2 };
 
// 한 칸 이동(가는 경로)
int vy[8] = { -1, 0, 0, 1, 1, 0, 0, -1 };
int vx[8] = { 0, -1, -1, 0, 0, 1, 0 };
 
// 두 칸 이동(가는 경로)
int ty[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int tx[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
 
int R1 = 0, C1 = 0, R2 = 0, C2 = 0;
 
int BFS()
{
    bool visit[10][9] = { false, };
 
    memset(visit, false, sizeof(visit));
 
    queue<info> q;
 
    q.push(Ho);
 
    visit[Ho.y][Ho.x] = true;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            info goHo = q.front();
 
            q.pop();
 
            if (goHo.y == King.y && goHo.x == King.x) return goHo.count;
 
            for (int i = 0; i < 8; i++)
            {
                // 한 칸 검사
                int y = goHo.y + vy[i];
                int x = goHo.x + vx[i];
                if (y < 0 || y >= 10 || x < 0 || x >= 9 || (y == King.y && x == King.x)) continue;
 
                // 두 칸 검사
                y = goHo.y + ty[i];
                x = goHo.x + tx[i];
                if (y < 0 || y >= 10 || x < 0 || x >= 9 || (y == King.y && x == King.x)) continue;
 
                // 세 칸 (도착 지점) 검사
                y = goHo.y + dy[i];
                x = goHo.x + dx[i];
                if (y < 0 || y >= 10 || x < 0 || x >= 9 || visit[y][x]) continue;
 
                q.push({ y, x, goHo.count + 1 });
                visit[y][x] = true;
            }    
        }
    }
 
    return -1;
}
 
int main(void)
{
    scanf("%d %d %d %d", &R1, &C1, &R2, &C2);
 
    Ho = { R1, C1, 0 };
    King = { R2, C2, 0 };
 
    printf("%d\n", BFS());
 
    return 0;
}

<따로 지점 검사를 할 때, 배열을 쓰지 않을 경우>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int dy[8] = { -3, -2, 2, 3, 3, 2, -2, -3 };
int dx[8] = { -2, -3, -3, -2, 2, 3, 3, 2 };
 
int R1 = 0, C1 = 0, R2 = 0, C2 = 0;
 
bool isCan(int r, int c, int index)
{
    bool ret = true;
 
    int y = 0, x = 0;
 
    if (index == 0)
    {
        y = -1;
 
        for (int i = 0; i < 2; i++)
        {
            r += y;
            c += x;
 
            if (r == R2 && c == C2)
            {
                ret = false;
                break;
            }
 
            x = -1;
        }
    }
    else if (index == 1)
    {
        x = -1;
 
        for (int i = 0; i < 2; i++)
        {
            r += y;
            c += x;
 
            if (r == R2 && c == C2)
            {
                ret = false;
                break;
            }
 
            y = -1;
        }
 
    }
    else if (index == 2)
    {
        x = -1;
 
        for (int i = 0; i < 2; i++)
        {
            r += y;
            c += x;
 
            if (r == R2 && c == C2)
            {
                ret = false;
                break;
            }
 
            y = 1;
        }
    }
    else if (index == 3)
    {
        y = 1;
 
        for (int i = 0; i < 2; i++)
        {
            r += y;
            c += x;
 
            if (r == R2 && c == C2)
            {
                ret = false;
                break;
            }
 
            x = -1;
        }
    }
    else if (index == 4)
    {
        y = 1;
 
        for (int i = 0; i < 2; i++)
        {
            r += y;
            c += x;
 
            if (r == R2 && c == C2)
            {
                ret = false;
                break;
            }
 
            x = 1;
        }
    }
    else if (index == 5)
    {
        x = 1;
 
        for (int i = 0; i < 2; i++)
        {
            r += y;
            c += x;
 
            if (r == R2 && c == C2)
            {
                ret = false;
                break;
            }
 
            y = 1;
        }
    }
    else if (index == 6)
    {
        x = 1;
 
        for (int i = 0; i < 2; i++)
        {
            r += y;
            c += x;
 
            if (r == R2 && c == C2)
            {
                ret = false;
                break;
            }
 
            y = -1;
        }
    }
    else if (index == 7)
    {
        y = -1;
 
        for (int i = 0; i < 2; i++)
        {
            r += y;
            c += x;
 
            if (r == R2 && c == C2)
            {
                ret = false;
                break;
            }
 
            x = 1;
        }
    }
 
    return ret;
}
 
int BFS()
{
    bool visit[10][9] = { false, };
    
    memset(visit, false, sizeof(visit));
 
    queue<pair<int, int> > q;
 
    q.push({ R1, C1 });
 
    visit[R1][C1] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            if (r == R2 && c == C2) return ret;
 
            for (int i = 0; i < 8; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= 10 || x < 0 || x >= 9 || visit[y][x]) continue;        
 
                if (!isCan(r, c, i)) continue;
 
                q.push({ y, x });
                visit[y][x] = true;
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
int main(void)
{
    scanf("%d %d", &R1, &C1);
    scanf("%d %d", &R2, &C2);
 
    printf("%d\n", BFS());
 
    return 0;
}