https://www.acmicpc.net/problem/7562
문제
> 체스판 위에 한 나이트가 놓여져 있다.
> 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다.
> 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
> 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
> 각 테스트 케이스는 세 줄로 이루어져 있다.
> 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다.
> 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다.
> 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
접근
그래프 탐색을 이용해 나이트가 이동할 수 있는 경로를 다 따져서 이동 할 때마다 횟수를 누적해 이 중에서 제일 작은 수를 출력한다.
나이트가 가능한 경로는 8가지이므로 이것도 8방 탐색이지만, 위치가 다르기 때문에 각각의 8가지에 위치를 선언해준다.
그리고 그래프 탐색에서 큐에 넣을 수들이 체스판에서의 좌표와 현재까지의 이동한 횟수이므로 struct로 세가지를 처리해준다.
이제 입력으로 첫 위치가 들어오면 그걸 큐에 넣고 앞에서 정의해준 나이트의 8가지 움직임을 반복문을 통해 따져본다. 체스판을 넘어가지 않으면서 이미 갔던 자리가 아닌 곳을 다음 탐색으로 큐에 넣는다. 큐에 넣는 새로운 좌표를 구하면서 동시에 struct의 세번째인 cnt에 1씩 횟수를 누적해 이 또한 같이 넘겨준다.
while문 중간에 만약 목표위치에 도달했는지를 봐야하므로
현재의 좌표가 목표좌표와 같은지 확인한다. 같다면 여기서 같이 온 cnt값을 가지고 Min값과 min연산을 해준다. 계속 하면 가장 작은 이동 횟수가 담겨져있을것이다.
문제해결
> 체스판의 크기 l, 목표 좌표 행과 열인 endr, endc를 선언해주고 이동횟수의 최소를 위해 Min변수도 선언해준다.
> 나이트의 이동경로 8가지를 각각 위로 두가지 우로 두가지, 아래로 두가지 좌로 두가지에 대해 정의해준다.
> 체스판에서 이미 갔던좌표를 표시하기 위해 부울형으로 방문처리용 벡터를 준다.
> 큐에 전달할 세 쌍을 각각 행, 열, 이동횟수로 선언해주고 그래프 탐색 메소드 Chess를 정의해준다.
> 큐에 세 쌍의 입력을 받아 넣어주고 탐색을 시작한다.
> 현재 탐색중인 좌표가 목표지점인지 검증하는 부분을 정의해주고, 여기서 이동횟수의 최소값을 갱신해준다.
> 나이트가 이미 갔던 좌표를 마킹해준다.
> 반복문을 통해 8방을 탐색한다. 얻은 다음 좌표가 체스판을 넘어가지 않으면서 가지 않았던 좌표이면 큐에 넣어준다. 이때, 이동횟수도 1누적해준다.
> main함수에서 테스트 케이스를 입력받고 테스트 케이스마다 시작좌표, 체스판의 크기, 목표좌표를 입력받는다. Min의 최악의 경우엔 INT의 최대값을 넣어주고 그래프 탐색메소드에서 min연산을 한다.
> 그래프 탐색메소드에 시작좌표와 아직 이동하지않았으므로 0을 넣고 돌린다. 끝나면 Min엔 최소 이동횟수가 들어있다.
> Min을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int l;
int endr, endc;
int Min;
int dir[8] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int dic[8] = { -1, 1, 2, 2, 1, -1, -2, -2 };
vector<vector<bool>> chess;
struct rcc
{
int row, col, cnt;
};
void Chess(int r, int c, int ct)
{
queue<rcc> q;
q.push({ r, c, ct });
while (!q.empty())
{
int fr = q.front().row;
int fc = q.front().col;
int fcnt = q.front().cnt;
q.pop();
if (fr == endr && fc == endc)
{
Min = min(Min, fcnt);
continue;
}
if (chess[fr][fc]) continue;
chess[fr][fc] = true;
for (int i = 0; i < 8; i++)
{
int nr = fr + dir[i];
int nc = fc + dic[i];
int ncnt = fcnt + 1;
if (nr < 0 || nr >= l) continue;
if (nc < 0 || nc >= l) continue;
if(!chess[nr][nc]) q.push({ nr, nc, ncnt });
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
Min = INT_MAX;
int startr, startc;
cin >> l;
chess.assign(l, vector<bool>(l, false));
cin >> startr >> startc;
cin >> endr >> endc;
Chess(startr, startc, 0);
cout << Min << '\n';
}
}
후기
첫 오류로 무한 루프로 인해 결과값이 나오지 않고 계속 멈춰있었다. 처음엔 나이트가 갔던곳을 경유해갈 수도 있겠다 싶어 이를 처리하지 않았지만 무한루프가 나고 다시 생각해보니 똑같은자리에서 왔다갔다를 반복하고 있는 경우가 있다고 생각했다. 그래서 체스판을 부울형으로 그려 방문처리를 해주었더니 해결됐다.
다음은 테스트 케이스의 모든 결과가 같은 값이 나오는거였다.
처음에 Min값을 전역에서 INT_MAX로 주고했다. 이 때문에 첫 테스트 케이스 이후 Min의 값이 첫 테스트케이스보다 작은게 아니라면 절대 갱신이 안되는거였다. 그래서 전역에선 Min 변수만 선언하고 테스트 케이스의 while문 안에서 초가값을 선언해주어서 해결했다.
마지막으로 비주얼 스튜디오는 괜찮은데 제출했을 때 컴파일 에러가 났다. 컴파일 에러는 보통 오타나 빼먹은거라 오타를 봤더니 없어서 뭘 빼먹었구나 싶었더니 Min을 INT_MAX로 줬는데 climits를 선언해주지 않아서 그렇다고 한다.
이 까지 수정하고 나니 맞았다.
