Cannon's Tour
문제: NxN 크기의 장기판이 있다. 장기의 말들 중 포는 다음과 같은 규칙으로 움직인다. 위치 (x,y)에 놓인 포는 상하좌우 네 방향 중 하나로 다른 말 하나만을 건너뛴 어떤 위치로든 이동할 수 있다.
장기판의 현재 상태와, 포가 놓여져 있는 위치 (x,y)와 포가 최종적으로 이동할 목표 위치 (xd, yd)를 입력받아 현재 위치에서 목표 위치로 포가 이동할 방법이 존재하는지 검사하여 Yes 혹은 No를 출력하는 프로그램을 작성하라.
bool moveCannon(int** board, int N, int x, int y, int xd, int yd) {
if (!isInBoundary(x, y, N) || board[x][y] != CELL_VALID)
// Current position is not valid
return false;
else if (x == xd && y == yd) {
// Arrived at the destination
board[x][y] = CELL_VISITED;
return true;
}
else {
// Moved to the valid position
board[x][y] = CELL_VISITED;
// For every direction
for (int i = 0; i < 4; i++) {
int count = 0;
int xn = x;
int yn = y;
// Move ahead by one cell in the current direction
for (int j = 0; j < N; j++) {
xn += directions[i][0];
yn += directions[i][1];
if (!isInBoundary(xn, yn, N))
// Out of the boundary, quit moving ahead
break;
if (board[xn][yn] == CELL_TAKEN)
// Meet other chess pieces
count++;
if (count > 1)
// Meet more than one chess pieces, stop checking this direction
break;
if (count == 1 && board[xn][yn] == CELL_VALID)
// Only after one other chess piece
// And if the position is valid
if (moveCannon(board, N, xn, yn, xd, yd))
// check that position is the destination
return true;
}
}
// Counldn't find any paths from this position
board[x][y] = CELL_BLOCKED;
return false;
}
}🏠Take Home Message
1. Psuedo code를 작성하는 것은 생각보다 쉬웠다. 재귀함수의 특성을 이용하여
Base Case
: 입력이 체스판 밖으로 벗어나거나 유효하지 않은 곳일 경우에 false 리턴
: 입력이 도착지일 경우에 true 리턴
Recursive Case
: 네 가지 방향 중 조건을 만족하는 곳으로 재귀함수를 호출한다.
2. 재귀함수 안에서의 변수 사용이 어려웠다.
a. xn, yn을 이용하여 이동할 방향으로 1칸씩 전진시키기
b. Count를 이용하여 이동할 방향에서 첫 번째와 두 번째 만나는 말 사이로만 포를 이동시키기
이 부분은 디버깅을 통해 직접 수정해줬다.
3. Recursive Case에서 호출한 재귀함수의 리턴값을 사용하지 않았다.
: 반복문과 조건문을 이용해서 포를 이동하며 함수의 Recursion을 계속 실행했을 때, Base Case에서 true를 리턴한 경우나 길을 찾지 못해 반복문 을 빠져 나와 false 리턴한 경우에 Recursive Case를 빠져나오기 위해서는 반드시 return값을 이용해야 한다.
4. 재귀함수의 signature에서 많은 종류의 매개변수를 이용했다.:
: 재귀함수를 이용하려면 세부적인 매개변수가 필요한 건 사실이지만, C의 특성을 포함한 이유로 많은 매개변수를 이용했다. Clean Coding을 하고 싶지만 일단 구현했으니 만족한다.
