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

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

Approach

사용 알고리즘: bfs

• 입력받은 시작지점 (x,y)에서부터 bfs를 수행하면서 값이 0이면서 아직 방문하기 전의 지점을 방문해서 그 이전 방문지점의 거리에 1을 더한 값을 matrix에 저장
• 결과적으로 입력받은 도착지점 (x,y)에 도달했을 때 도착지점의 값이 곧 답이 된다.

1. 2차원 matrix를 모두 0으로 초기화
2. 시작지점과 도착지점을 입력받고 시작지점에서부터 bfs수행 (이때, 나이트가 체스판 밖을 넘어가면 무시, 이미 방문했던 지점이면 무시, 이동할 수 있는 지점으면 이동 후 값 업데이트)
3. 도착지점에 도착하면 break하고 도착지점에 저장된 값 반환

Source Code

# include <iostream>
# include <queue>
# include <vector>
#include <string.h>
using namespace std;

int n; 
int graph[301][301] = {0,}; // 체스판의 정보를 담는 2차원 matrix
							// 모두 0으로 초기화 한다 

// 나이트의 이동경로 방향벡터 정의 
int dx[8] = {-1, 1, -1, 1, -2, 2, -2, 2};
int dy[8] = {-2, 2, 2, -2, 1, -1, -1, 1};

int bfs(int start_x, int start_y, int end_x, int end_y)
{
    queue<pair<int, int>> q; // 큐 정의 
    
    q.push({start_x, start_y}); // 시작지점 넣기 
    
    while (!q.empty())
    {
    	// 현재 지점 정보 꺼내기 
        int x = q.front().first;
        int y = q.front().second;
        
        // 현재 지점이 도착 지점이라면 종료 
        if (x == end_x && y == end_y)
            break;
        
        q.pop();
        
        // 나이트가 이동할 수 있는 모든 경로를 확인하면서 
        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 만약 이동한 지점이 체스판을 벗어난다면 무시 
            if (nx <= -1 || ny <= -1 || nx >= n || ny >= n)
                continue;
            // 아직 방문하지 않은 지점이라면 
            if (graph[nx][ny] == 0)
            {
            	// 최단거리 기록 
                graph[nx][ny] = graph[x][y] + 1;
                // 큐에 이동한 새 지점 집어넣기 
                q.push({nx, ny});
            }
        }
    }
    
    // 도착지점에 저장된 값 반환 
    return graph[end_x][end_y];
}



int main()
{
	// 테스트케이스 입력받기 
    int T;
    cin >> T;
    
    // 각 테스트케이스마다 
    for (int t = 0; t < T; t++)
    {
    	// 정보 입력받기 
        int start_x, start_y, end_x, end_y;
        cin >> n;
        cin >> start_x >> start_y;
        cin >> end_x >> end_y;
        
        // bfs 수행 후 답 출력 
        cout << bfs(start_x, start_y, end_x, end_y) << endl;
        
        // 2차원 matrix 초기화 
        memset(graph, 0, sizeof(graph));
    }
    
    return 0;
}

memset에 대해 처음 알았다. 그냥 graph[301][301] = {0,}; 로 초기화 했는데 그건 안된다. 왤까? 꼭 memset을 써야되나요??