[BOJ] 17837 새로운 게임 2 (Java)

1. 문제 링크

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

17837번: 새로운 게임 2

 

2. 접근법

1. 변수 선언

  - Piece[] pieces: 말들의 정보 저장

  - int[][] color: 보드 색상 저장

  - ArrayList<Integer>[][] board: 보드 위 말들의 idx 저장

 

2. 1번부터 k번 말까지 각 말의 방향에 따라 이동할 위치를 찾고 해당 위치의 color[][] 값에 따라 움직이기

  2.1. 이동 시, 말들을 쌓을 때 ArrayList<Integer> tempPieces에 현위치의 모든 말들의 정보를 담아둠

  2.2. tempPieces에 있는 말들을 이동할 위치로 이동시킴. 이때 target 말부터 움직여야 하기에 flag 변수를 사용함

  2.3. 이동할 위치가 빨간색 칸인 경우, 역순으로 움직여야 하기에 tempPieces를 역순으로 탐색

 

3. 답 구하기

  3.1. board[][]에 추가할 때, board[][]의 사이즈가 4 이상이면 답을 출력하고 바로 종료하도록 함

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 새로운 게임 2

public class BJ17837 {

    private static class Piece {
        int x;
        int y;
        int dir;

        Piece(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }
    static int n, k;
    static int ans;
    static Piece[] pieces;
    static int[][] color;
    static ArrayList<Integer>[][] board;
    static int[] dx = {0, 0, 0, -1, 1};
    static int[] dy = {0, 1, -1, 0, 0};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        color = new int[n + 1][n + 1];
        board = new ArrayList[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                board[i][j] = new ArrayList<>();
            }
        }
        pieces = new Piece[k];

        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++) {
                color[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int dir = Integer.parseInt(st.nextToken());
            
            board[x][y].add(i);
            pieces[i] = new Piece(x, y, dir);
        }

        solution();
        System.out.println(ans);
    }

    private static void solution() {

        while(true) {
            ans++;
            if(ans > 1000) {
                ans = -1;
                break;
            }

            // 1번부터 k번 말까지 이동시킴
            for(int i = 0; i < k; i++) {
                Piece target = pieces[i];
                int xx = target.x + dx[target.dir];
                int yy = target.y + dy[target.dir];
                
                if(xx < 1 || xx > n || yy < 1 || yy > n || color[xx][yy] == 2) {      // 파란색으로 이동하는 경우
                    moveToBlue(i);
                }
                else if(color[xx][yy] == 0) {                                         // 흰색으로 이동하는 경우
                    moveToWhite(i);
                }
                else {                                                                // 빨간색으로 이동하는 경우
                    moveToRed(i);
                }
            }
        }
    }

    private static void moveToBlue(int idx) {

        // 이동 방향을 반대로 바꾸기
        int currentDir = pieces[idx].dir;
        pieces[idx].dir = currentDir % 2 == 0 ? currentDir - 1 : currentDir + 1;

        Piece bottom = pieces[idx];
        // 방향을 반대로 바꾼 후 이동하려는 칸
        int xx = bottom.x + dx[bottom.dir];
        int yy = bottom.y + dy[bottom.dir];
        
        if(xx < 1 || xx > n || yy < 1 || yy > n || color[xx][yy] == 2) return;      // 해당 칸이 체스판을 벗어나거나 파란색인 경우, 가만히 있음
        else if(color[xx][yy] == 0) moveToWhite(idx);                               // 해당 칸이 흰색인 경우
        else if(color[xx][yy] == 1) moveToRed(idx);                                 // 해당 칸이 빨간색인 경우
    }

    private static void moveToWhite(int idx) {

        Piece bottom = pieces[idx];
        int xx = bottom.x + dx[bottom.dir];
        int yy = bottom.y + dy[bottom.dir];

        boolean flag = false;
        ArrayList<Integer> tempPieces = new ArrayList<>();
        for(int i = 0; i < board[bottom.x][bottom.y].size(); i++) {
            tempPieces.add(board[bottom.x][bottom.y].get(i));
        }
        
        // bottom과 bottom 위에 있는 모든 말들에 대하여
        for(int i = 0; i < tempPieces.size(); i++) {

            int targetIdx = tempPieces.get(i);

            if(targetIdx == idx) {
                flag = true;
                for(int j = tempPieces.size() - 1; j >= i; j--) {
                    board[bottom.x][bottom.y].remove(j);
                }
            }
            if(!flag) continue;
            
            // board[][]에 반영
            board[xx][yy].add(targetIdx);

            // 게임 종료 조건
            if(board[xx][yy].size() >= 4) {
                System.out.println(ans);
                System.exit(0);
            }

            // pieces[]에 반영
            pieces[targetIdx] = new Piece(xx, yy, pieces[targetIdx].dir);
        }
    }

    private static void moveToRed(int idx) {

        Piece bottom = pieces[idx];
        
        int xx = bottom.x + dx[bottom.dir];
        int yy = bottom.y + dy[bottom.dir];

        ArrayList<Integer> tempPieces = new ArrayList<>();
        for(int i = 0; i < board[bottom.x][bottom.y].size(); i++) {
            tempPieces.add(board[bottom.x][bottom.y].get(i));
        }

        // bottom과 bottom 위에 있는 모든 말들에 대하여
        for(int i = tempPieces.size() - 1; i >= 0; i--) {

            int targetIdx = tempPieces.get(i);

            // board[][]에 반영
            board[xx][yy].add(targetIdx);
            board[bottom.x][bottom.y].remove(i);
            // 게임 종료 조건
            if(board[xx][yy].size() >= 4) {
                System.out.println(ans);
                System.exit(0);
            }

            // pieces[]에 반영
            pieces[targetIdx] = new Piece(xx, yy, pieces[targetIdx].dir);
            
            if(targetIdx == idx) break;
        }
    }
}

 

4. 막힌 부분

처음에는 2.1.처럼 배열을 복사할 생각을 못했다.

remove()하면 리스트이기에 idx가 하나씩 당겨질텐데 바보 같이 특정 idx의 값을 계속 찾고 있었다 ㅋㅋ

그래서 tempPieces에 복사했는데, 얕은 복사를 해버려서;;;; 또 해맸다 ㅠㅠ

정말 바보 같은 소영이...

 

최근 푼 삼성 기출 구현 문제는 거의 두 시간 걸린다 ㅠ

생각한 로직대로 구현은 1시간이면 하는데 오류 잡는 데만 또 1시간 걸림.. 

계속 풀다보면 시간을 줄일 수 있겠지.. 아자잣