9204. 체스

1. 문제 링크
2. 테스트 케이스

처참한 결과

1. 문제 해결

필자처럼 많이 틀릴 문제가 아니다!

1-1. 메모리 초과가 발생한 이유

알고리즘을 아래와 같이 구현하였다.

1. 시작 좌표를 기준으로 비숍의 움직임을 진행한다.
2. 배열을 벗어나지 않았다면 움직인 좌표를 매개변수로 넘기면서 재귀를 진행한다.
3. 현재 좌표가 도착 좌표와 동일할 경우, 움직인 횟수를 비교하여 최소로 움직인 String을 출력한다.

시작 위치의 비숍을 한 칸씩 이동시키면서 StringBuilder에 좌표를 넣고 빼고를 진행하면 "메모리 초과"가 발생한다.

1-2. 비숍의 움직임

비숍을 움직여 3가지 상태를 얻을 수 있다.

1. 시작 좌표 == 도착 좌표
2. 시작 좌표 != 도착 좌표
 2-1. 도착 좌표로 갈 수 없는 경우
 2-2. 도착 좌표로 갈 수 있는 경우
  2-2-1. 한 번만으로 이동 가능한 경우
  2-2-2. 두 번만으로 이동 가능한 경우

2-1, 2-2 상태의 경우, 직접 체스판을 그려 눈으로 확인하는게 빠르다.

2-2의 경우를 보자.
시작 좌표에서 도착 좌표로 갈 수 있는 경우인데, 반드시 최대 2번만으로 이동이 가능하다!! 이것도 직접 그려 확인하자.

명심해야 할 것은 최대 2번이다. 즉, 1번만으로도 도착 좌표에 도달할 수 있다. (ex. F 1 E 2)

따라서, 최종 알고리즘은 아래와 같다.

1. 시작 좌표의 비숍을 4방향으로 이동시켜본다.
2. 1번에서 이동시킨 좌표에 도착 좌표의 비숍이 있는 지 확인한다.
 2-1. 있을 경우, "1 시작 좌표 도착 좌표" 출력
 2-2. 없을 경우, 도착 좌표의 비숍을 1번과 동일하게 진행하여 "2 시작 좌표 중첩 되는 좌표 도착 좌표"를 출력한다.

1-3. 많이 틀린 이유

조건대로 진행하였는데 33%에서 계속 "틀렸습니다" 가 발생하였는데 이유는 연산자 우선순위를 간과하였다.

틀렸을 때의 코드는 아래와 같다.

...
if (Math.abs(start_x - finish_x) + Math.abs(start_y -finish_y) % 2 == 1) {
	System.out.println("Impossible");
}
...

괄호를 치지 않아서 나머지 연산을 진행할 때, 에러가 계속 발생하였고 이로 인해 틀리게 되었다.

2. 소스 코드

//체스
import java.util.*;
import java.io.*;

public class Main {
	static int ud[] = { -1, -1, 1, 1 };
	static int rl[] = { 1, -1, 1, -1 };

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

		int tc = Integer.parseInt(br.readLine());

		for (int i = 0; i < tc; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int start_y = st.nextToken().charAt(0) - 'A';
			int start_x = 8 - Integer.parseInt(st.nextToken());

			int finish_y = st.nextToken().charAt(0) - 'A';
			int finish_x = 8 - Integer.parseInt(st.nextToken());

			if (start_x == finish_x && start_y == finish_y)
				System.out.println("0 " + (char) ('A' + start_y) + " " + (8-start_x));
			else if ((Math.abs(start_x - finish_x) + Math.abs(start_y - finish_y)) % 2 == 1) {
				System.out.println("Impossible");
			} else {
				boolean[][] visited = new boolean[8][8];

				moveVishop(start_x, start_y, finish_x, finish_y, visited);
				
				if(visited[finish_x][finish_y]) {
					System.out.println("1 " + (char) ('A' + start_y) + " " + (8-start_x) + " " + (char) ('A' + finish_y) + " " + (8-finish_x));
					continue;
				}
				//print(visited);

				System.out.print("2 " + (char) ('A' + start_y) + " " + (8-start_x) + " ");
				moveVishop(finish_x, finish_y, finish_x, finish_y, visited);
			}
		}
	}

	private static void moveVishop(int sx, int sy, int fx, int fy, boolean[][] visited) {

		for (int i = 0; i < 4; i++) {
			int x = sx, y = sy;
			while (true) {
				visited[x][y] = true;
				int nx = x + ud[i];
				int ny = y + rl[i];

				if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8)
					break;

				if (visited[nx][ny]) {
					System.out.println((char) (ny + 'A') + " " + (8-nx) + " " + (char) (fy + 'A') + " " + (8-fx));
					return;
				}

				x = nx;
				y = ny;
			}
		}
	}

	private static void print(boolean[][] visited) {
		for (int i = 0; i < visited.length; i++) {
			for (int j = 0; j < visited.length; j++) {
				if (visited[i][j])
					System.out.print("T");
				else
					System.out.print("F");
			}
			System.out.println();
		}
	}
}