나이트의 이동 (Silver 2)
문제
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
접근법
이 문제에서는 나이트가 목표지점까지 이동하기 위한 최단거리를 구하는 문제이다. 최단거리 문제는 BFS로 풀 수 있다. 나이트 특유의 2*1 이동 방식에 유의해서 인접 노드를 잘 설정하면 쉽게 풀 수 있는 문제이다. 필자는 dx,dy 배열을 사용하여 나이트의 이동을 표현하였다.
array<int, 8> dx{ -2, -1, 1, 2, 2, 1, -1, -2 };
array<int, 8> dy{ 1, 2, 2, 1, -1, -2, -2, -1 };자료구조 선택
BFS는 큐를 활용해서 구현할 수 있다. 큐에는 다음 나이트의 "이동"을 담는다. 이동에는 이동할 위치와 다음 이동의 깊이(=이동 거리)를 담을 수 있다. 이동에 대한 구조체를 다음과 같이 정의할 수 있다.
struct Move {
Move(int _x, int _y, int _depth)
: x(_x)
, y(_y)
, depth(_depth)
{}
int x; // 다음 위치의 x 좌표
int y; // 다음 위치의 y 좌표
int depth; // 다음 이동의 깊이(이동 횟수)
};나이트의 이동에 대한 클래스 Knight를 다음과 같이 정의하였다.
class Knight {
public:
Knight() {}
void InputData(); // 데이터 입력 및 visited 배열 초기화
int Search(); // BFS 탐색
private:
static const int MAX = 304;
array<array<bool, MAX>, MAX> visited {};
int l; // 체스판의 크기
int cx, cy, tx, ty; // 현재 위치, 목표의 위치
array<int, 8> dx{ -2, -1, 1, 2, 2, 1, -1, -2 };
array<int, 8> dy{ 1, 2, 2, 1, -1, -2, -2, -1 };
};정의한 Knight 클래스는 main 함수에서 다음과 같이 사용한다.
int main() {
// 입출력 성능 향상을 위한 설정
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int T; // 테스트 케이스
cin >> T;
while(T--)
{
Knight knight; // Knight 클래스 생성
knight.InputData(); // 데이터 입력
cout << knight.Search() << endl; // 최단거리 탐색 및 결과 출력
}
return 0;
}이렇게 클래스로 캡슐화하여 문제를 풀 경우 여러 테스트 케이스를 처리하더라도 큐나 방문 기록 배열 초기화에 대해서 신경 쓰지 않아도 된다는 장점이 있다.
구현
데이터 입력 부분
데이터 입력 함수이 Knight::InputData 멤버 함수에서는 체스판의 크기와 체스 말의 위치를 입력받는다. 그리고 체스판 밖에 해당하는 위치의 방문 기록은 모두 true로 설정한다. 이렇게 하면 다음 이동이 체스판을 벗어나는지 별도의 검사를 하지 않아도 되기 때문에 더 빠른 계산이 가능하다. 대신 체스 판의 크기와 체스 말의 위치에 일정 부분 offset값을 더 해줘야 한다.
void Knight::InputData()
{
cin >> l; // 체스판의 크기
cin >> cx >> cy >> tx >> ty; // 현재 체스말의 위치
l += 4;
cx += 2;
cy += 2;
tx += 2;
ty += 2;
// 체스판 밖에 해당하는 위치의 방문 기록을 true로 설정
for (int i = 0; i < l; i++)
{
visited[i][0] = true;
visited[i][1] = true;
visited[i][l - 1] = true;
visited[i][l - 2] = true;
visited[0][i] = true;
visited[1][i] = true;
visited[l - 1][i] = true;
visited[l - 2][i] = true;
}
}BFS 탐색 부분
출발 위치와 목표지점이 같은 경우에 대한 예외처리를 잊지 말자. 전체적인 탐색 코드는 일반적인 BFS와 차이가 없다.
int Knight::Search()
{
// 출발위치와 목표지점이 같은 경우
if (cx == tx && cy == ty)
return 0;
queue<Move> q;
// (1,1) 에서 시작
q.emplace(cx, cy, 0);
visited[cx][cy] = true;
while (!q.empty())
{
Move cur = q.front();
q.pop();
// 인접노드 검사
for (size_t i = 0; i < dx.size(); ++i)
{
Move next(cur.x + dx[i], cur.y + dy[i], cur.depth + 1);
// 이미 방문한 노드이거나, 범위를 벗어나는 노드
if (visited[next.x][next.y] == true) continue;
// 목표 도착
if (next.x == tx && next.y == ty)
{
int retVal = next.depth;
return retVal;
}
// 방문하지 않은 위치라면, 방문 체크 후 해당 위치 큐에 삽입.
else
{
visited[next.x][next.y] = true;
q.emplace(next.x, next.y, next.depth);
}
}
}
// 탐색에 실패한 경우
return -1;
}성능 평가
해당 알고리즘의 시간 복잡도는 최악의 경우 모든 위치를 방문해야 한다. 그래서 시간 복잡도는 \(O(N)\)이다. 다만 문제에서 입력으로 체스판의 한 변의 크기 \(l\)을 주기 때문에 한 변의 길이를 기준으로 보면 \(O(l^2)\)이라고 할 수 도 있다. 공간 복잡도를 살펴보면 방문 기록 배열의 크기와 큐의 크기는 전체 이동 가능한 위치에 비례하기 때문에 \(O(N )\) 혹은 \(O(l^2)\)라고 할 수 있다.
전체 코드
#include <iostream>
#include <array>
#include <queue>
#define endl '\n'
using namespace std;
struct Move {
Move(int _x, int _y, int _depth)
: x(_x)
, y(_y)
, depth(_depth)
{}
int x; // 다음 위치의 x 좌표
int y; // 다음 위치의 y 좌표
int depth; // 다음 이동의 깊이(이동 횟수)
};
class Knight {
public:
Knight() {}
void InputData(); // 데이터 입력 및 visited 배열 초기화
int Search(); // BFS 탐색
private:
static const int MAX = 304;
array<array<bool, MAX>, MAX> visited {};
int l; // 체스판의 크기
int cx, cy, tx, ty; // 현재 위치, 목표의 위치
array<int, 8> dx{ -2, -1, 1, 2, 2, 1, -1, -2 };
array<int, 8> dy{ 1, 2, 2, 1, -1, -2, -2, -1 };
};
void Knight::InputData()
{
cin >> l; // 체스판의 크기
cin >> cx >> cy >> tx >> ty; // 현재 체스말의 위치
l += 4;
cx += 2;
cy += 2;
tx += 2;
ty += 2;
// 체스판 밖에 해당하는 위치의 방문 기록을 true로 설정
for (int i = 0; i < l; i++)
{
visited[i][0] = true;
visited[i][1] = true;
visited[i][l - 1] = true;
visited[i][l - 2] = true;
visited[0][i] = true;
visited[1][i] = true;
visited[l - 1][i] = true;
visited[l - 2][i] = true;
}
}
int Knight::Search()
{
if (cx == tx && cy == ty)
return 0;
queue<Move> q;
// (1,1) 에서 시작
q.emplace(cx, cy, 0);
visited[cx][cy] = true;
while (!q.empty())
{
Move cur = q.front();
q.pop();
// 인접노드 검사
for (size_t i = 0; i < dx.size(); ++i)
{
Move next(cur.x + dx[i], cur.y + dy[i], cur.depth + 1);
// 이미 방문한 노드이거나, 범위를 벗어나는 노드
if (visited[next.x][next.y] == true) continue;
// 목표 도착
if (next.x == tx && next.y == ty)
{
int retVal = next.depth;
return retVal;
}
// 방문하지 않은 위치라면, 방문 체크 후 해당 위치 큐에 삽입.
else
{
visited[next.x][next.y] = true;
q.emplace(next.x, next.y, next.depth);
}
}
}
// 탐색에 실패한 경우
return -1;
}
int main() {
// 입출력 성능 향상을 위한 설정
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int T; // 테스트 케이스
cin >> T;
while(T--)
{
Knight knight; // Knight 클래스 생성
knight.InputData(); // 데이터 입력
cout << knight.Search() << endl; // 최단거리 탐색 및 결과 출력
}
return 0;
}
