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

✨ 구현

 

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

17837번: 새로운 게임 2

---

📍 고려해야할 점

• 한 좌표 안에 여러 개의 말이 들어갈 수 있다. ➔ 이동하려는 칸에 말이 존재한다면 그 위에 말이 올라감
• 한 말이 이동할 때 위에 올려져 있는 말까지 모두 이동한다. 
• 여러 개의 말이 들어갈 때 좌표의 색깔에 따라 정렬 기준이 존재한다. 
• 좌표의 범위를 벗어나거나 좌표 칸이 파란색일 때의 조건을 유의해야한다. 

 

 

 

🕹️ 풀이과정 

어떤 자료구조로 활용할지 정하기만 하면 쉽게 풀리는 문제였다. 

• 하나의 말이 이동할 때 위에 올려져 있는 말까지 모두 이동해야하기 때문에 ArrayList<Integer>[][] horseInfo 로 선언했다.  
• 이동해야할 칸이 빨간색이라면 말이 쌓여있는 순서를 반대로 바꿔야 하고, 흰색이라면 그대로 쌓아야한다. 👉 순서가 앞뒤로 바꾸는 경우가 발생할 것이니 요소를 앞뒤에서 모두 뽑을 수 있는 Deque를 사용하기로 결정했다. 

 

알고리즘 과정은 다음과 같다. 

1. i번째의 말이 위치한 칸에 있는 모든 말들을 순서대로 뽑아 Deque에 저장한다. 
2. 위치한 칸에 있는 모든 말들을 제거한다. 
3. 말들을 이동시키려는 좌표의 색깔이 파란색이거나 범위를 벗어난다면 i번째 말의 방향을 반대로 바꾼다. 👉 바꾸고 나서도 이동하려는 칸이 또 파란색이거나 범위를 벗어난다면 움직이지 않는다. 
4. 좌표의 색깔이 빨간색이거나 흰색이면 이동시킨 후 순서를 조건에 맞도록 정렬한다. 👉 deque.pollFirst() 또는 deque.pollLast()
5. 이 과정을 반복하되, 한 칸에 4개 이상의 말이 존재하거나 turn 횟수가 1000번을 넘어간다면 반복문을 종료한다. 

 

 

 

👩‍💻 코드 

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

public class BOJ_17837_새로운게임2 {
	
	static int N, K;
	static int[][] board;

	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	
	static Info[] horse;
	static ArrayList<Integer>[][] horseInfo;
	static Deque<Integer> dq = new LinkedList<>();
	
	static class Info{
		int x, y, d, n;
		public Info(int x, int y, int d, int n) {
			this.x=x;
			this.y=y;
			this.d=d;
			this.n=n;
		}
	}
	
	
	static boolean simulate() {
		
		for(int i=0; i<K; i++) {
			Info now = horse[i];
			int size = horseInfo[now.x][now.y].size();
			if(size>=4) return true;
			dq = new LinkedList<>();
			
			// 현재 말 위에 있는 말들 
			for(int j=size-1; j>=0; j--) {
				int idx = horseInfo[now.x][now.y].get(j);
				dq.add(idx);
				horseInfo[now.x][now.y].remove(horseInfo[now.x][now.y].size()-1);
				if(idx==now.n) break;
			}
			
			int nx = now.x+dx[now.d];
			int ny = now.y+dy[now.d];
			
			// 파란색이거나 범위를 벗어난다면 
			if(nx<0 || ny<0 || nx>=N || ny>=N || board[nx][ny]==2){
				
				// 현재 말의 방향을 반대로 
				if(now.d==1 || now.d==3) now.d--;
				else now.d++;
				
				nx = now.x+dx[now.d];
				ny = now.y+dy[now.d];
				
				if(nx<0 || ny<0 || nx>=N || ny>=N || board[nx][ny]==2) {
					while(!dq.isEmpty()) {
						int n = dq.pollLast();
						horseInfo[now.x][now.y].add(n);
					}
					continue;
				}
			}
			
			// 이동할 칸이 흰색이라면 
			if(board[nx][ny]==0) {
				while(!dq.isEmpty()) {
					int n = dq.pollLast();
					horseInfo[nx][ny].add(n);
					horse[n].x=nx;
					horse[n].y=ny;
				}
			}
			
			// 빨간색이라면
			else if(board[nx][ny]==1) {
				while(!dq.isEmpty()) {
					int n = dq.pollFirst();
					horseInfo[nx][ny].add(n);
					horse[n].x=nx;
					horse[n].y=ny;
				}
			}
			
			if(horseInfo[nx][ny].size()>=4) return true;
		}
		return false;
	}
	
	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());
		board = new int[N][N];
		horse = new Info[K];
		horseInfo = new ArrayList[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				horseInfo[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 x = Integer.parseInt(st.nextToken())-1;
			int y = Integer.parseInt(st.nextToken())-1;
			int d = Integer.parseInt(st.nextToken())-1;
			
			horse[i] = new Info(x, y, d, i);
			horseInfo[x][y].add(i);
		}
		
		int answer=0;
		
		while(true) {
			
			if(simulate())break;
			
			answer++;
			
			if(answer>1000)break;
		}
		
		if(answer>1000) System.out.println(-1);
		else System.out.println(answer+1);
	}
}