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

 

 

 

문제 출저

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

17837번: 새로운 게임 2

 

 

 

 

문제 풀이

n * n 크기의 체스판이 주어집니다. k 개의 기물이 주어집니다. 기물은 행과 열 방향 정보가 주어집니다.

방향은 오른쪽, 왼쪽, 위쪽, 아래쪽 4방향 입니다. 

 

체스판 기물들은 방향대로 움직입니다. 이 때, 기물들을 만나면 기물이 위로 올라타게 됩니다. 아래에 기물이 움직이면 그 기물 위에 있는 기물들도 같이 움직입니다. 

 

체스판에는 흰색, 빨강, 파랑이 각각 숫자 0, 1, 2으로 주어집니다.

흰색은 아무런 능력이 없습니다.

빨강은 기물의 순서를 뒤집은 다음 쌓이게 합니다. 즉 A,B,C 가 있는 지점에 D,E,F,G 기물이 오는 경우  D, E, F, G 기물의 순서가 G, F, E, D로 뒤집힌 다음 쌓여 A, B, C, G, F, E, D 로 쌓이게 됩니다. 

파랑은 방향을 정반대로 바꿉니다. 만약 다음에 이동할 칸이 파란색이면 방향을 바꾼 다음 한 칸 이동합니다. 만약 (1,1)이 오른쪽으로 이동해서 (1,2)로 이동하려는데 (1,2)칸이 파란색이면 오른쪽이던 기존 방향을 정반대로 돌려 왼쪽으로 바꾼 다음 한 칸 이동하여 (1, 0)이 되게 합니다. 만약 (1, 0)도 파란색이거나 벽이면 (1, 1)에 가만히 있습니다. 가만히 있어도 방향은 정반대로 바껴있습니다.

벽을 만났을 때는 파랑과 완전히 똑같은 메커니즘으로 움직입니다. 

 

체스판의 기물들은 1000번 이동할 수 있습니다. 그 동안 기물이 4개 이상 쌓였을 때 몇 번 이동했는지를 구해야 합니다. 만약 1000번 내에 4개를 쌓을 수 없는 경우 -1을 출력합니다. 

 

 

구현식으로 문제를 풀었습니다. 

int[][] board로 체스판의 상태를 저장합니다. (0 : 흰색, 1 : 빨강, 2 : 파랑)

class Piece를 만들어 데이터와 메소드를 정의했습니다.

int y, int x, int dir : 행과 열, 방향 정보 저장

changeLocation() : 위치 업데이트 

changeDir() : 방향을 정반대로 바꿈

move() : 방향으로 이동. 파란칸을 만났을 때 까지 고려, 이동한 다음 현재 위치를 반환

moveCheck() : 이동할 수 있는지 확인. 벽과 파란칸을 만나면 false 반환, 그 외에는 true 반환 

 

Map<Integer, Piece> pieces : 입력 받은 순서대로 저장하여 Integer를 id 형식으로 Piece를 내용으로 저장했습니다.

List<Integer>[][] status : 체스판 현재 위치에 기물들의 쌓인 정보를 저장하는 2차원의 리스트 배열입니다. 

 

 

pieces의 안에 기물들을 이동시킵니다.

status : 이동 결과를 status에 저장하고 한 기물씩 이동할 떄마다 status의 해당 지점이 4개 이상인지 체크합니다. 4개 이상이면 true, 아니면 false를 리턴합니다.

이 동작을 1000번 반복합니다. 4개 이상이어서 true를 반환하면 반복문을 멈추고 현재 count를 출력합니다.

만약 멈춰지지 않으면 -1을 출력합니다. 

 

내가 해맨 부분

1000번 반복 누락 : 디버깅을 하면서 1000번을 테스트코드 정답에 맞게 4번, 7번으로 수정했다. 이 상태 그대로 제출하면 4%에서 오답이 발생한다. 

파란칸으로 이동해서 반대로 이동했는데 빨간칸인 경우 : 이 때는 발간칸에 규칙에 따라 뒤집어야 합니다. 하지만 파란칸, 벽을 두 번으로 만나 가만히 있어야 하는 경우 빨간칸이어도 뒤집는 효과는 발생하지 않습니다. 

 

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
새로운 게임2
https://www.acmicpc.net/problem/17837

흰색(0) : 이동, 이미 말이 있는 경우 그 말 맨 위에 쌓인다.
빨강(1) : 출발한 말에 순서가 반대로 된다.
파랑(2) : 이동 방향 반대로 하고 한 칸 이동. 또 파란색이면 이동하지 않고 가만히 있는다.
체스판을 벗어나면 파란색과 같은 경우다.

4개 이상 쌓이면 종료
1000번 이상 했을 때 안 쌓이면 종료 -1


현재 칸이 빨간색이고 이동한 뒤의 위치도 현재 칸과 같은데 말의 순서를 뒤집어버리는 경우 (뒤집으면 안된다.)

