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

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

문제 탐색하기

또 다른 구현 문제다. 보자마자 눈이 핑 돈다면 제대로 문제를 읽은게 맞다. 체스판과 말을 활용하여 아래의 규칙을 따르도록 만족하면 된다. 체스판에는 흰색, 빨간색, 파란색으로 칠해져있고 이를 통해서 지켜야할 규칙은 아래와 같다.

• 흰색인 경우 (칸이 0일 때)
  • 가장 위에 A번 말을 올려놓는다 (A번 위에 말이 있는 경우 같이 옮긴다.)
• 빨간색의 경우 (칸이 1일 때)
  • 가장 위에 A번 말을 올려놓는건 동일하다. (A번 위에 말이 있는 경우 옮긴 후 A번 부터 해당 말의 순서를 뒤집는다.
• 파란색의 경우 (칸이 2일 때)
  • A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 이동하지 않고 가만히 있는다.
• 체스판을 벗어나는 경우
  • 파란색과 동일하다.

위의 규칙을 문제에 나열된 순서대로 구현하면 될 듯 하지만 실상은 그렇지 않다. 위의 경우는 다음 칸에 도달 가능할 때의 얘기이고 매번 말이 움직일 때마다 범위 체크를 먼저 해주어야 한다. 하지만 범위체크를 하면 파란색과 동일한 취급을 받으므로 이를 flag 처럼 써서 파란색을 두번 통과 했는지 확인하는 방식으로 코드를 구현하면 된다.

 

시간복잡도는 어떤 식으로 측정해야할까. 문제에서 1000번 이상 진행하거나 절대로 게임이 종료되지 않는 (예제 1번의 경우) 경우에는 -1 출력하라고 되어 있다. 매 순회마다 모든 말을 이동 시켜야 하므로 K번 반복해야하며, 1000번 이상 진행해야 할 수 있고. 모든 말을 옮겨야 한다면 최악의 경우 K라고 할 수 있다. 이에 따라서 시간 복잡도는 O(K ^ 2) 정도로 보는 것이 타당할 것이다.

 

이런 문제를 구현할 때 제일 중요한 것은 문제를 이해하였는지 확인하는 것인데 말로 옮겨보거나 직접 출력을 해서 결과물을 볼 수 있다면 더할 나위 없다. 이번 문제를 해결할 때 여러번 IndexOutOfBoundsException을 만나고 정신을 차려보니 여러번 틀렸다. 조건만 맞추면 리스트를 순회할 수 있을 줄 알았지만 실상은 아예 빈 리스트를 뒤지고 있었다. 

 

코드 구현하기

1. 문제의 입력을 받고 체스판이 될 2차원 배열과 말을 기록할 2차원 배열, 그리고 HashMap을 통해서 말들의 위치를 기억하여 매번 순회를 할 때 사용할 수 있도록 만든다.
2. 말의 이동을 구현한다.
   1. 말이 체스판의 범위를 벗어나지 않는지 확인한다. 벗어난다면 체크해두고 방향을 전환한다. 이 때 기록을 해두는 이유는 이후에 파란 색을 한번 더 만나는지를 구현하기 위함이다.
   2. 앞서 체스판의 범위를 벗어나지 않았다면 그 바뀐 진행 방향이 흰색이나 빨간 색을 만날 때만 말들이 이동한 기록을 구현해 둔다.
   3. 범위를 벗어나지 않고 기본 진행 방향이 흰색이나 빨간 색을 만나는지 확인한다.
   4. 빨간 색을 만난다면 기록해둔 말들의 순서를 뒤 바꾸고 기존 위치에 남겨둘 말과 이후 위치에 남겨둘 말을 기록한다.
   5. HashMap에 새로 바뀐 말들의 위치를 업데이트 한다.
   6. 올라탄 말의 수가 4이상인지 확인한다.
3. 반복문을 통해서 매 순회 마다 말의 번호를 1번 부터 K번 까지 반복하고 모든 순회를 1000번 반복하여 게임이 몇 번 진행 되는지 확인한다.
4. 답이 1001 보다 같거나 크면 -1을 출력하고 아니면 게임 진행 횟수를 출력한다.

시도 회차 수정사항

1회차

리스트의 인덱스를 넘어서는 예외를 만나고 조건문을 통해서 인덱스를 미리 확인하도록 하였지만 여전히 같은 오류를 만나게 됐다. 그러던 중 if 문의 분기가 잘못된것을 깨닫고 범위 체크를 먼저 하는 방식으로 변경하였다.

 

2회차

예제는 다 맞았지만 정답을 구할 수 없었다. 이에 따라서 말들이 이동하는 경로를 직접 출력하여 확인해보았고 1번 예제에서 중간에 없어지는 말이 존재한다는 것을 깨달았다... 이에 따라서 나와 같은 사람들이 고통받지 않도록 이를 아래와 같이 남겨두었다..

헉

 

풀이

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

public class Main {
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}

	static class Node {
		int x, y, dir, num;

		public Node(int x, int y, int dir, int num) {
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.num = num;
		}

		@Override
		public boolean equals(Object o) {
			if (o instanceof Node) {
				Node n = (Node) o;
				return n.num == this.num;
			}
			return false;
		}

		@Override
		public int hashCode() {
			return (num + ", ").hashCode();
		}

		@Override
		public String toString() {
			return "(" + x + ", " + y + ", " + dir + ", " + num + ")";
		}
	}

	static int N, K, count;
	static boolean end = false;
	static int[][] board;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	static HashMap<Integer, Node> map = new HashMap<>();
	static ArrayList<Node>[][] nodes;

	static int blue(int currentDir) {
		if (currentDir == 0) {
			return 1;
		} else if (currentDir == 1) {
			return 0;
		} else if (currentDir == 2) {
			return 3;
		}
		return 2;
	}

	static boolean checkWhite(int x, int y) {
		return board[x][y] == 0;
	}

	static boolean checkRed(int x, int y) {
		return board[x][y] == 1;
	}

	static boolean checkBlue(int x, int y) {
		return board[x][y] == 2;
	}

	static void printBoard(ArrayList<Node>[][] board) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(board[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("__________________________");
	}

	static void move(Node now) {
		int index = nodes[now.x][now.y].indexOf(now);
		int nx = now.x + dx[now.dir];
		int ny = now.y + dy[now.dir];
		boolean checked = false;
		ArrayList<Node> temp = new ArrayList<>();

		if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
			int newDir = blue(now.dir);
			nx = now.x + dx[newDir];
			ny = now.y + dy[newDir];
			now.dir = newDir;
			checked = true;
		}

		if (checkBlue(nx, ny)) {
			if (!checked) {
				int newDir = blue(now.dir);
				nx = now.x + dx[newDir];
				ny = now.y + dy[newDir];
				now.dir = newDir;
				if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
					return;
				}
				if (checkWhite(nx, ny)) {
					temp.add(new Node(nx, ny, now.dir, now.num));
					for (int j = index + 1; j < nodes[now.x][now.y].size(); j++) {
						Node node = nodes[now.x][now.y].get(j);
						temp.add(new Node(nx, ny, node.dir, node.num));
					}
				} else if (checkRed(nx, ny)) {
					temp.add(new Node(nx, ny, now.dir, now.num));
					for (int j = index + 1; j < nodes[now.x][now.y].size(); j++) {
						Node node = nodes[now.x][now.y].get(j);
						temp.add(new Node(nx, ny, node.dir, node.num));
					}
				} 
			}
		} else if (checkWhite(nx, ny)) {
			temp.add(new Node(nx, ny, now.dir, now.num));
			for (int j = index + 1; j < nodes[now.x][now.y].size(); j++) {
				Node node = nodes[now.x][now.y].get(j);
				temp.add(new Node(nx, ny, node.dir, node.num));
			}
		} else if (checkRed(nx, ny)) {
			temp.add(new Node(nx, ny, now.dir, now.num));
			for (int j = index + 1; j < nodes[now.x][now.y].size(); j++) {
				Node node = nodes[now.x][now.y].get(j);
				temp.add(new Node(nx, ny, node.dir, node.num));
			}
		}

		ArrayList<Node> original = new ArrayList<>();
		for (int j = 0; j < nodes[now.x][now.y].size(); j++) {
			Node node = nodes[now.x][now.y].get(j);
			if (!temp.contains(node)) {
				original.add(node);
			}
		}

		if (checkRed(nx, ny)) {
			Collections.reverse(temp);
		}


		for (Node n : temp) {
			nodes[nx][ny].add(n);
			map.put(n.num, n);
		}

		if (nodes[nx][ny].size() >= 4) {
			end = true;
		}
		nodes[now.x][now.y] = original;
	}

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		N = fr.nextInt();
		K = fr.nextInt();
		board = new int[N][N];
		nodes = new ArrayList[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = fr.nextInt();
				nodes[i][j] = new ArrayList<>();
			}
		}

		for (int i = 0; i < K; i++) {
			int x = fr.nextInt() - 1;
			int y = fr.nextInt() - 1;
			Node now = new Node(x, y, fr.nextInt() - 1, i);
			map.put(i, now);
			nodes[x][y].add(now);
		}

		while (count++ < 1001) {
			for (int i = 0; i < K; i++) {
				move(map.get(i));
			}

			if (end) {
				break;
			}
		}

		System.out.println(count >= 1001 ? -1 : count);
	}
}