백준 9204번: 체스(Python/Java)

https://www.acmicpc.net/problem/9204

9204번: 체스

 

 

 

접근

---

우선 알아둬야 할 두 가지 전제조건이 있다. 체스에 관해 잘 모르더라도 문제를 풀다 보면 자연스럽게 눈치챘을 부분이다. 우선 비숍은 본인이 있는 지점의 색상과 같은 지점만 갈 수 있다는 것을 알아둬야 한다. 즉, 현재 비숍이 있는 발판이 검은색이라면 흰색 발판 지점은 어떤 경우의 수를 생각하더라도 절대 도착할 수 없다. 

 

다음으로 알아둘 것은 비숍의 이동 횟수다. 문제 조건에서 '최대 4번 움직일 수 있으며'라고 주어졌지만 사실 4번까지 움직일 일은 절대 없다. 아니, 4번이 아니라 3번도 움직이지 않는다. 체스에서 비숍이 특정 위치에 도착할 때 걸리는 경우의 수는 최대 2번이다. 첫 번째 전제조건에 해당하는 임의의 두 지점을 통해 확인해보자.  여기까지 확인됐다면 우리는 한 번도 움직이지 않을 때부터 두 번 움직일 때까지 확인하면 된다.

 

가장 먼저 한 번도 움직이지 않을 때다. 만약 출발 지점과 도착 지점이 같다면 한 번도 움직일 필요가 없다. 다음으로 한번 움직일 때다. 만약 출발 지점의 대각선 방향에 도착 지점이 있다면 한 번의 움직임으로 원하는 곳에 도착할 수 있다. 마지막 두 번째 경우는 위의 두 상황이 아닌 모든 경우인데, 이때는 출발 지점에서 도착 지점의 대각선 지점으로 이동하고 해당 지점에서 도착 지점으로 이동하는 경우다.

 

대각선 지점을 확인하는 방법은 간단하다. 출발 지점의 x좌표와 도착 지점의 x좌표의 차, 출발 지점의 y좌표와 도착 지점의 y좌표의 차가 같다면 둘은 대각선 지점에 있는 곳이다. 8X8배열이기 때문에 경우의 수가 생각보다 크지 않아 적절히 if문을 준다면 쉽게 확인 가능하다.

 

 

 

풀이

---

Python

upDown = [-1, -1, 1, 1]
leftRight = [-1, 1, -1, 1]

roundNum = int(input())

for i in range(roundNum):
    firstLine = list(map(str, input().split()))
    startWidth, startHeight = (ord(firstLine[0])-64), int(firstLine[1])
    goalWidth, goalHeight = (ord(firstLine[2])-64), int(firstLine[3])

    midRoot = [0, 0]
    resultCheck = False
    for i in range(0, 9):
        for j in range(4):
            if 1 <= (startHeight+(i*upDown[j])) < 9 and 1 <= (startWidth+(i*leftRight[j])) < 9:
                if abs(goalHeight - (startHeight+(i*upDown[j]))) == abs(goalWidth - (startWidth+(i*leftRight[j]))):
                    midRoot = [(startHeight+(i*upDown[j])), (startWidth+(i*leftRight[j]))]
                    resultCheck = True
                    break

        if resultCheck:
            break

    if resultCheck:
        if startWidth == goalWidth and startHeight == goalHeight:
            print(0, chr(startWidth+64), startHeight)
        elif startWidth == midRoot[1] and startHeight == midRoot[0]:
            print(1, chr(startWidth+64), startHeight, chr(goalWidth+64), goalHeight)
        else:
            print(2, chr(startWidth+64), startHeight, chr(midRoot[1]+64), midRoot[0], chr(goalWidth+64), goalHeight)
    else:
        print("Impossible")

 

Java

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        int[] upDown = {-1, -1, 1, 1};
        int[] leftRight = {-1, 1, -1, 1};

        int roundNum = Integer.parseInt(scan.nextLine());

        for(int round = 0 ; round < roundNum ; round++){
            String[] firstLine = (scan.nextLine()).split(" ");
            int startWidth = (firstLine[0].charAt(0)-64), startHeight = Integer.parseInt(firstLine[1]);
            int goalWidth = (firstLine[2].charAt(0)-64), goalHeight = Integer.parseInt(firstLine[3]);

            int[] midRoot = new int[2];
            boolean resultCheck = false;
            loop:
            for(int i = 0 ; i < 9 ; i++){
                for(int j = 0 ; j < 4 ; j++){

                    if((startHeight+(i*upDown[j])) >= 1 && (startHeight+(i*upDown[j])) < 9
                    && (startWidth+(i*leftRight[j])) >= 1 && (startWidth+(i*leftRight[j])) < 9){
                        if(Math.abs(goalHeight - (startHeight+(i*upDown[j]))) == Math.abs(goalWidth - (startWidth+(i*leftRight[j])))){
                            midRoot[0] = (startHeight+(i*upDown[j]));
                            midRoot[1] = (startWidth+(i*leftRight[j]));

                            resultCheck = true;
                            break loop;
                        }
                    }
                }
            }

            if(resultCheck){
                if(startWidth == goalWidth && startHeight == goalHeight){
                    System.out.println("0 " + ((char)(startWidth+64)) + " " + startHeight);
                }else if(startWidth == midRoot[1] && startHeight == midRoot[0]){
                    System.out.println("1 " + ((char)(startWidth+64)) + " " + startHeight + " " + ((char)(goalWidth+64)) + " " + goalHeight);
                }else{
                    System.out.println("2 " + ((char)(startWidth+64)) + " " + startHeight + " " + 
                    ((char)(midRoot[1]+64)) + " " + midRoot[0] + " " + ((char)(goalWidth+64)) + " " + goalHeight);
                }
            }else{
                System.out.println("Impossible");
            }

        }

    }

}

 

 

 

후기

---

너비 우선 탐색 문제라고 설명이 나와있긴 하지만 너비 우선 탐색보다는 그냥 단순 구현 문제라고 볼 수 있었던 문제. 주변 탐색 가능한 구역을 한 번씩 탐색한다는 공통점이 있긴 하지만 이를 너비 우선 탐색이라고 볼 수 있느냐는 또 다른 문제다. 나는 일단 단순 구현으로 생각하고 풀었다.

 

하지만 보드의 크기가 문제 조건이었던 8X8보다 컸다면 단순 구현으로 풀기엔 연산이 너무 많아질 것으로 생각된다. 보다 효율적으로 탐색할 수 있는 방법을 다시 한번 생각해봐야겠다.