[BOJ/백준] 7562 나이트의 이동

● [문제번호 7562] 나이트의 이동

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

7562번: 나이트의 이동

 

● 알아야 할 것

: BFS

: pair 자료구조와 메소드

: queue 자료구조와 메소드

 

● 풀이 과정

: BFS를 이용하여 구현했다.

체스판에서

다음 위치로 이동 불가능한 경우는 다음과 같다.

1. 체스판의 X축을 벗어나는 경우

2. 체스판의 Y축을 벗어나는 경우

3. 방문한 적이 있지만 최소 거리가 아닌 경우

 

: DFS도 구현했지만 '시간 초과'를 벗어나기 어려운 것 같다.

왜냐하면 한 위치에서 DFS로 끝까지 갔다가 다음 위치로 들어가서 끝까지 갔다가하면

불필요한 실행과 실행시간이 많이 걸리는 것 같다.

 

구글링 해도 적절한 DFS 해법도 없는 것 같고,

해당 문제의 '알고리즘 분류'에서도 '깊이 우선 탐색'이 없는 것을 보니

주어진 제약조건에서 BFS로 풀어야 적절한 것 같다.

 

● 주의 할 것

: 각 테스트케이스 마다 체스판을 초기화 해줘야한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// controlX : 체스판에서 이동하기 위한 좌상, 우상, 우하, 좌하
// controlY : 체스판에서 이동하기 위한 좌상, 우상, 우하, 좌하
// chess : 체스판 저장
// dist : (fromX, fromY)에서 (index1, index2)까지 최소 이동 거리 (방문기록)
// fromX, fromY : 나이트가 현재 있는 칸
// toX, toY : 나이트가 이동하려고 하는 칸
int controlX[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int controlY[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int chess[301][301];
int dist[301][301];
int T, L, fromX, fromY, toX, toY;

// 넓이 우선 탐색
// 기본적인 작성 형태 + 종료 조건 추가
int bfs()
{
    queue<pair<int, int>> q;
    
    // 초기 위치 0이 아닌 1로 저장
    // (0은 방문X로 구분하기 위해)
    dist[fromX][fromY] = 1;
    q.push(pair<int, int>(fromX, fromY));
    
    while(!q.empty())
    {
        int fromRow = q.front().first;
        int fromCol = q.front().second;
        
        q.pop();
        
        // 목표 위치 도달
        if(fromRow == toX && fromCol == toY)
            return dist[toX][toY];
        
        for(int i = 0; i < 8; i++)
        {
            int row = fromRow + controlX[i];
            int col = fromCol + controlY[i];
            
            // 방문하면 안되는 3가지
            // 1. 체스판의 X축을 벗어나는 경우
            if(row < 0 || L <= row)
                continue;
            // 2. 체스판의 Y축을 벗어나는 경우
            else if(col < 0 || L <= col)
                continue;
            // 3. 방문한 적 있지만 최소 거리가 아닌 경우
            else if(dist[row][col] != 0 && dist[row][col] <= dist[fromRow][fromCol] + 1)
                continue;
            else
            {
                dist[row][col] = dist[fromRow][fromCol] + 1;
                q.push(pair<int, int>(row, col));
            }
        }
    }
    
    // 목표지점에 도달하지 못 한 경우
    return 0;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> T;
    
    while(T--)
    {
        cin >> L;
        
        cin >> fromX >> fromY >> toX >> toY;
        
        // 각 테스트케이스의 체스판 방문기록 초기화
        fill(&dist[0][0], &dist[L][L], 0);
        
        // 최소 이동 횟수(bfs() - 1) 또는 못 가는 경우(0)
        cout << max(bfs() - 1, 0) << "\n";
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [600 - 그래프 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	13023	ABCDE	https://pirateturtle.tistory.com/269
2	1260	DFS와 BFS	https://pirateturtle.tistory.com/270
3	11724	연결 요소의 개수	https://pirateturtle.tistory.com/271
4	1707	이분 그래프	https://pirateturtle.tistory.com/272
5	2667	단지번호붙이기	https://pirateturtle.tistory.com/273
6	4963	섬의 개수	https://pirateturtle.tistory.com/274
7	2178	미로 탐색	https://pirateturtle.tistory.com/275
8	7576	토마토	https://pirateturtle.tistory.com/276
9	7562	나이트의 이동	https://pirateturtle.tistory.com/277