BOJ 17837 새로운 게임 2(JAVA) 🎮

문제 링크

17837번: 새로운 게임 2

문제 설명

게임 종료 시점에 몇 번의 턴이 진행되었는지 찾기, 한 칸에 4개 이상의 말이 쌓이면 게임이 종료

입력

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.

다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.

같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

출력

게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.

구조화

이동하려는 칸의 케이스 구분

• 흰색(0)
• 빨간색(1)
• 파란색(2)

파란색의 경우

위의 케이스를 한번 더 적용

오답 노트

문제를 잘 읽자! 4개 이상을 K로 생각해서 시간을 많이 날린 문제ㅠㅠ

소스 코드

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

public class Main_17837_새로운게임2 {

	/*
	 * 
	 * 말이 이동하려는 칸이
	 * 흰색이면(0)
	 * 원래 있던 것 뒤로 쌓임
	 * 
	 * 빨간색이면(1)
	 * 원래 있던 것 뒤로 거꾸로 쌓임
	 * 
	 * 파란색이면(2), 경계면
	 * 반대방향으로 이동하려는 칸이
	 * 파란색, 경계면 stop
	 * 
	 * 종료는 모든 말이 한칸에 있을때
	 * -1은 절대로 종료되지 않는 경우 -> 모든 말이 stop
	 * or 1000보다 넘어가면!
     *
	 */
     
	static public class Horse{
		int y;
		int x;
		int d;

		public Horse(int y, int x, int d) {
			super();
			this.y = y;
			this.x = x;
			this.d = d;
		}
		
		
	}
	static int N, K, result, turn;
	static HashMap<Integer, Horse> horse;
	static int[][] map;
	static List<Integer>[][] list;
	
	static int[][] way = {{},{0,1},{0,-1},{-1,0},{1,0}};
	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());
		
		horse = new HashMap<>();
		map = new int[N][N];
		list = new ArrayList[N][N];
		for (int i = 0; i < N; i++) 
		{
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) 
			{
				list[i][j] = new ArrayList<>();
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i < K; i++) 
		{
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			horse.put(i+1,new Horse(y-1,x-1,d));
			list[y-1][x-1].add(i+1);
		}
		
		playGame();

	}
	
	private static void playGame() {
		
		turn = 0;
		
		Outer: while(++turn <= 1000)
		{
			for (int i = 1; i <= K; i++) 
			{
				Horse cur = horse.get(i);
				List<Integer> up_horse = new ArrayList<>();
				int y = cur.y;
				int x = cur.x;
				int d = cur.d;
				int start_idx = findIdx(y,x,i);
				
				for(int j=start_idx;j < list[cur.y][cur.x].size();j++){
					up_horse.add(list[cur.y][cur.x].get(j));
				}

				int ny = y + way[d][0];
				int nx = x + way[d][1];
				
				// 경계를 넘었거나 파란색이면
				if(!isRight(ny,nx) || map[ny][nx]==2)
				{
					// 방향을 바꿔서 한번더!
					// 짝수면 -- 홀수면 ++
					ny -= way[d][0];
					nx -= way[d][1];
					int dir = d%2==0 ? d-1 : d+1;
					ny += way[dir][0];
					nx += way[dir][1];
					cur.d = dir;
					if(!isRight(ny,nx) || map[ny][nx]==2)
					{
						continue;
					}
					else 
					{
						if(map[ny][nx] == 1) {
                            for (int p = up_horse.size() - 1; p >= 0; p--) {
                                list[ny][nx].add(up_horse.get(p));
                                Horse hh = horse.get(up_horse.get(p));
                                horse.put(up_horse.get(p), new Horse(ny, nx, hh.d));
                            }
                        } else {
                            for(Integer h:up_horse) {
                                list[ny][nx].add(h);
                                Horse hh = horse.get(h);
                                horse.put(h, new Horse(ny, nx, hh.d));
                            }
                        }
					}
				}
				
				// 가려고 하는 칸이 흰색이라면
				else if(map[ny][nx]==0)
				{
					for(Integer h:up_horse) {
                        list[ny][nx].add(h);
                        Horse hh = horse.get(h);
                        horse.put(h, new Horse(ny, nx, hh.d));
                    }
				}
				// 가려고 하는 칸이 빨간색이라면
				else if(map[ny][nx]==1)
				{
					for(int p=up_horse.size()-1;p>=0;p--){
                        list[ny][nx].add(up_horse.get(p));
                        Horse hh = horse.get(up_horse.get(p));
                        horse.put(up_horse.get(p), new Horse(ny, nx, hh.d));
                    }
				}

				// 한 칸에 있는 말의 수가 4개 이상이라면 턴 종료
				if(list[ny][nx].size()>=4)
				{
					break Outer;
				}
				
				// 말 뺴기
                for(int p=list[y][x].size()-1;p>=start_idx;p--){
                    list[y][x].remove(p);
                }
			}
		}
		System.out.println(turn>1000?-1:turn);
	}

	private static int findIdx(int y, int x, int idx) {
		for (int i = 0; i < list[y][x].size(); i++) {
			if(list[y][x].get(i) == idx)
			{
				return i;
			}
		}
		return 0;
	}

	private static boolean isRight(int ny, int nx) {
		return (ny>=0 && ny<N && nx>=0 && nx<N);
	}

}