소스코드

구현 : 왕실의 나이트

문제

문제 정의

행복 왕국의 왕실 정원은 체스판과 같은 8x8좌표 평면이다.
왕실 정원의 특정한 한 칸에 나이트가 서있다.
나이트는 이동 시, L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다.
나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
- 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
- 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

<hr/>	a	b	c	d	e	f	g	h
1
2
3
4
5
6
7
8

이처럼 8x8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.
이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하고, 열 위치를 표현할 때는 a부터 h로 표현한다.
예시
- 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 다음 2가지이다.
  - 오른쪽으로 두 칸 이동 후, 아래로 한 칸 이동하기 (결과적으로 c2에 위치)
  - 아래로 두 칸 이동 후, 오른쪽으로 한 칸 이동하기 (결과적으로 b3에 위치)

입력조건

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

출력조건

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

입·출력 예시

입력
```
c2
```
출력
```
6
```

풀이

문제 해설

나이트가 이동할 수 있는 모든 경우의 수는 아래와 같이 총 8가지이다.
- 위로 2칸, 왼쪽으로 1칸
- 위로 2칸, 오른쪽으로 1칸
- 아래로 2칸, 왼쪽으로 1칸
- 아래로 2칸, 오른쪽으로 1칸
- 왼쪽으로 2칸, 위로 1칸
- 왼쪽으로 2칸, 아래로 1칸
- 오른쪽으로 2칸, 위로 1칸
- 오른쪽으로 2칸, 아래로 1칸
따라서, 단순히 위 8가지 중 가능한 이동만 확인하면 된다.
- 가능한 이동: 평면을 벗어나지 않는 이동

소스코드

public class 왕실의_나이트 {
    
  private static int answer = 0;
  
  public static int solution1(int row, char col) {
    //위로 이동하는 경우
    if (row > 2) {
      //왼쪽으로 이동하는 경우
      if (col > 'a') {
        answer++;
      }
      //오른쪽으로 이동하는 경우
      if (col < 'h') {
        answer++;
      }
    }
    //아래로 이동하는 경우
    if (row < 7) {
      //왼쪽으로 이동하는 경우
      if (col > 'a') {
        answer++;
      }
      //오른쪽으로 이동하는 경우
      if (col < 'h') {
        answer++;
      }
    }
    //왼쪽으로 이동하는 경우
    if (col > 'b') {
      //위로 이동하는 경우
      if (row > 1) {
        answer++;
      }
      //아래로 이동하는 경우
      if (row < 8) {
        answer++;
      }
    }
    //오른쪽으로 이동하는 경우
    if (col < 'g') {
      //위로 이동하는 경우
      if (row > 1) {
        answer++;
      }
      //아래로 이동하는 경우
      if (row < 8) {
        answer++;
      }
    }

    return answer;
  }
}

시간복잡도

solution1 의 경우
- 정답 구하기
  - 단순히 8가지 경우 중 가능한 것만 확인하면 된다.
  - 최대 경우의 수가 8가지이기 때문이다.
- 따라서 총 시간복잡도는 O(1) 이다.

나동빈, 『이것이 코딩 테스트다』

본 게시글은 위 교재를 기반으로 정리한 글입니다.