[BOJ 17837] 새로운 게임 2 (Java)

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

17837번: 새로운 게임 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_BOJ_17837 {
	static int[] dr= {0,0,0,-1,1};
	static int[] dc= {0,1,-1,0,0};
	static int[] opposites= {0,2,1,4,3};
	static int N, K;
	static HorseList[][] hmap;	//map 위치에 있는  horse들 저장
	static Horse[] horses;	//horse들 정보
	static int[][] map;		//color 저장
	static int answer=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());
		map=new int[N][N];
		horses=new Horse[K+1];
		hmap=new HorseList[N][N];
		for (int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				hmap[i][j]=new HorseList();
			}
		}
		int r, c, d;
		for (int i=1; i<=K; i++) {
			st=new StringTokenizer(br.readLine());
			r=Integer.parseInt(st.nextToken())-1;
			c=Integer.parseInt(st.nextToken())-1;
			d=Integer.parseInt(st.nextToken());
			horses[i]=new Horse(r,c,d);
			hmap[r][c].li.add(i); //
		}
		for (int i=0; i<1000; i++) {
			if (turn()) {
				answer=i+1;
				break;
			}
		}
		System.out.println(answer==0 ? -1 : answer);
	}
	
	private static boolean check() {
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (hmap[i][j].li.size()>=4) return true;
			}
		}
		return false;
	}

	private static boolean turn() {
		for (int i=1; i<=K; i++) {
			Horse h=horses[i];
			int r=h.r; 
			int c=h.c;
			int next_r=r+dr[h.d];
			int next_c=c+dc[h.d];
			if (!isValid(next_r, next_c) || map[next_r][next_c]==2) {		//벗어나는 경우, 파란색
				h.d=opposites[h.d];
				next_r=r+dr[h.d];
				next_c=c+dc[h.d];
				if (isValid(next_r, next_c) && map[next_r][next_c]!=2) {
					i--;		//한번 더 이동시키기
				}
			}
			else if (map[next_r][next_c]==0) {		//흰
				int loc=findNum(r, c, i);
				for (int j=loc; j<hmap[r][c].li.size(); j++) {
					int num=hmap[r][c].li.get(j);
					hmap[r][c].li.remove(j);
					hmap[next_r][next_c].li.add(num);
					horses[num].r=next_r;
					horses[num].c=next_c;
					j--;
				}
			}
			else if (map[next_r][next_c]==1) {		//빨
				int loc=findNum(r,c,i);
				int len=hmap[r][c].li.size();
				for (int j=len-1; j>=loc; j--) {
					int num=hmap[r][c].li.get(j);
					hmap[r][c].li.remove(j);
					hmap[next_r][next_c].li.add(num);
					horses[num].r=next_r;
					horses[num].c=next_c;
				}
			}
			if (check()) return true;
		}
		return false;
		
	}
	
	private static boolean isValid(int r, int c) {
		return r>=0 && c>=0 && r<N && c<N;
	}

	private static int findNum(int r, int c, int n) {
		for (int i=0; i<hmap[r][c].li.size(); i++) {
			if (n==hmap[r][c].li.get(i)) return i;
		}
		return -1;
	}
	public static class Horse{
		int r, c, d;
		public Horse(int r, int c, int d) {
			this.r = r;
			this.c = c;
			this.d = d;
		}
	}
	public static class HorseList{
		ArrayList<Integer> li;
		public HorseList() {
			li=new ArrayList<>();
		}
	}

}

구현+시뮬레이션 문제.

 

자료구조는 다음과 같이 정했다.

-각 말의 위치와 방향을 저장하는 1차원 배열 

-각 map의 위치에 존재하는 말 번호 리스트를 저장하고 있는 2차원 배열

 

1 turn 마다 1번부터 K번까지의 말들을 돌면서, 다음과 같이 움직여준다.

-파란색을 만날 경우 방향만 반대 방향으로 바꿔주고, 다음 갈 칸을 체크해 파란색이 아닐 경우 한번 더 이동시켜주기

-흰색을 만날 경우, 현재 말이 현재 있는 위치에서 몇번째 말인지 체크하고,

그 위치부터 시작해서 끝 위치까지 말부터 현재 위치에서 그 말을 빼주고, 새로운 위치에 말을 넣고, 말의 정보를 담고 있는 객체인 Horse의 위치 정보를 변경해준다. 이때 빼주는 연산이 있으므로 j-- 해서 remove 가 잘 되도록 한다. (주의)

-빨간색을 만날 경우, 이 역시 현재 말이 현재 있는 위치에서 몇번째 말인지 체크하고, 

역순으로 넣어야 하므로 끝 위치부터 시작해서 그 위치까지 흰색에서 했던 연산을 반복한다.

각 말을 움직일 때마다 check 함수를 호출해서 종료 조건이 되는지 확인한다.

 

remove 연산을 썼기 때문에 시간적으로 조금 아쉬운데,

다른 분들의 코드를 보니 (https://yabmoons.tistory.com/304)

흰색을 만날 경우, 새로운 위치에 삽입할 때=>현재 말이 현재 있는 위치에서 몇번째인지 구해줘서, 그 끝 위치까지 새로운 위치에 넣어주고

기존 위치에서 삭제할 때=>현재 말이 현재 있는 위치에서 "역순으로" 몇번째인지 구해줘서, 마지막 원소에서부터 그 위치까지 pop_back() 을 해주는 방식을 취하셨다.

 

반대인 빨간색을 만날 경우, 삽입할 때 흰색에서 삭제했던 것처럼 역순으로 접근해서 넣어주면 된다.