백준 7562번 나이트의 이동

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

풀이

1. BFS 문제

2. 8방향으로 탐색하며, 이미 방문했던 노드는 다시 방문하지 않는다.

   bfs 알고리즘으로 탐색하기 때문에 첫 방문했을 때에 이미 가장 적은 횟수이기 때문이다.

주의사항

처음에 dfs 로 풀었는 데, 개발 툴에서 답이 나오길래 제출했더니 시간초과가 떴었다.

가만히 생각해보니 dfs 방식을 사용하면 (x, y) 노드에 첫 방문했을 때, 가장 적은 횟수로 방문한 것이 아니기 때문이다.

그래서 내 알고리즘에도 재방문한 노드에 대해서 이동 횟수를 비교하고 작은 값을 덧씌우고 다시 dfs 탐색을 시작하기 때문이다. 

DFS 소스

#include <iostream>
#include <cstring>
#define MAX 300
using namespace std;
int from[2] = {0, };
int to[2] = {0, };
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
bool isInner(int N, int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < N);
}
void dfs(int (*map)[MAX + 1], int N, int x, int y) {
    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isInner(N, nx, ny)) {
            if (nx == from[0] && ny == from[1]) { continue; }
            if (map[nx][ny] == 0 || map[nx][ny] > map[x][y] + 1) {
                map[nx][ny] = map[x][y] + 1;
                dfs(map, N, nx, ny);
            }
        }
    }
}
int main()
{
    int T, N;
    
    scanf("%d", &T);
    for (int i = 0; i < T; ++i) {
        scanf("%d", &N);
        scanf("%d %d", &from[0], &from[1]);
        
        int map[MAX + 1][MAX + 1] = {0, };
        dfs(map, N, from[0], from[1]);
        
        scanf("%d %d", &to[0], &to[1]);
        printf("%d\n", map[to[0]][to[1]]);
    }
    
    return 0;
}


BFS 소스

#include <iostream>
#include <cstring>
#include <queue>
#include <utility>
#define MAX 300
using namespace std;
int from[2] = {0, };
int to[2] = {0, };
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
bool isInner(int N, int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < N);
}
int main()
{
    int T, N;
    
    scanf("%d", &T);
    for (int i = 0; i < T; ++i) {
        scanf("%d", &N);
        scanf("%d %d", &from[0], &from[1]);
        
        queue<pair<int, int>> q;
        int map[MAX + 1][MAX + 1] = {0, };
        bool visit[MAX + 1][MAX + 1] = {0, };
        
        q.push(make_pair(from[0], from[1]));
        visit[from[0]][from[1]] = true;
        
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            
            for (int i = 0; i < 8; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if (isInner(N, nx, ny) && !visit[nx][ny]) {
                    map[nx][ny] = map[x][y] + 1;
                    visit[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                }
            }
        }
        
        scanf("%d %d", &to[0], &to[1]);
        printf("%d\n", map[to[0]][to[1]]);
    }
    
    return 0;
}

#include <iostream>
#include <cstring>
#define MAX 300
using namespace std;
int from[2] = {0, };
int to[2] = {0, };
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
bool isInner(int N, int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < N);
}
void dfs(int (*map)[MAX + 1], int N, int x, int y) {
    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isInner(N, nx, ny)) {
            if (nx == from[0] && ny == from[1]) { continue; }
            if (map[nx][ny] == 0 || map[nx][ny] > map[x][y] + 1) {
                map[nx][ny] = map[x][y] + 1;
                dfs(map, N, nx, ny);
            }
        }
    }
}
int main()
{
    int T, N;
    
    scanf("%d", &T);
    for (int i = 0; i < T; ++i) {
        scanf("%d", &N);
        scanf("%d %d", &from[0], &from[1]);
        
        int map[MAX + 1][MAX + 1] = {0, };
        dfs(map, N, from[0], from[1]);
        
        scanf("%d %d", &to[0], &to[1]);
        printf("%d\n", map[to[0]][to[1]]);
    }
    
    return 0;
}