7562

백준 7562번

Link: 7562번: 나이트의 이동

---

문제 설명

이번에도 BFS문제다.

기본적인 BFS문제와 다른 점은 나이트의 이동 반경을 전부 표시하려면 8가지의 경우의 수가 나온다는 점인데 이 8가지를 전부 고려해보고 이동시켜야 한다.

8가지 경우를 각 경우에 대해 다 찾아봐야 해서 시간초과 날줄 알았는데 정직하게 BFS 돌려도 시간내에 풀리는 문제였다.

답을 구하려면 BFS를 진행하며 거친 트리의 레벨을 구하면 되는데, 이 과정에서 어떻게 구현할지 고민을 많이 했던 것 같다.

보통 아는 BFS대로 하면 말도안되는 큰수가 나오더라.

어떻게할지 고민해보다 예전에 풀었던 BFS 문제 중 큐에 있는 모든 원소를 pop해서 저장한 다음, 그 모든 원소에 대해 각각 BFS를 진행하는 문제를 풀어본 기억이 났다.

그대로 적용해서 풀어보니 바로 풀렸다.

그 문제 풀때는 풀이방법을 모르겠어서 답을 봤던것 같은데, 이번에는 내가 직접 방법을 떠올려 구현하고 풀었다는 점은 발전 요소.

앞으로도 트리 레벨 구하는 유형은 이런식으로 풀면 될것 같다.

---

정답 코드

//
// Created by Keith_Lee on 22/01/2019.
//

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;

int I;
int result = 0;

int map[300][300];
bool visit[300][300];

int dx[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

void BFS(int startX, int startY, int endX, int endY){
    queue<pair<int, int>> Queue;
    Queue.push(make_pair(startX, startY));
    visit[startX][startY] = true;

    while(!Queue.empty()){
        vector<pair<int, int>> currents;

        while(!Queue.empty()){
            int currentX = Queue.front().first;
            int currentY = Queue.front().second;
            Queue.pop();
            currents.push_back(make_pair(currentX, currentY));
        }

        for(int q=0; q<currents.size(); q++){
            int currentX = currents[q].first;
            int currentY = currents[q].second;

            if(currentX == endX && currentY == endY){
                return;
            }

            for(int i=0; i<8; i++){
                int nextX = currentX + dx[i];
                int nextY = currentY + dy[i];

                if(nextX >= 0 && nextX < I && nextY >= 0 && nextY < I) {
                    if(!visit[nextX][nextY]){
                        visit[nextX][nextY] = true;
                        Queue.push(make_pair(nextX, nextY));
                    }
                }
            }
        }

        result++;

    }
}

int main(){
    int tc;
    cin >> tc;

    for(int test=0; test<tc; test++){
        bzero(visit, sizeof(visit));
        result = 0;
        cin >> I;

        int startX, startY;
        cin >> startX >> startY;

        int endX, endY;
        cin >> endX >> endY;

        BFS(startX, startY, endX, endY);

        cout << result << '\n';
    }

    return 0;
}

---