[BOJ] 17837 새로운 게임 2

 

 

[문제]

 

 

[소스 코드]

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

public class Main {
	static int n,k;
	static List<Integer>[][] map;
	static int[][] horse,color;
	static int[] dr = {0,1,0,-1};
	static int[] dc = {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];
		map = new LinkedList[n][n];
		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());
				map[i][j] = new LinkedList<>(); 
			}
		}
		horse = new int[k][3];
		for(int i=0;i<k;i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken()) - 1;
			int d = Integer.parseInt(st.nextToken());
			if(d==1) d = 0;
			if(d==4) d = 1;
			horse[i][0] = r;
			horse[i][1] = c;
			horse[i][2] = d;
			map[r][c].add(i);
		}
		game();
	}
	private static void game() {
		for(int t=1;t<=1000;t++) {
			for(int i=0;i<k;i++) {
				int r = horse[i][0];
				int c = horse[i][1];
				int d = horse[i][2];
				int order = searchOrder(r,c,i);
				int nr = r + dr[d];
				int nc = c + dc[d];
				if(nr<0 || nr>=n || nc<0 || nc>=n || color[nr][nc]==2) { 
					d = (d+2)%4;
					nr = r + dr[d];
					nc = c + dc[d];
					horse[i][2] = d;
					if(nr<0 || nr>=n || nc<0 || nc>=n || color[nr][nc]==2) continue;
				}
				if(move(r,c,nr,nc,order)) {
					System.out.println(t);
					return;
				}
			}
		}
		System.out.println(-1);
	}
	private static boolean move(int r,int c,int nr,int nc,int order) {
		List<Integer> list = new LinkedList<>();
		while(map[r][c].size()>order) {
			list.add(map[r][c].remove(order));
		}
		if(color[nr][nc]==1) {
			Collections.reverse(list);
		}
		for(int idx : list) {
			horse[idx][0] = nr;
			horse[idx][1] = nc;
			map[nr][nc].add(idx);
		}
		return map[nr][nc].size()>=4;
	}
	private static int searchOrder(int r,int c,int i) {
		for(int j=0;j<map[r][c].size();j++) {
			if(map[r][c].get(j)==i) return j;
		}
		return -1;
	}
}

 

1. 모든 horse 이동 + 해당 위치로 이동 가능한지 확인

2. horse 이동 -> color에 따른 이동 설정