4%에서 계속 틀린 이유 1000번 실행하도록 해야하는데 디버그 한다고 2, 7 이런 식으로 바꿔서 4%에서 틀렸다.
후...


 */
public class Main {

  static int n;
  static int k;
  static int[][] board;
  static int[] dx = {1,-1,0,0};
  static int[] dy = {0,0,-1,1};

  // 기물 상태 저장
  static Map<Integer, Piece> pieces = new HashMap<>();

  // 현재 상태 저장
  static List<Integer>[][] status;


  static int answer;


  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());

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

    status = new List[n][n];
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        status[i][j] = new ArrayList<>();
      }
    }

    for(int i = 1; i <= k; i++) {
      st = new StringTokenizer(br.readLine());
      int y = Integer.parseInt(st.nextToken()) - 1;
      int x = Integer.parseInt(st.nextToken()) - 1;
      int dir = Integer.parseInt(st.nextToken()) - 1;
      Piece piece = new Piece(y, x, dir);

      pieces.put(i, piece);
      status[y][x].add(i);
    }

    int count = 0;
    answer = -1;

    while(count <= 1000) {
      count++;
      if(move()) {
        answer = count;
        break;
      }
    }

    System.out.println(answer);

  }



  // 기물 이동
  public static boolean move() {
    for(int i = 1; i <= k; i++) {

      Piece piece = pieces.get(i);
      int nowy = piece.y;
      int nowx = piece.x;


      // 남을 것
      List<Integer> remainPieces = new ArrayList<>();

      // 같이 떠날 것
      List<Integer> withPieces = new ArrayList<>();

      // 현재 상태
      List<Integer> now = status[piece.y][piece.x];

      // 위에 있는 말 확인
      boolean start = false;
      for(int j = 0; j < now.size(); j++) {
        if(now.get(j) == i) start = true;

        if(start) withPieces.add(now.get(j));
        else remainPieces.add(now.get(j));
      }

      // 남는 거 적용
      status[piece.y][piece.x] = remainPieces;

      // 기물 이동
      Dot d = piece.move();

      // 빨간색 : 순서 역전 (파랑색 혹은 벽을 만나 같은 위치로 돌아오면 바뀌면 안된다.)
      boolean sameLocation = false;
      if(nowy == piece.y && nowx == piece.x) sameLocation = true;

      if(!sameLocation && board[d.y][d.x] == 1) {
        withPieces = reversePiece(withPieces);
      }

      // 같이 온 기물들도 위치 변경
      // 이동한 곳에 적용
      for(int id : withPieces) {
        pieces.get(id).changeLocation(d);
        status[d.y][d.x].add(id);
      }

      if(status[d.y][d.x].size() >= 4) {
        return true;
      }

    }
    return false;
  }

  // 순서 역전
  public static List<Integer> reversePiece(List<Integer> withPieces) {
    List<Integer> newWithPieces = new ArrayList<>();
    for(int i = withPieces.size() - 1; i >= 0; i--) {
      newWithPieces.add(withPieces.get(i));
    }
    return newWithPieces;
  }


  // 체스판 클래스
  public static class Piece {
    int y;
    int x;
    int dir;

    Piece(int y, int x, int dir) {
      this.y = y;
      this.x = x;
      this.dir = dir;
    }

    // 위치 변경
    public void changeLocation(Dot d) {
      y = d.y;
      x = d.x;
    }

    // 방향을 반대로 바꿈
    public void changeDir() {
      if(dir == 0) dir = 1;
      else if(dir == 1) dir = 0;
      else if(dir == 2) dir = 3;
      else if(dir == 3) dir = 2;
    }

    // 체스 기물 이동
    public Dot move() {
      int ny = y + dy[dir];
      int nx = x + dx[dir];
      // 흰색, 빨강이면 이동
      if(moveCheck(ny,nx)) {
        y = ny;
        x = nx;
      }
      // 파랑 혹 벽 : 반대 방향으로 한 칸 이동한다.
      else {
        changeDir();
        ny = y + dy[dir];
        nx = x + dx[dir];

        if (moveCheck(ny, nx)) {
          y = ny;
          x = nx;
        }
      }
      return new Dot(y,x);
    }

    // 이동 가능한지 확인
    public boolean moveCheck(int y, int x) {
      if(y >= 0 && y < n && x >= 0 && x < n && board[y][x] != 2) {
        return true;
      }
      return false;
    }

    public void print() {
      System.out.println(y + " " + x + " " + dir);
    }

  }

  // y,x 좌표를 표현할 클래스
  public static class Dot {
    int y;
    int x;

    Dot(int y, int x) {
      this.y = y;
      this.x = x;
    }
  }


  // status print 함수
  public static void printStatus() {
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        List<Integer> status1 = status[i][j];
        if(status1.size() == 0) System.out.print(0 + " ");
        for(int number : status1) {
          System.out.print(number + " ");
        }
      }
      System.out.println();
    }
    System.out.println();
  }



}