백준 킹 - 1063번

1.  문제

8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 행을 상징한다. 열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고, 행은 가장 아래가 1이고 가장 위가 8이다. 예를 들어, 왼쪽 아래 코너는 A1이고, 그 오른쪽 칸은 B1이다.

킹은 다음과 같이 움직일 수 있다.

• R : 한 칸 오른쪽으로
• L : 한 칸 왼쪽으로
• B : 한 칸 아래로
• T : 한 칸 위로
• RT : 오른쪽 위 대각선으로
• LT : 왼쪽 위 대각선으로
• RB : 오른쪽 아래 대각선으로
• LB : 왼쪽 아래 대각선으로

체스판에는 돌이 하나 있는데, 돌과 같은 곳으로 이동할 때는, 돌을 킹이 움직인 방향과 같은 방향으로 한 칸 이동시킨다.

 

 

입력

 

첫째 줄에 킹의 위치, 돌의 위치, 움직이는 횟수 N이 주어진다. 둘째 줄부터 N개의 줄에는 킹이 어떻게 움직여야 하는지 주어진다. N은 50보다 작거나 같은 자연수이고, 움직이는 정보는 위에 쓰여 있는 8가지 중 하나이다.

출력

첫째 줄에 킹의 마지막 위치, 둘째 줄에 돌의 마지막 위치를 출력한다.

 

 

 

2. 코드

 

package 백준.구현;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class 킹 {
    //열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고,
    // 행은 가장 아래가 1이고 가장 위가 8이다. 예를 들어, 왼쪽 아래 코너는 A1이고, 그 오른쪽 칸은 B1이다.


    static Map<String, int[]> directionMap = new HashMap<>();

    static {
        directionMap.put("R", new int[]{0, 1});
        directionMap.put("L", new int[]{0, -1});
        directionMap.put("B", new int[]{-1, 0});
        directionMap.put("T", new int[]{1, 0});
        directionMap.put("RT", new int[]{1, 1});
        directionMap.put("LT", new int[]{1, -1});
        directionMap.put("RB", new int[]{-1, 1});
        directionMap.put("LB", new int[]{-1, -1});
    }

    //1. a를 행으로치환, 숫자를 열로
    //2.  생각할 것 돌이 있는데 돌로 움직이게 될 경우 온 방향대로 같이 밀어냄
    //3. 돌이나 내가 체스판 밖으로 나갈 경우 그 움직임은 끝나고 담 움직임 하면 됨


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String position = st.nextToken();
        String stone = st.nextToken();
        int number = Integer.parseInt(st.nextToken());

        int chess[][] = new int[10][10];

        //1. a를 행으로치환, 숫자를 열로

        int pCol = position.charAt(0) - 'A' + 1; //열
        int pRow = position.charAt(1) - '0'; // 행


        int sCol = stone.charAt(0) - 'A' + 1;
        int sRow = stone.charAt(1) - '0';




        chess[pRow][pCol] = 2; // 내 위치
        chess[sRow][sCol] = 3; // 돌 위치

        for (int i = 0; i < 10; i++) {
            chess[0][i] = 1;
            chess[i][0] = 1;
            chess[9][i] = 1;
            chess[i][9] = 1;

        }
        int now = 0;
        while (now < number) {
            String movement = br.readLine();

            int[] dir = directionMap.get(movement);
            int addRow = dir[0];
            int addCol = dir[1];

            if (chess[pRow +addRow][pCol + addCol] == 0) {

                chess[pRow][pCol] = 0;
                chess[pRow + addRow][pCol + addCol] = 2;
                pRow = pRow + addRow;
                pCol = pCol + addCol;

            } else if (chess[pRow + addRow][pCol + addCol] == 3 &&
                    chess[sRow + addRow][sCol + addCol] == 0) {


                chess[sRow + addRow][sCol + addCol] = 3;
                sRow += addRow;
                sCol += addCol;

                chess[pRow + addRow][pCol + addCol] = 2;
                chess[pRow][pCol] = 0;
                pRow += addRow;
                pCol += addCol;

            }

            now++;
        }
       
        StringBuilder sb = new StringBuilder();


        sb.append((char) (pCol + 'A' - 1)).append(pRow).append("\n");
        sb.append((char) (sCol + 'A' - 1)).append(sRow);
        System.out.println(sb);



//        System.out.println("pRow = " + pRow);
//        System.out.println("pCol = " + pCol);
//        System.out.println(sRow);
//        System.out.println(sCol);




        }

    }

 

 

 

 

3. 풀이

 

 

 

3-1. 체스판 뒤집기

 

 

먼저 체스판의 시작의 경우 좌측 하단부터 시작하지만, 내가 편한 건 배열처럼 좌측 상단부터 시작하는 것이다.

 

먼저 map으로 각 움직임을 저장해놓고 그 String이 들어온다면 그 좌표를 반환하게 해줬다.

 

 

