[백준] 17837.새로운 게임 2 (java) / 시뮬레이션

@시뮬레이션 / 1h 38m(필기 18m, 디버깅 1h 포함)

어제 푼 새로운 게임(백준 17780) 이랑 거의 똑같은 문제인데

실수로 조건 하나 놓쳐서 그거 잡느라 1시간 걸렸다 ㅠㅠ

 

 

문제 링크

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

17837번: 새로운 게임 2

 

 

 

구현 포인트

1. 큰 틀은 새로운 게임과 거의 똑같다.

포스팅 바로가기

 

 

2. 차이점은 새로운 게임은 가장 아래에 있는 말만 이동할 수 있지만,

새로운 게임 2는 가장 아래에 있는 말이 아니어도 이동할 수 있다는 점이다.

예를 들면

D
C

A

이렇게 쌓여 있을 때, 새로운 게임은 A일때만 이동할 수 있지만, 새로운 게임 2는 C와 D일 때도 이동 가능하다.

 

 

3. 이 부분을 해결하기 위해서

몇 번째에 해당 말이 위치하는지 찾기 위한 searchOrder 함수를 만들었다.

이 함수는 말이 있는 칸에서 몇번째 높이(num이라 지칭)에 해당 말이 있는지를 반환 해 준다.

 

 

4. 말이 이동할 때, searchOrder에서 반환받은 높이인 num을 기준으로 말을 옮겨 준다.

이 때, 옮기는 횟수는 칸의 총 높이(size)가 해당 말이 있는 위치(num) 보다 클 동안 반복해준다.

D
C

A

여기서 C부터 옮긴다고 가정하면, 높이는 1(맨 아래 A의 높이는 0)이 되고,

이 높이 부터 리스트에서 remove(높이) 해서 옮겨 준다.

만약, 반대로 쌓아야 할 경우, removeLast() 를 이용해서 옮겨준다.

 

size > num 일 동안 옮겨 주기 때문에, size == num 이 되는 순간(여기서는 A만 남는 순간)

옮기는 행위가 끝난다.

 

 

 

삽질 포인트

아무 생각 없이 파란색일때 반대방향으로 옮겨줄 때는 흰색 칸에 옮기는 것 처럼 했는데

테케 3번에서 계속 -1이 나왔다.

가려는 칸이 파란색이거나, 경계인 경우 반대 방향의 칸의 색깔이 뭔지에 따라 옮기는 방법을 달리해줘야 한다!

이거 잡느라 한시간 썼다 ㅠㅠ

 

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	
	private static int N, K, color[][], horse[][];
	private static LinkedList<Integer>[][] map;
	private static int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		color = new int[N][N];
		horse = new int[K][3];
		map = new LinkedList[N][N];
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				map[i][j] = new LinkedList<>();
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				color[i][j] = Integer.parseInt(st.nextToken());
		}
		
		int x, y, d;
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken()) - 1;
			y = Integer.parseInt(st.nextToken()) - 1;
			d = Integer.parseInt(st.nextToken());
			
			if (d == 1) d = 0;
			else if (d == 4) d = 1;
			
			horse[i][0] = x;
			horse[i][1] = y;
			horse[i][2] = d;
			
			map[x][y].add(i);
		}
		game();
	}

	private static void game() {
		for (int t = 1; t <= 1000; t++) {
			for (int k = 0; k < K; k++) {
				int x = horse[k][0];
				int y = horse[k][1];
				int d = horse[k][2];
				int num = searchOrder(k, x, y);
				
				int nx = x + dx[d];
				int ny = y + dy[d];
				
				if (nx < 0 || nx >= N || ny < 0 || ny >= N || color[nx][ny] == 2) {
					horse[k][2] = d = (d + 2) % 4;
					nx = x + dx[d];
					ny = y + dy[d];
					
					if (nx < 0 || nx >= N || ny < 0 || ny >= N || color[nx][ny] == 2)
						continue;
				}
				
				if (move(x, y, nx, ny, num, color[nx][ny])) {
					System.out.println(t);
					return;
				}
			}
		}
		System.out.println("-1");
	}

	private static boolean move(int x, int y, int nx, int ny, int num, int order) {
		while (map[x][y].size() > num) {
			int temp = -1;
			if (order == 0)
				temp = map[x][y].remove(num);
			else 
				temp = map[x][y].removeLast();
			
			horse[temp][0] = nx;
			horse[temp][1] = ny;
			map[nx][ny].add(temp);
		}

		if (map[nx][ny].size() >= 4)
			return true;
		
		return false;
	}

	private static int searchOrder(int n, int x, int y) {
		for (int i = 0; i < map[x][y].size(); i++)
			if (map[x][y].get(i) == n)
				return i;
		
		return -1;
	}
}

 

똑같은 문제네 하고 만만하게 봤다가, 고생했다.

 

끝!