[코딩테스트 C++] 나이트의 이동

오늘의 문제

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

나이트의 이동

접근방식

• 이동만 잘 정의해두면 된다.
• 이 문제는 BFS로 풀어야 시간을 줄일 수 있다. 원하는 목적지가 있기 때문
• 이동시마다 depth를 1씩 늘려준다.목적지에 도착하면 바로 끝을 낸다.

나의 풀이

#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;
int t, n;
queue<pair<pair<int, int>, int>> q;
const int MAX = 300;
int dest[2];
int dx[]= {1, 1, -1, -1, 2, 2, -2, -2};
int dy[]= {2, -2, 2, -2, 1, -1, 1, -1};
bool visit[MAX][MAX] ={false, };

int solution(){
    int answer =0;
    while(!q.empty()){
        int y = q.front().first.first;
        int x = q.front().first.second;
        int depth = q.front().second;
        if(y == dest[0] && x == dest[1])
            return depth;
        q.pop();
        for(int i=0;i<8;i++){
            int my = y+dy[i];
            int mx = x+dx[i];
            if(my >= n || my <0 || mx >= n || mx <0)
                continue;
            if(visit[my][mx] == false){
                visit[my][mx] = true;
                q.push(make_pair(make_pair(my, mx), depth+1));
            }
        }
    }
    return answer;
}

다른 풀이

// 7562번 나이트의 이동
#include <cstdio>
#include <queue>
using namespace std;
typedef struct pos {
    int x, y;
} Pos;
const int lth = 300;
int tc, n, mp[lth][lth], ans;
int dx[] = {-2, -1, -2, -1, 1, 2, 1, 2}, dy[] = {1, 2, -1, -2, -2, -1, 2, 1};
Pos init, gl;
int bfs(Pos init) {
    queue<Pos> q;
    q.push(init);
    mp[init.x][init.y] = 1;
    while (!q.empty()) {
        Pos cur = q.front(); q.pop();
        for (int i = 0; i < 8; i++) {
            Pos nxt;
            nxt.x = cur.x + dx[i];
            nxt.y = cur.y + dy[i];
            if (nxt.x >= 0 && nxt.y >= 0 && nxt.x < n && nxt.y < n) {
                if (nxt.x == gl.x && nxt.y == gl.y) 
                    return mp[cur.x][cur.y];
                else if (mp[nxt.x][nxt.y] == 0) {
                    q.push(nxt);
                    mp[nxt.x][nxt.y] = mp[cur.x][cur.y] + 1;
                }
            }
        }
    }
    return 0;
}
int main() {
    scanf("%d\n", &tc);
    while (tc--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            mp[i][j] = 0;
        scanf("%d %d", &init.x, &init.y);
        scanf("%d %d", &gl.x, &gl.y);
        if(init.x == gl.x && init.y == gl.y) ans = 0;
        else ans = bfs(init);
        printf("%d\n", ans);
    }
    return 0;
}

배울 점

• 이제는 하루 중 문제를 푸는것에서 즐거움을 얻는것 같은 요상한 느낌. 다른거 하기가 힘들면 문제를 풀게된다.
• 방법이 같다!