[백준] 7562번 : 나이트의 이동

문제

 

---

풀이

 

myunji.tistory.com/284

[백준] 2178번 : 미로 탐색

이 문제랑 똑같은 유형인데 그냥 방향이 4개에서 8개가 됐을 뿐이다.

---

소스코드

 

#include <iostream>
#include <cstring>
#include <queue>
#include <utility>

using namespace std;

int matrix[300][300], l;
pair<int, int> dir[8] = {{1,  -2}, //나이트가 갈 수 있는 방향
                         {2,  -1},
                         {2,  1},
                         {1,  2},
                         {-1, 2},
                         {-2, 1},
                         {-2, -1},
                         {-1, -2}};

int bfs(pair<int, int> start, pair<int, int> end) {
    queue<pair<int, int>> q;

    q.push(start);
    while (matrix[end.first][end.second] == 0) { //도착점 도달하면 반복 종료
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
        for (int i = 0; i < 8; i++) { //방향 체크
            int next_row = row + dir[i].first;
            int next_col = col + dir[i].second;
            if ((next_row >= 0) && (next_row < l) && (next_col >= 0) && (next_col < l) && //범위 체크
                (matrix[next_row][next_col] == 0)) { //방문 체크
                matrix[next_row][next_col] = matrix[row][col] + 1; //matrix[next_row][next_col]를 오기 위해 몇 번 거쳐야 하는가?
                q.push(make_pair(next_row, next_col));
            }
        }
    }
    return matrix[end.first][end.second] - 1;
}

int main() {
    int T, w, x, y, z;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> l >> w >> x >> y >> z;
        matrix[w][x] = 1;
        pair<int, int> start = {w, x};
        pair<int, int> end = {y, z};
        cout << bfs(start, end) << '\n';
        for (int i = 0; i < l; i++) //2차원 배열 초기화
            memset(matrix[i], 0, sizeof(int) * l);
    }
}

전체 소스코드다. 2178번과 특별하게 다른 부분만 설명하도록 하겠다.

 

    while (matrix[end.first][end.second] == 0) { //도착점 도달하면 반복 종료
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
        for (int i = 0; i < 8; i++) { //방향 체크
            int next_row = row + dir[i].first;
            int next_col = col + dir[i].second;
            if ((next_row >= 0) && (next_row < l) && (next_col >= 0) && (next_col < l) && //범위 체크
                (matrix[next_row][next_col] == 0)) { //방문 체크
                matrix[next_row][next_col] = matrix[row][col] + 1; //matrix[next_row][next_col]를 오기 위해 몇 번 거쳐야 하는가?
                q.push(make_pair(next_row, next_col));
            }
        }
    }

while문의 종료조건을 도착점에 도달한 때로 수정했다.

 

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> l >> w >> x >> y >> z;
        matrix[w][x] = 1;
        pair<int, int> start = {w, x};
        pair<int, int> end = {y, z};
        cout << bfs(start, end) << '\n';
        for (int i = 0; i < l; i++) //2차원 배열 초기화
            memset(matrix[i], 0, sizeof(int) * l);
    }

이렇게 테스트케이스가 여러개 들어오는 문제는 배열 초기화를 잊으면 안된다.