[BOJ] 17837 새로운게임2 - Java

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

17837번: 새로운 게임 2

[풀이]

다음과 같은 조건을 주의해야 한다.

• 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
• 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

원래 있는 칸(A)

이동하려는 칸(B)이 

1. 흰색인 경우 -> 이동하려고 한 칸(B)에 그대로 이동, Arr뒤에 붙인다.

2. 빨간색인 경우 -> 이동하려고 한 칸(B)에 그대로 이동, Reverse한 뒤 붙인다.

3. 파란색 or 범위를 벗어나는 경우 -> 방향을 바꾸고 새로 이동하려는 칸을 구한다.(C)

    3-1. 새로 이동하려는 칸(C)이 파란색 or 범위를 벗어나는 경우 -> 이동하지 않고 원래 있던 칸(A)에 있는다. (빨간색이어도 뒤집지 않음)

    3-2. 새로 이동하려는 칸(C)이 파란색 or 범위를 벗어나지 않는 경우 -> 흰색이면 C로 이동, 빨간색이면 뒤집고 C로 이동

 

- 4개가 되자마자 종료해야 하므로, 말이 이동할 때마다 4개를 넘는지 체크해준다.

- 각 맵에 저장되어 있는 말들을 ArrayList<Integer> [][] 로 관리한다. (말의 번호가 순서대로 적혀져있음)

- 각 말의 방향과, 행,열을 HashMap형태로 관리한다. (말의 위치가 매번 바뀌기 때문에 말의 번호로 꺼내올 수 있게끔 함)

- 내 위 말 모두 다같이 이동은 subList를 통해 구현했다.

Map[now.row][now.col] = new ArrayList<>(nowArr.subList(0, index));
ArrayList<Integer> nextArr = new ArrayList<>(nowArr.subList(index, nowArr.size()));

 

[코드]

import java.util.*;
import java.io.*;

public class Main {
   static StringTokenizer st;
   static int N, K;
   static int[][] Color;
   static ArrayList<Integer>[][] Map;
   static int[] dRow = { 0, 0, 0, -1, 1 };
   static int[] dCol = { 0, 1, -1, 0, 0 };
   static HashMap<Integer, Integer> HorseDir = new HashMap<>();
   static HashMap<Integer, Point> HorseArr = new HashMap<>();

   public static void main(String[] args) throws Exception {
      // TODO Auto-generated method stub
      //System.setIn(new FileInputStream("src/main/java/input.txt"));
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      K = Integer.parseInt(st.nextToken());
      Color = new int[N + 1][N + 1];
      Map = new ArrayList[N + 1][N + 1];
      for (int i = 1; i < N + 1; i++) {
         for (int j = 1; j < N + 1; j++) {
            Map[i][j] = new ArrayList<>();
         }
      }

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

      for (int i = 1; i < K + 1; i++) {
         st = new StringTokenizer(br.readLine());
         int row = Integer.parseInt(st.nextToken());
         int col = Integer.parseInt(st.nextToken());
         int dir = Integer.parseInt(st.nextToken());
         Map[row][col].add(i);
         HorseDir.put(i, dir);
         HorseArr.put(i, new Point(row, col, i, dir));
      }

      // START
      int answer = 0;
      while (true) {
         answer++;
         if (answer > 1000) {
            System.out.println(-1);
            System.exit(0);
         }

         for (int i = 1; i < HorseArr.size() + 1; i++) {
            Point now = HorseArr.get(i);
            ArrayList<Integer> nowArr = Map[now.row][now.col];
            int index = 0;
            for (int k = 0; k < nowArr.size(); k++) {
               if (nowArr.get(k) == now.num) {
                  index = k;
                  break;
               }
            }

            Map[now.row][now.col] = new ArrayList<>(nowArr.subList(0, index));
            ArrayList<Integer> nextArr = new ArrayList<>(nowArr.subList(index, nowArr.size()));
            int newRow = now.row + dRow[now.dir];
            int newCol = now.col + dCol[now.dir];
            if (!(0 < newRow && newRow <= N && 0 < newCol && newCol <= N) || Color[newRow][newCol] == 2) { //파란색 혹은 벽
               int rDir = reverseDir(now.dir);
               HorseDir.put(now.num, rDir);

               int rNewRow = now.row + dRow[rDir];
               int rNewCol = now.col + dCol[rDir];
               if (!(0 < rNewRow && rNewRow <= N && 0 < rNewCol && rNewCol <= N) || Color[rNewRow][rNewCol] == 2) {// 또 파란색 혹은 벽이면 now에다가 놓기
                  Map[now.row][now.col].addAll(nextArr);
                  for (int k = 0; k < nextArr.size(); k++) {
                     HorseArr.put(nextArr.get(k),
                           new Point(now.row, now.col, nextArr.get(k), HorseDir.get(nextArr.get(k))));
                  }
               } else {// 파란색 혹은 벽 아니면 다음칸으로 이동
                  if (Color[rNewRow][rNewCol] == 1) { // 왔는데 거기가 빨간색이면 뒤집기
                     Collections.reverse(nextArr);
                  }
                  Map[rNewRow][rNewCol].addAll(nextArr);
                  for (int k = 0; k < nextArr.size(); k++) {
                     HorseArr.put(nextArr.get(k),
                           new Point(rNewRow, rNewCol, nextArr.get(k), HorseDir.get(nextArr.get(k))));
                  }
               }
            }
            else if (0 < newRow && newRow <= N && 0 < newCol && newCol <= N) {
               if (Color[newRow][newCol] == 1) { // 빨간색
                  Collections.reverse(nextArr);
               }
               Map[newRow][newCol].addAll(nextArr);
               for (int k = 0; k < nextArr.size(); k++) {
                  HorseArr.put(nextArr.get(k),
                        new Point(newRow, newCol, nextArr.get(k), HorseDir.get(nextArr.get(k))));
               }
            }
            for (int a = 1; a < N + 1; a++) {
               for (int b = 1; b < N + 1; b++) {
                  if (Map[a][b].size() >= 4) {
                     System.out.println(answer);
                     System.exit(0);
                  }
               }
            }
         }

         
      }

   }

   static int reverseDir(int dir) {
      switch (dir) {
      case 1:
         return 2;
      case 2:
         return 1;
      case 3:
         return 4;
      case 4:
         return 3;
      }
      return -1;
   }

   static class Point {
      int row;
      int col;
      int num;
      int dir;

      public Point(int row, int col, int num, int dir) {
         super();
         this.row = row;
         this.col = col;
         this.num = num;
         this.dir = dir;
      }

      @Override
      public String toString() {
         return "Point [row=" + row + ", col=" + col + ", num=" + num + ", dir=" + dir + "]";
      }

   }

}

[느낀점]

구현은 날 참 킹받게 한다.

구현 안나오고 dfs 백트래킹 나왔으면 좋겠다.

왜이리 어렵지ㅜㅜ