[이것이 코딩 테스트다.Part02.Chapter04] - 왕실의 나이트 (Java)

안녕하세요.
지금까지 계속 저만의 기술 블로그를 만들어야지, 만들거야
마음으로만 다짐하다가 인제야 시작하게 되었습니다.
비록 시작은 코딩일기지만, 그 끝은 창대하게
어엿한 개발자 블로그로 성장할 수 있도록 노력하겠습니다.

Prologue

안녕하세요!
나동빈 저자의 [이것이 코딩 테스트다] 문제풀이 정리 포스트입니다.

[왕실의 나이트]

<문제>

행복 왕국의 왕실 정원은 체스판과 같은 8 X 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다.

나이트는 말을 타고 있기 때문에 이동을 할 때에는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 두 간 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 간 이동한 뒤에 수평으로 한 칸 이동하기

이처럼 8 X 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.

예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 다음과 같은 2가지이다. a1의 위치는 좌표 평면에서 구석의 위치에 해당하며 나이트는 정원의 밖으로는 나갈 수 없기 때문이다.

1. 오른쪽으로는 두 칸 이동 후 아래로 한 칸 이동하기 (c2)
2. 아래로 두 칸 이동 후 오른쪽으로 한 칸 이동하기 (b3)

또 다른 예로 나이트가 c2에 위치해 있다면 나이트가 이동할 수 있는 경우의 수는 6가지이다. 이건 직접 계산해보시오.

<입력 조건>

• 첫째 줄에 8 X 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입련된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.

<출력 조건>

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

<입력 예시>                                                                             <출력 예시>

• a1                                                                                             2

PseudoCode

처음 문제를 봤을 때 들었던 생각은

1. 나이트의 현재 위치를 행과 열로 나누어 잡고.

2. 나이트가 이동할 수 있는 8가지 경우의 수를 시도해보고 
   체스판을 벗어나지 않는 경우의 수를 출력한다.

입니다.

처음엔 체스판이 나와서 2차원 배열로 풀어야하나 싶었지만 풀다보니 굳이 2차원 배열로 어렵게 돌아갈 필요가 없었습니다.

단순히 행과 열이 나이트가 이동할 수 있는 8가지의 경우의 수에 대해서 체스판을 벗어나는지 아닌지만 체크하면 쉽게 풀 수있는 문제였습니다.

SourceCode

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String nightPos = br.readLine();

        int row = nightPos.charAt(1) - '0';
        int col = nightPos.charAt(0) - 'a' + 1;

        int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
        int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};

        int count = 0;

        for (int i = 0; i < 8; i++)
        {
            int nextRow = row + dx[i];
            int nextColumn = col + dy[i];

            if ((1 <=nextRow && nextRow <= 8) &&  (1 <= nextColumn && nextColumn <= 8))
            {
                count += 1;
            }
        }

        System.out.println(count);
    }

}

(언제나처럼 코드리뷰! 부탁드립니다!)

수도코드를 그대로 구현하였으며 딱히 어려운점은 없었습니다.

코드를 살펴보면,

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String nightPos = br.readLine();

int row = nightPos.charAt(1) - '0';
int col = nightPos.charAt(0) - 'a' + 1;

int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};

int count = 0;

우선 필요한 변수들을 몇 가지 선언 및 초기화하는 파트입니다.

• 값을 입력받기 위한 BufferedReader
• 나이트의 위치를 우선 문자열로 받는 nightPos
• 나이트의 현재 위치의 행 row
• 나이트의 현재 위치의 행 col
• 나이트의 이동계산을 위한 dx[ ], dy[ ]
• 경우의 수를 위한 count

여기에서 중요한 포인트는 아무래도 dx[ ], dy[ ] 입니다.
나중에 bfs와 dfs 문제를 풀때도 자주 쓰이게 될 친구들인데 저는 처음에 이게 도무지 이해가 가지 않아서 어려움을 겪었습니다 ㅠㅠ

이 dx[ ], dy[ ] 는 나중에 반복문을 순회할때 사용되는데 첫 번째의 경우를 예를 들면 dx[0] = -2, dy[0] = -1 이므로 각각의 값을 row와 col에 더해주면 나이트가 이동했을 때의 좌표값을 구할 수 있습니다.
이렇게 구한 좌표값이 체스판을 벗어나는지 아닌지만 잘 체크하면 되겠습니다.

for (int i = 0; i < 8; i++)
{
    int nextRow = row + dx[i];
    int nextColumn = col + dy[i];

    if ((1 <=nextRow && nextRow <= 8) &&  (1 <= nextColumn && nextColumn <= 8))
    {
        count += 1;
    }
}

System.out.println(count);

상기에 언급했던 나이트가 이동한 좌표값이 체스판을 벗어나는지 체크하는 부분입니다.

1. 8가지 경우에 대해서 나이트를 전부 이동시켜봅니다.

2. 이동한 나이트의 좌표가 체스판 내부에 있다면 가능한 경우의 수를 의미하는
   count에 1을 더해줍니다.

3. 계산된 count를 출력합니다.

Epilogue

처음에 체스판을 보고 쫄았지만.. 다시 천천히 생각해보고 간단하게 풀 수 있음을 깨달았습니다. 하지만 만약에 저 dx, dy 개념을 아예 몰랐다면 조금 어려울 수 있지 않았을까 싶습니다.

코드에 대한 조언은 언제나 환영이며, 오히려 부탁드리겠습니다.