[백준 - 17780] 골드2 - 새로운 게임

www.acmicpc.net/problem/17780

17780번: 새로운 게임

풀이시간: 1시간 50분

 

1. 유형

시뮬레이션

 

2. 풀이법

ArrayList로 이차원 배열을 만드는 발상이 중요하다.

 

또한 파란색을 밟았을 때, 뒤돌아 가는 것이 중요하다.

static int side[] = {0, 2, 1, 4, 3}; 처럼 반대 방향을 따로 저장

 

3.코드

package 나혼자푸는문제;

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

public class back_17780새로운게임 {
	static int N,K,map[][];
	static ArrayList<Pair> horse[][];
	static int dr[] = { 0, 0, 0, -1, 1 };
	static int dc[] = { 0, 1, -1, 0, 0 };
	static int side[] = {0, 2, 1, 4, 3};
	static class Pair{
		int idx;
		int d;
		public Pair(int idx, int d) {
			this.idx=idx;
			this.d=d;
		}
	}
	public static void main(String[] args) throws IOException {
		init();
		solve();
	}
	static void solve() {
		int cnt=0;
		out:while(true) {
			if(cnt>1000) { 
				cnt=-1;
				break;
			}
			cnt++;
			for (int h = 1; h <= K; h++) {//말
				out2:for (int i = 1; i <= N; i++) {
					for (int j = 1; j <= N; j++) {
						if(horse[i][j].size()>0 && horse[i][j].get(0).idx==h) {
							ArrayList<Pair> cur = horse[i][j];
							int ny = i+dr[cur.get(0).d];
							int nx = j+dc[cur.get(0).d];
							//파란색과 맵 이탈
							if(ny<1 || ny>N || nx<1 ||nx>N || map[ny][nx]==2) {
								ny = i+dr[side[cur.get(0).d]];
								nx = j+dc[side[cur.get(0).d]];
								cur.get(0).d = side[cur.get(0).d];
								if(ny<1 || ny>N || nx<1 ||nx>N || map[ny][nx]==2) {
									continue;
								}
							}
							if(map[ny][nx]==1) {
								for (int k = cur.size()-1; k >=0; k--) {
									horse[ny][nx].add(new Pair(cur.get(k).idx, cur.get(k).d));
									cur.remove(k);
								}
								if(horse[ny][nx].size()>=4) break out;
								break out2;
							}
							if(map[ny][nx]==0) {
								int len = cur.size();
								for (int k = 0; k<len ; k++) {
									horse[ny][nx].add(new Pair(cur.get(0).idx, cur.get(0).d));
									cur.remove(0);
								}
								if(horse[ny][nx].size()>=4) break out;
								break out2;
							}
						}
					}
				}
			}
		}
		System.out.println(cnt);
	}
	static void init() throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(in.readLine(), " ");
		N=Integer.valueOf(st.nextToken());
		K=Integer.valueOf(st.nextToken());
		map=new int[N+1][N+1];
		for (int i = 1; i < N+1; i++) {
			st = new StringTokenizer(in.readLine()," ");
			for (int j = 1; j < N+1; j++) {
				map[i][j] = Integer.valueOf(st.nextToken());
			}
		}
		horse = new ArrayList[N+1][N+1];
		for (int i = 0; i < N+1; i++) {
			for (int j = 0; j < N+1; j++) {
				horse[i][j] = new ArrayList<>();
			}
		}
		int y,x,d;
		for (int i = 1; i <= K; i++) {
			st=new StringTokenizer(in.readLine()," ");
			y=Integer.valueOf(st.nextToken());
			x=Integer.valueOf(st.nextToken());
			d=Integer.valueOf(st.nextToken());
			horse[y][x].add(new Pair(i, d));
		}
	}
}

이차원 리스트 만들고 메모리 할당

		horse = new ArrayList[N+1][N+1];
		for (int i = 0; i < N+1; i++) {
			for (int j = 0; j < N+1; j++) {
				horse[i][j] = new ArrayList<>();
			}
		}

다음 좌표를 추출한다

if(horse[i][j].size()>0 && horse[i][j].get(0).idx==h) {
    ArrayList<Pair> cur = horse[i][j];
    int ny = i+dr[cur.get(0).d];
    int nx = j+dc[cur.get(0).d];

빨간 칸 밟으면 거꾸로 좌표에 넣는다

for (int k = cur.size()-1; k >=0; k--) {
    horse[ny][nx].add(new Pair(cur.get(k).idx, cur.get(k).d));
    cur.remove(k);
}

흰색은 순서대로 넣는다. 리스트를 0번부터 지우면 순서가 바뀌기 때문에, 연속해서 index 0번만 지워준다.

for (int k = 0; k<len ; k++) {
    horse[ny][nx].add(new Pair(cur.get(0).idx, cur.get(0).d));
    cur.remove(0);
}