[백준 17837: JAVA] 새로운 게임2

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

17837번: 새로운 게임 2

---

[1회차] 10월 31일, 스터디

문제 접근 방법 (사용 자료구조, 알고리즘)

입력
(1) N, K, int map[N][N] : 게임판에 대한 정보, int move[N][N][K+1] : 게임판에 말들의 이동에 대한 정보 저장, Horse horses[K+1] : 말에 대한 정보 저장 
(2) Horse 클래스 : x(세로), y(가로), dir(이동 방향), idx(move 배열에서의 해당 말의 위치 인덱스)

로직
(1) 말의 다음 이동 칸에 대한 정보를 확인한다. -> 0(흰색), 1(빨간색), 2(파란색), 인덱스에 벗어나는 경우
(2) 0, 1의 경우에 대해서는 바로 moveTo 메서드를 호출한다.
(3) 2, 인덱스 벗어나는 경우는 이동방향을 바꿔서 다음칸에 대한 이동정보를 다시 확인한다
  - 다음칸이 0, 1일 경우는 moveTo 메서드 호출한다
  - 다음칸이 2, 인덱스 벗어나는 경우는 아무 조치도 쥐하지 않는다
(4) moveTo 메서드 : 현재 말에 업혀있는 말의 정보(현재 말 포함)를 list에 넣어두고 move칸은 0으로 만든다.
이동할 칸이 빨간색이면 인덱스를 거꾸로 해서 추가하고, 흰 색이면 인덱스를 그대로 해서 추가한다.
(5) moveTo 메서드에서 말이 4개 이상 업히면 isFind 전역변수를 true로 만들어주고 모든 반복문을 종료한다.
(6) 턴의 수(ans)가 1000을 넘어가면 종료한다.

출력
ans가 1000보다 크면 -1, 작으면 ans를 출력한다.

 

 

메모리 & 시간

가장 짧은 수행시간의 2배임 노력하겟음

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, K, map[][], move[][][], ans;
    static boolean isFind;
    static int dir[][] = {{}, {0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    static Horse[] horses;

static class Horse{
    int x, y, dir, idx;
    public Horse(int x, int y, int dir, int idx) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.idx = idx;
    }
}
public static void main(String[] args) throws Exception {
    // 입력
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(in.readLine());

    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    map = new int[N][N];
    move = new int[N][N][K+1];

    for (int i = 0; i < N; i++) {
        st = new StringTokenizer(in.readLine());
        for (int j = 0; j < N; j++) {
            map[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    horses = new Horse[K+1];
    for (int i = 1; i <= K; i++) {
        st = new StringTokenizer(in.readLine());
        int x = Integer.parseInt(st.nextToken()) - 1;
        int y = Integer.parseInt(st.nextToken()) - 1;
        int dir = Integer.parseInt(st.nextToken());
        horses[i] = new Horse(x, y, dir, 0);
        move[x][y][0] = i;
        
    }

    ans = 1;
    game();
    System.out.println(ans > 1000? -1 : ans);
}

private static void game() {
    while(true) {
        for (int i = 1; i < K + 1; i++) {
            Horse h = horses[i];
            
            int dx = h.x + dir[h.dir][0];
            int dy = h.y + dir[h.dir][1];

            // 1. 흰 색 또는 빨간 색일 경우 
            if(inBound(dx, dy) && (map[dx][dy] == 0 || map[dx][dy] == 1)) {
                moveTo(dx, dy, h, map[dx][dy]);
            }
            // 3. 파란색이거나 범위를 넘어갈 경우
            else if(!inBound(dx, dy) || map[dx][dy] == 2) {
                // 방향 바꿈
                if(h.dir == 1 || h.dir == 3) h.dir += 1;
                else h.dir -= 1;

                // 한 칸 이동
                dx = h.x + dir[h.dir][0];
                dy = h.y + dir[h.dir][1];

                if(inBound(dx, dy) && map[dx][dy] != 2) {
                    moveTo(dx, dy, h, map[dx][dy]);
                }
            }
            
            if(isFind) break;
        }
        if(ans > 1000 || isFind) break;
        ans++;
    }

}

private static void moveTo(int x, int y, Horse h, int color) {
    List<Integer> list = new ArrayList<>();

    for (int i = h.idx; i <= K; i++) {
        if(move[h.x][h.y][i] == 0) break;
        list.add(move[h.x][h.y][i]);
        move[h.x][h.y][i] = 0;
    }

    for (int i = 0; i <= K; i++) {
        if(move[x][y][i] == 0) {
            h.idx = i;
            if(color == 0) {
                for (int j = 0; j < list.size(); j++) {
                    move[x][y][i+j] = list.get(j);
                    horses[list.get(j)] = new Horse(x, y, horses[list.get(j)].dir, i + j);
                }
            } else {
                for (int j = list.size()-1, k = 0; j >= 0; j--, k++) {
                    move[x][y][i+k] = list.get(j);
                    horses[list.get(j)] = new Horse(x, y, horses[list.get(j)].dir, i + k);
                }
            }
            if(i + list.size() >= 4) isFind = true;
            break;
        }
    }

    h.x = x;
    h.y = y;
}

private static boolean inBound(int x, int y) {
    if(x >= 0 && y >= 0 && x < N && y < N) return true;
    return false;
}
}

 

 

문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)

문제 해석	문제 접근	코드 구현
15분	20분	1시간 50분

인덱스 때문에 삽질 엄청나게 했지만 오랜 시간이 걸리지는 않았다,