백준 7562번 - 나이트의 이동 (C++)

유형: 그래프, BFS

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

7562번: 나이트의 이동

 

풀이 1

처음 생각해낸 풀이. 큐에 좌표뿐만 아니라 카운트 수도 저장했다.

초기 코드는 메모리 초과로 실패했는데, 방문처리를 큐에서 pop할 때가 아니라 파생위치를 큐에 넣을 때 해줘야한다.

왜냐하면, 큐에서 pop할 때 방문처리를 하면 큐에 있는 원소들은 전부 방문하지 않았다는 전제가 깔린다.

따라서 큐에 좌표가 중복으로 들어갈 수도 있어서, 불필요한 탐색이 많아진다. (그래서 메모리 초과가 발생함)

#include "iostream"
#include "vector"
#include "queue"

using namespace std;

int solution(int len, vector<int> start, vector<int> end){
    int answer = 0;

    // 나이트가 이동 가능한 방향
    int xPos[] = {-2, -2, -1, -1, 1, 1, 2, 2};
    int yPos[] = {1, -1, 2, -2, 2, -2, 1, -1};

    // 맵 구성
    vector<vector<bool>> maps(len);
    for(auto &now: maps) {
        for(int i = 0; i < len; i++) now.push_back(false);
    }

    // 큐 구성
    queue<vector<int>> q;
    q.push({start[0], start[1], 0}); // 시작점 추가
    maps[start[0]][start[1]] = true;

    while(!q.empty()){
        // 큐의 맨 앞의 원소를 pop
        auto now = q.front(); q.pop();
        auto x = now[0], y = now[1], cnt = now[2];

        // 정답에 도달했다면 탈출
        if(x == end[0] && y == end[1]) {
            answer = cnt;
            break;
        }

        // 파생 위치를 큐에 넣기
        for(int i = 0; i < 8; i++){
            auto tempX = x + xPos[i];
            auto tempY = y + yPos[i];

            // 범위 초과된건 넘어감
            if (tempX < 0 || tempX >= len || tempY < 0 || tempY >= len) continue;
            else if(!maps[tempX][tempY]){
                // 파생중에 방문하지 않은건 큐에 넣음
                q.push({tempX, tempY, cnt+1});
                maps[tempX][tempY] = true;
            }
        }
    }

    return answer;
}


int main(){
    ios::sync_with_stdio(0);

    int n; cin >> n;

    while (n--){
        int len; cin >> len;
        vector<int> st(2); cin >> st[0] >> st[1];
        vector<int> ed(2); cin >> ed[0] >> ed[1];

        cout << solution(len, st, ed) << endl;
    }

    return 0;
}

 

풀이 2

여기서는 큐에 카운트 횟수를 넣지 않고, maps에 카운트 횟수를 저장한다.

이렇게 하면 maps 좌표에 해당하는 값이 0일 때에만 방문하지 않은 노드로 인식된다.

풀이 1번의 방문처리를 왜 파생을 계산하는 시점에서 해야하는지 조금 더 이해하기 쉽다.

#include "iostream"
#include "vector"
#include "queue"

using namespace std;

int solution(int len, vector<int> start, vector<int> end){
    // 나이트가 이동 가능한 방향
    int xPos[] = {-2, -2, -1, -1, 1, 1, 2, 2};
    int yPos[] = {1, -1, 2, -2, 2, -2, 1, -1};

    // 맵 구성
    vector<vector<int>> maps(len);
    for(auto &now: maps) {
        for(int i = 0; i < len; i++) now.push_back(0);
    }

    // 큐 구성
    queue<vector<int>> q;
    q.push({start[0], start[1]}); // 시작점 추가

    while(!q.empty()){
        // 큐의 맨 앞의 원소를 pop
        auto now = q.front(); q.pop();
        auto x = now[0], y = now[1];

        // 정답에 도달했다면 탈출
        if(x == end[0] && y == end[1]) break;

        // 파생 위치를 큐에 넣기
        for(int i = 0; i < 8; i++){
            auto tempX = x + xPos[i];
            auto tempY = y + yPos[i];

            // 범위 초과된건 넘어감
            if (tempX < 0 || tempX >= len || tempY < 0 || tempY >= len) continue;
            
            // 파생중에 방문하지 않은건 큐에 넣음 (값이 0일때만 유효함)
            else if(!maps[tempX][tempY]){
                q.push({tempX, tempY});
                maps[tempX][tempY] = maps[x][y] + 1;
                // 파생중에 정답이 있다면 탈출
                if(tempX == end[0] && tempY == end[1]) break;
            }
            
        } // 파생 넣기 끝
    }

    return maps[end[0]][end[1]];
}


int main(){
    ios::sync_with_stdio(0);

    int n; cin >> n;

    while (n--){
        int len; cin >> len;
        vector<int> st(2); cin >> st[0] >> st[1];
        vector<int> ed(2); cin >> ed[0] >> ed[1];

        cout << solution(len, st, ed) << endl;
    }

    return 0;
}