그래서 보면 B의 경우는 기존 체스판의 경우에는 아래로 움직임 {+1, 0} 이 되어야 한다.\

나는 뒤집어놨기 때문에 위로 움직임을 해줬다 {-1, 0}

 

즉 위 아래의 움직임만 모두 바꿔줬다.

 

 

3-2. 알파벳을 index로 치환

 

 

 

입력으로 들어오는 값은 king의 위치는 A1, 돌의 위치는 A2이런 식으로 들어오고,

뒤집어 있기에 A는 열이고, 숫자는 행이다.

들어온 열의 값에서 -A를 빼주면 위치에 따라 0, 1, 2 ~ 로 지정할 수 있는데 우리가 원하는 수는 1이니 +1

 

 

 

 

 

3-3 경계 값은 더 큰 배열로

 

 

 

king의 위치를 2번, 돌의 위치를 3번으로 지정해줬다.

 

그리고 8X8 배열이지만 나는 10x10 배열로 만들어줬다.

 

왜냐하면 경계를 다 1로 만들어줘서 경계값을 지정하기 위해서다. 배열의 범위를 초과하지 못하게 따로 지정해줘야하는데,

그 경우를 줄이기 위함

 

실제로 경계를 다 1로 만들어준 모습

 

 

 

3-4 실제 로직

 

 

 

자 우리가 그럼 움직일 수 있는 자리는 2개이다.

 

1. king이 다음 위치로 움직였을 때 경계가 아닌 자리 즉 1이 없는 위치

2.king이 다음 위치로 움직였을 때 돌이 있고 그 돌은 같은 방향으로 밀어내기에 그 돌도 움직일 수 있는 위치

 

그리고 움직였을 때 움직인 킹의 위치 또는 킹 + 돌 위치를 기록과 원래 있던 곳은 0으로 만들어주기!

 

 

 

 

 

3-5 출력

 

 

마찬가지로 현재 index로 지정되어 있는 걸 아까처럼 다시 A,B,C~로 바꿔주고 출력하면 끝

 

 

 

 

3-6 자꾸 틀린 부분

 

오랜만에 배열을 한 사이즈 더 크게 해서 경계 값을 설정 해줘야겠다고 생각했다.

원래라면 배열을 초과하는 조건을 다 검색했겠지만..

그 결과 처음엔 

 

 

체스 배열을 10,10이 아니라 9,9로 했고 그 결과 ArrayIndexOutOfBounds가 나왔다..

 

내 1로 체크하는 로직 자체가 문제가 없다고 생각해서 이 부분에 논리 오류 검출이 오래 걸렸다ㅠ

 

역시 이 로직 자체는 문제가 없었고 배열을 10,10으로 만들어줘야 내가 원하는 8,8 배열안에서 움직임이 있는걸 

너무 늦게 꺠달았다.. 너무 간단해서 쉽게 생각한 결과ㅠ

 

 

 

4. 더 나은 방법

 

 

사실 배열을 쓸 필요가 없다.

 

while (now < number) {
    String movement = br.readLine();
    int[] dir = directionMap.get(movement);
    int addRow = dir[0];
    int addCol = dir[1];

    int nextPR = pRow + addRow;
    int nextPC = pCol + addCol;

    // 킹이 이동할 위치가 체스판 안에 있는지 확인
    if (nextPR < 1 || nextPR > 8 || nextPC < 1 || nextPC > 8) {
        now++;
        continue;
    }

    // 돌이 있는 경우, 돌도 같이 이동할 수 있는지 확인
    if (nextPR == sRow && nextPC == sCol) {
        int nextSR = sRow + addRow;
        int nextSC = sCol + addCol;

        // 돌이 체스판 안에 있을 때만 이동
        if (nextSR < 1 || nextSR > 8 || nextSC < 1 || nextSC > 8) {
            now++;
            continue;
        }

        // 둘 다 이동
        sRow = nextSR;
        sCol = nextSC;
    }

    // 킹 이동
    pRow = nextPR;
    pCol = nextPC;

    now++;
}

 

 

이런 식으로 그냥 숫자로 접근해도 된다.

 

배열을 더 크게 잡을 필요도 없고, 애초에 움직이기 전에 숫자로 넘지 않는 것만 확인해주고,

배열없이 그냥 딱 두개의 숫자로만 확인하고 움직여주면 된다.

 

 

 

 

번외.

 

배열의 범위를 벗어나는 위치를 배열의 크기로 확인하는 것 말고 숫자의 범위로 확인하는 로직을 떠올렸을 때 부터

숫자만 써도 가능할 것 같은 느낌이 들었지만, 일단은 내가 구현한 게 맞는 지 부터 확인하고 싶었다.

 

그 이후 ArrayOutOfBound 가 떴을 때만 해도 논리적으로 틀린 줄 알았지만,,

 

더 효율적인 코드를 짜려고 노력해야겠다.

 

 

 

 

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