BOJ - 17780 새로운 게임

17780 새로운 게임 : https://www.acmicpc.net/problem/17780

---

Problem

---

Solve

주어진 조건

• N : 체스판 크기 , K : 사용한 말의 개수, 이동방향 : 상,하,좌,우
• 1턴은 1번말 부터 K번 말까지 순서대로 이동한다.
  - 이동하는 말 위에 올라가져있는 말도 함께 이동한다.
  • 가장 아래에 있는 말만 이동이 가능하다.
• 말이 이동한 곳의 색
  • 빨간색 : 말의 순서 reverse 후 올려져있는 말과 함께 이동.
  • 흰색 : 올려져있는 말과 함께 이동.
  • 파란색 : 이동하려는 반대 방향으로 이동, 만약 반대 방향이 파란색이나 범위 밖이라면 현재 위치에서 방향만 변경
  • 범위 밖 : 파란색과 동일.
• 턴 진행 중 4마리 이상의 말이 겹치게 되는 순간 종료.

말의 정보(y,x,번호,방향)를 담는 Unit클래스를 만든 후 List< Unit >[][] unitBoard = new List[N][N] 를 생성한다.
unitBoard배열을 통해 unitBoard[i][j]에 존재하는 말의 리스트를 알수있다.
이때 unitBoard[i][j] 리스트에 첫번째 Unit이 가장 아래있는 말이다.

풀이 순서는 아래와 같다.
1. 풀이에 필요한 변수 및 배열을 초기화한다.
2. turn이 1000이하일때까지 반복한다.

• 1000을 초과하게 되면 -1을 반환한다.

3.1번 말 부터 K번 말까지 이동시킨다.

• 말이 이동할 곳이 파란색이거나 범위 밖이라면 방향을 바꾼다.
  • 바뀐 방향의 좌표를 확인한다.
  • 만약 바뀐 방향의 좌표도 파란색이거나 범위 밖이라면 방향만 바뀐채 다음 말을 이동시킨다.
  • 바뀐 방향의 좌표가 흰색 또는 빨간색이라면 바뀐 방향으로 이동을 진행한다.
• 말이 이동할 곳이 빨간색이나 흰색이라면 현재 좌표의 List< Unit >을 따로 저장해둔다
  • 빨간색이라면 이동할 좌표의 Unit List에 저장해둔 list를 reverse해서 추가한다.
  • 흰색이라면 이동할 좌표의 Unit List에 저장해둔 list를 그대로 추가한다.

4. 말을 하나씩 이동시켰을 때 마다 이동한 좌표의 Unit List의 개수가 4개 이상인지 확인하고 조건을 만족하면 함수를 종료시킨다.

---

Code

public class 새로운게임 {
	static int N;
	static int K;
	static int[][] board;
	static List<Unit>[][] unitBoard;
	static Unit[] units;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		//타일 색  배열
		board = new int[N][N];
        //Unit 저장 배열
		units = new Unit[K + 1];
        //Unit List 배열
		unitBoard = new List[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				unitBoard[i][j] = new ArrayList<>();
			}
		}

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

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			int d = Integer.parseInt(st.nextToken());

			//방향 변경을 위한 방향 변경
            // 0 : ↑, 1 : →, 2 : ↓, 3 : ←
			if (d == 2) {
				d = 3;
			} else if (d == 3) {
				d = 0;
			} else if (d == 4) {
				d = 2;
			}

			Unit unit = new Unit(i + 1, y, x, d);
			unitBoard[y][x].add(unit);
			units[i + 1] = unit;
		}

		int answer = -1;
		for (int turn = 1; turn <= 1000; turn++) {
			if (start()) {
				answer = turn;
				break;
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static boolean start() {
    	//해당 턴에서 1번말 부터 K번 말까지 순서대로 이동
		for (int u = 1; u <= K; u++) {
			Unit current = units[u];

			int currentY = current.y;
			int currentX = current.x;
            //해당 말이 가장 아래에 있지않으면 제외
			if (unitBoard[currentY][currentX].get(0).num != current.num)
				continue;

			int ny = currentY + dy[current.d];
			int nx = currentX + dx[current.d];

			//이동할 좌표가 파란색 또는 범위 밖이라면 방향을 반대로 변경한다.
			if (ny < 0 || nx < 0 || ny >= N || nx >= N || board[ny][nx] == 2) {
				int nd = (current.d + 2) % 4;
				ny = currentY + dy[nd];
				nx = currentX + dx[nd];
				current.d = nd;
	
    			//변경한 방향으로 이동해도 파란색이거나 범위 밖이라면 방향만 바뀐채로 다음 말 이동
                //변경한 방향이 흰색이거나 빨간색이면 다음 코드 실행
				if (ny < 0 || nx < 0 || ny >= N || nx >= N || board[ny][nx] == 2) {
					continue;
				}
			}

			//이동할 좌표가 빨간색
			if (board[ny][nx] == 1) {
				int size = unitBoard[currentY][currentX].size();
                //현재 좌표의 말들을 반대로 이동할 좌표의 list에 추가
				for (int i = size-1; i >= 0; i--) {
					Unit unit = unitBoard[currentY][currentX].get(i);
					unit.y = ny;
					unit.x = nx;
					unitBoard[ny][nx].add(unit);
				}
				unitBoard[currentY][currentX].clear();
			} 
            //이동할 좌표가 흰색
            else {
				int size = unitBoard[currentY][currentX].size();
                //현재 좌표의 말들을 이동할 좌표의 list에 추가
				for (int i = 0; i < size; i++) {
					Unit unit = unitBoard[currentY][currentX].get(i);
					unit.y = ny;
					unit.x = nx;
					unitBoard[ny][nx].add(unit);
				}
				unitBoard[currentY][currentX].clear();
			}

			//말을 이동시켰을때 이동시킨 좌표에 말이 4개 이상 겹쳐져있다면 함수 종료
			if(unitBoard[ny][nx].size()>=4) return true;
		}
		return false;
	}

	static class Unit {
		int num;
		int y;
		int x;
		int d;

		public Unit(int num, int y, int x, int d) {
			this.num = num;
			this.y = y;
			this.x = x;
			this.d = d;
		}
	}
}

---

Result

---

Reference