[JAVA 알고리즘]BAEKJOON 9204번 체스
체스
문제 설명
체스에서 비숍은 대각선으로만 움직일 수 있는 말이다. 비숍은 현재 있는 칸과 같은 색상을 가지는 칸은 몇 번 움직이면 이동할 수 있다. (체스판에 다른 말은 없다고 가정한다)
체스판 위의 두 좌표가 주어진다. 이때, 비숍이 한 좌표에서 다른 좌표로 이동할 수 있는지와 그 방법을 구하는 프로그램을 작성하시오. 체스판의 좌표는 글자(A-H)와 숫자(1-8)로 나타내며, 글자는 열에, 숫자는 행에 적혀져 있다.
그림 1 – 체스판, 비숍, 비숍이 한 번에 움직일 수 있는 위치
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 시작 위치 X와 도착 위치 Y가 주어진다. 각 위치는 두 글자가 공백으로 구분되어져 있다. 글자는 열, 숫자는 행이다. 중복되는 테스트 케이스는 주어지지 않는다.
출력
각 테스트 케이스에 대해서 한 줄을 출력한다. 만약, 비숍이 X에서 Y로 이동할 수 없으면 'Impossible'을 출력한다. 이 경우를 제외하면, 움직이는 방법을 출력한다.
움직일 수 있을 때는 먼저 움직인 횟수를 출력한다. 그 다음에는 입력 형식과 같은 형식으로 움직인 방법을 출력한다. 최대 4번 움직일 수 있으며, 가능한 경우가 여러 개일 때에는 아무거나 출력하면 된다.
제한사항
- 없음
입출력 예
| input | return |
| 3 E 2 E 3 F 1 E 8 A 3 A 3 |
Impossible 2 F 1 B 5 E 8 0 A 3 |
문제 분석
시작 위치에서 도착 위치까지 이동하는데 최대 4번 움직일 수 있으며, 여러 개의 가능한 경우가 있으면 아무거나 출력해도 된다.
하지만, 비숍은 체스판 안에서 모든 칸을 2번이면 움직일 수 있다. -> 2번의 조건으로 파악이 가능하다.
그러면 나올 수 있는 조건은 4가지로 볼 수 있다.
- 비숍이 이동할 수 없는 경우, 체스판의 다른 색에 위치해 있다.
- 비숍이 이동할 필요 없는 경우, 도착 위치가 시작 위치와 동일하다.
- 비숍이 한 번의 이동으로 도착할 경우, 시작 위치의 대각선 선상에 도착 위치가 있다.
- 비숍이 두 번의 이동으로 도착할 경우, 시작 위치의 대각선 선상에 도착 위치가 없다.
출력하는 방법은 4가지로 구분을 하고 두 번을 이동할 경우에는 중간 지점이 필요한데, 이를 시작 위치의 대각선과 도착 위치의 대각선의 교차되는 위치를 출력하면 해결할 수 있다.
손으로 풀기
- 체스판의 위치를 구분하기 위해서 이차배열로 체스판을 0과 1로 구현을 해준다.
- 입력값이 문자와 숫자로 주워지는데 체스판으로 확인하기 쉽게 하기 위해 좌표값으로 이용할 수 있도록 변환해 준다.
- 움직임을 확인하기 위해 boolean을 이차배열로 사용한다.
- 좌표를 이용해서 조건문으로 비숍이 이동할 수 없는 경우와 비숍이 이동할 필요 없는 경우는 바로 확인해 출력한다.
- 시작위치에서 대각선 방향으로 반복하면서 한번 이동이 아닌 체스판 끝까지 이동을 하도록 움직임이면서 도착 위치가 있으면 시작 위치와 도착위치를 출력한다.
- 도착위치에서 대각선 방향으로 반복하면서 끝까지 이동하면서 교차지점을 찾아 시작, 교차, 도착 위치를 출력한다.
나의 문제풀이
import java.io.*;
import java.util.*;
public class Main {
static int[] dx = {1, 1, -1, -1};
static int[] dy = {1, -1, 1, -1};
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder stringBuilder = new StringBuilder();
// 0,1로 체스판의 흰,검 형태로 만들어준다.
int[][] map = new int[8][8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (i % 2 == j % 2) {
map[i][j] = 1;
} else {
map[i][j] = 0;
}
}
}
// 테스트 케이스 만큼 반복한다.
int T = Integer.parseInt(bufferedReader.readLine());
for (int i = 0; i < T; i++) {
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int startY = stringTokenizer.nextToken().charAt(0) - 'A';
int startX = Math.abs(Integer.parseInt(stringTokenizer.nextToken()) - 8);
int endY = stringTokenizer.nextToken().charAt(0) - 'A';
int endX = Math.abs(Integer.parseInt(stringTokenizer.nextToken()) - 8);
// 좌표의 값이 다르면 이동할 수 없다.
if (map[startX][startY] != map[endX][endY]) {
stringBuilder.append("Impossible\n");
continue;
}
// 좌표의 값이 일치하면 이동을 안해도 된다.
if (startX == endX && startY == endY) {
stringBuilder.append("0 " + (char)(startY + 'A') + " " + (8 - startX) + "\n");
continue;
}
// 체스말이 움직인 경로 체크
boolean[][] visited = new boolean[8][8];
// 체스말이 움직이기 위한 포인트
Queue<int[]> queue = new LinkedList<>();
// 비숍은 체스판의 모든 장소를 2번이면 갈 수 있기 때문에 시작 위치와 도착 위치에서만 움직이면 동선이 파악가능하다.
queue.offer(new int[]{startX, startY});
queue.offer(new int[]{endX, endY});
// 한번에 움직여서 갈 수 있는 장소인지 확인
boolean first = true;
while (!queue.isEmpty()) {
int[] point = queue.poll();
int x = point[0];
int y = point[1];
// 반환점 좌표를 확인하기 위한 변수
int checkX = 0;
int checkY = 0;
// 움직이기전 좌표 표시
visited[x][y] = true;
// 대각선 4방향 움직임
for (int j = 0; j < 4; j++) {
int nextX = x;
int nextY = y;
// 체스판 끝까지 전부 움직여 본다.
while (true) {
nextX += dx[j];
nextY += dy[j];
if (nextX >= 0 && nextY >= 0 && nextX < 8 && nextY < 8) {
// 움직일 때마다 경로 좌표 표시
if (!visited[nextX][nextY]) {
visited[nextX][nextY] = true;
} else { // 도착 지점에서 움직였을 경우, 교차지점 반환점이다.
checkX = nextX;
checkY = nextY;
break;
}
continue;
}
break;
}
}
// 도착 지점이 움직인 경로로 확인됐을때,
if (visited[endX][endY]) {
// 한번에 왔는지, 두번째에 왔는지에 따라 결과 출력한다.
// 한번에 도착지점에 왔을 경우, 도착 지점에서 움직이지 않도록 바로 종료한다.
if (first) {
stringBuilder.append("1 " + (char)(startY + 'A') + " " + (8 - startX));
stringBuilder.append(" " + (char)(endY + 'A') + " " + (8 - endX) + "\n");
break;
} else {
stringBuilder.append("2 " + (char)(startY + 'A') + " " + (8 - startX));
stringBuilder.append(" " + (char)(checkY + 'A') + " " + (8 - checkX));
stringBuilder.append(" " + (char)(endY + 'A') + " " + (8 - endX) + "\n");
}
}
// 시작 위치에서 출력이 안되면 도착 위치 순서일때 출력을 해야한다.
first = false;
}
}
System.out.println(stringBuilder);
}
}
체스판을 만들어서 좌표를 이용해서 값을 비교하는 부분이 많을 거라 생각을 하고 체스판을 배열로 만들어서 사용을 했는데, 생각보다 사용하는 부분은 이동할 수 없을 경우에만 비교를 해서 체스판을 안 만들고 입력값을 이용해서 따로 조건을 만들어서 사용해도 상관없을 듯하다.
교차되는 지점을 찾기 위해 여러 가지 방법을 생각을 해봤는데, 처음에는 먼저 대각선으로 이동을 하고 해당 대각선에서 한 번 더 꺾어서 이동을 했을 때 위치를 이용해서 구하려고 했는데, 이런 방법을 이용하게 되면 대각선으로 이동하는 순서에 따라 해당 위치로 가지 못하게 될 수가 있어 시작점과 도착점에서 이동을 해 교차지점을 찾기로 하였다.
알고리즘 분류
- 구현
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
문제 출처 - https://www.acmicpc.net/problem/9204
9204번: 체스
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 시작 위치 X와 도착 위치 Y가 주어진다. 각 위치는 두 글자가 공백으로 구분되어져 있다. 글자는 열,
www.acmicpc.net