백준(BOJ) 1600 말이 되고픈 원숭이 ***

# BFS

기본적인 bfs 문제에서 상당히 생객해 보아야 할 점이 많아서 까다로웠던 문제였다.

넘나 머리가 아팠는데 재밌는 문제였다.

문제 푸는 과정에서 주의해야할 점은

1. visit배열을 만들 때 말처럼 이동 횟수를 기준으로 만들어 주어야한다.

(전체 이동 횟수 기준으로 하면 안된다.)

2. 나머지는 자잘한 실수들 조심하기~

(=대신 == 했다가 메모리 초과~ㅋㅋ)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 205
#define INF 987654321
#define MOD 1000000009
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

struct st
{
    int x, y;
    int cnt;
    int times;
};
int n, m, mx,map[MAX][MAX];
int dy[12] = {2,2,-2,-2,1,-1,1,-1,1,-1,0,0}, dx[12] = {1,-1,1,-1,2,2,-2,-2,0,0,1,-1};
// 말이 이동할때 8가지 방향과 동서남붕에 대한 방향 총 12가지 방향
bool visit[35][MAX][MAX];
// 말의 이동 횟수를 기준으로 visit을 사용한다.
queue<st> q;

int main()
{
    memset(map, 1, sizeof(map));
    scanf("%d%d%d", &mx,&m,&n);
    for (int i = 1; i <= n; i++)
        for (int k = 1; k <= m; k++)
            scanf("%d", &map[i][k]);
    st s = { 1,1,0,0 };
    visit[0][1][1]=true;
    q.push(s);
    while (!q.empty())
    // 기본적인 bfs 방법과 동일하게 진행한다.
    {
        st tmp = q.front();
        q.pop();
        for (int i = 0; i < 12; i++)
        {
            int ty = tmp.y + dy[i], tx = tmp.x + dx[i];
            if (1 <= ty&&ty <= n && 1 <= tx&&tx <= m && map[ty][tx]==0)
            {
                if (i < 8 && tmp.cnt < mx&&visit[tmp.cnt+1][ty][tx]==false)
                {
                    s = { tx,ty,tmp.cnt + 1,tmp.times+1 };
                    visit[tmp.cnt+1][ty][tx] = true;
                    q.push(s);
                }
                if (8 <= i&&visit[tmp.cnt][ty][tx]==false)
                {
                    s = { tx,ty,tmp.cnt,tmp.times+1 };
                    visit[tmp.cnt][ty][tx] = true;
                    q.push(s);
                }
                if (s.x == m && s.y == n)
                {
                    printf("%d", s.times);
                    return 0;
                }
            }
        }
    }
    printf("-1");
    return 0;
}