[java]새로운 게임 2 - 백준17837

문제



풀이

문제 해석을 하자면,

  • 체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구하라.


풀이

  • 시간초과를 조심해서 단순히 구현을 하면 되는 문제이다.
  • 다만, 생각보다 구현이 까다로웠다.
  • 1~K번말 “순서대로” 이동 을 지키기 위해 horse 배열에 따로 2차원배열 좌표값을 기록해갔다.
  • 그리고 map 배열에 색상을 기록해두고, inArr 배열에 실제 문제의 그림처럼 자료구조를 이어갔다.
  • 마지막으로 “말을 이동”할 때 꼭 해당 말부터 쌓인 말들 통째로 이동하게끔 구현해야한다.



코드

public static int N, K;
public static int result;
public static List<Pair>[][] inArr = new ArrayList[15][15];
public static int[][] map = new int[15][15];
public static Pair[] horse = new Pair[12];
public static int[] dx = {0, 0, -1, 1};
public static int[] dy = {1, -1, 0, 0};
public static int[] redir = {1, 0, 3, 2}; // 반대방향


public static void moveWhite(int nx, int ny, int idx) {
    // 통째로 옮기는 작업
    Pair p = horse[idx];

    int findIdx = 0; // 말이 쌓여있을때 몇번째에 있는지 찾기 (num:순번)
    int cx = p.x; int cy = p.y; // p.x, p.y 는 주소값으로 변경될 수 있어서 따로 복제해서 사용 (중요)
    int size = inArr[cx][cy].size();
    for(int i=0; i<size; i++) {
        if(inArr[cx][cy].get(i).num == p.num) {
            findIdx = i; break;
        }
    }
    for(int i=findIdx; i<size; i++) { // findIdx부터 통째로 이동
        horse[inArr[cx][cy].get(i).num].x = nx; //update 좌표
        horse[inArr[cx][cy].get(i).num].y = ny;
        inArr[nx][ny].add(inArr[cx][cy].get(i)); //add
        inArr[cx][cy].remove(i); //delete
        i--; //원복 -> 다음 배열인덱스 접근 위해 필수!
        size--;
    }

    //debug
    //		for(int i=0; i<N; i++) {
    //			System.out.println(Arrays.toString(inArr[i]));	
    //		}
    //		System.out.println("moveWhite");
}

public static void moveRed(int nx, int ny, int idx) {
    // 통째로 옮기는 작업
    Pair p = horse[idx];

    int findIdx = 0; // 말이 쌓여있을때 몇번째에 있는지 찾기 (num:순번)
    int cx = p.x; int cy = p.y; // p.x, p.y 는 주소값으로 변경될 수 있어서 따로 복제해서 사용 (중요)
    int size = inArr[cx][cy].size();
    for(int i=0; i<size; i++) {
        if(inArr[cx][cy].get(i).num == p.num) {
            findIdx = i; break;
        }
    }
    for(int i=size-1; i>=findIdx; i--) { // 뒤쪽부터 넣음으로써 순서 반대 효과
        horse[inArr[cx][cy].get(i).num].x = nx; //update 좌표
        horse[inArr[cx][cy].get(i).num].y = ny;
        inArr[nx][ny].add(inArr[cx][cy].get(i)); //add
        inArr[cx][cy].remove(i); //delete
        //뒤부터 삭제하므로 원복작업이 필요없음
    }

    //debug
    //		for(int i=0; i<N; i++) {
    //			System.out.println(Arrays.toString(inArr[i]));	
    //		}
    //		System.out.println("moveRed");
}


public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    K = Integer.parseInt(stk.nextToken());
    for(int i=0; i<N; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++) {
            map[i][j] = Integer.parseInt(stk.nextToken());
            inArr[i][j] = new ArrayList<>(); //init
        }
    }
    for(int i=0; i<K; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int x = Integer.parseInt(stk.nextToken())-1;
        int y = Integer.parseInt(stk.nextToken())-1;
        int dir = Integer.parseInt(stk.nextToken())-1;
        horse[i] = new Pair(x,y,dir, i); //초기엔 동일좌표 없음
        inArr[x][y].add(new Pair(x,y,dir,i));
    }
    //run
    boolean success = false;
    while(true) {
        if(success) break;
        if(result > 1000) {
            result = -1;
            break;
        }
        for(int i=0; i<K; i++) { // 1~K번말 "순서대로" 이동
            Pair p = horse[i]; // 좌표찾기
            int nx = p.x+dx[p.dir];
            int ny = p.y+dy[p.dir];
            // 범위체크 먼저 + 파란색
            if(nx<0||ny<0||nx>=N||ny>=N || map[nx][ny] == 2) {
                // 이동방향 반대 기록 후 "파란색 아니면" 이동까지 
                p.dir = redir[p.dir];
                nx = p.x+dx[p.dir];
                ny = p.y+dy[p.dir];
                for(Pair h : inArr[p.x][p.y]) {
                    if(h.num == p.num) // 현재 말만 선택 (여기선 나머지 쌓인말은 그대로) 
                        h.dir = p.dir; // 방향 기록 -> 디버깅 잘 보기 위해 추가
                }
                //debug
                //					for(int j=0; j<N; j++) {
                //						System.out.println(Arrays.toString(inArr[j]));	
                //					}
                //					System.out.println("moveBlue");

                if(nx<0||ny<0||nx>=N||ny>=N || map[nx][ny] == 2) continue;
                else {
                    // "빨간, 하얀" 로직 재사용
                    if(map[nx][ny]==0) moveWhite(nx,ny,i);
                    else if(map[nx][ny]==1) moveRed(nx,ny,i);
                }
            }
            // 하얀색 
            else if(map[nx][ny] == 0) {
                moveWhite(nx,ny,i); // 순번도 넘겨주자

            }
            // 빨간색
            else if(map[nx][ny] == 1) {
                moveRed(nx,ny,i);
            }

            if(inArr[nx][ny].size() >=4) {
                success = true;
                break;
            }
        }	
        result++;
        //debug
        //			System.out.println(result+" 턴 종료");
    }

    //output
    System.out.println(result);
}

static class Pair {
    int x; int y; int dir; int num;
    public Pair (int x, int y, int dir, int num) {
        this.x=x; this.y=y; this.dir=dir; this.num = num;
    }
    @Override
    public String toString() {
        //			return "Pair [x=" + x + ", y=" + y + ", dir=" + dir + ", num=" + num + "]";
        return "Pair [dir=" + dir + ", num=" + num + "]";
    }


}



느낀점

생략

댓글남기기

참고