[Java] 백준 17780 - 새로운 게임

 

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

17780번: 새로운 게임

이런 유형의 문제는 어디서 많이 봤는데, 풀어야지 풀어야지 해놓고 보기만 했던거같다

 

※ 문제에서 주어진 것

N : 체스판 크기 (N x N)

K : 말의 개수

 

※ 변수 의미

(인터넷의 여러 풀이 방법 참조)

- int[][] chess : 각 색깔 정보를 담은 체스판

- Deque<Integer> [][] deque : 각 체스판에 올려진 말

- Node : 각 말의 정보 (좌표 p, q, 방향 dir)

- ArrayList<Node> nodes : 말을 담은 arrayList

 

※ 방법

1. 최대 횟수인 1000까지만 반복하도록 while문 생성

2. while 1회실행시 nodes에 있는 노드들 K개를 꺼내옴

3. 꺼내온 노드의 좌표 p,q에 대하여 deque[p][q]의 가장 아래에 있는 노드 번호인지 확인

4-1. 가장 아래에 있지 않으면 다음 노드 가져옴 (continue) -> 3으로 이동

4-2. 가장 아래에 있으면 방향을 보고 이동할 좌표 nextP, nextQ를 지정

5. nextP와 nextQ의 색깔 확인 후 각 색깔에 맞춰 방향 및 이동 적용

6. 만약 nextP, nextQ로 이동 후, 쌓인 말의 개수가 4개 이상일 경우 턴(cnt) 출력 후 종료

7. 만약 while문을 빠져나오게 되면(1000번 이상 진행됨) -1 출력 후 종료

 

package BOJ;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.StringTokenizer;

public class boj17780 {
	// 색
	private static int WHITE = 0;
	private static int RED = 1;
	private static int BLUE = 2;
	
	// 0 : -> // 1 : <- // 2 : up // 3 :down
	private static int[] dir_p = {0, 0, -1, 1};
	private static int[] dir_q = {1, -1, 0, 0};
	
	private static int[][] chess;
	private static Deque<Integer>[][] deque;
	private static ArrayList<Node> nodes;
	
	static class Node{
		// 좌표 p,q
		int p,q;
		
		// 방향 dir
		int dir;
		
		public Node(int p, int q, int dir)
		{
			this.p = p;
			this.q = q;
			this.dir = dir;
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		chess = new int[N+1][N+1];
		deque = new ArrayDeque[N+1][N+1];
		nodes = new ArrayList<>();
		
		// 흰색 -> 올려줌
		// 빨간색 -> 말의 순서 바꿈
		// 파란색 -> 이동방향을 반대로 하고 한 칸 이동 (체스판을 벗어나는 경우도 동일)
		// 이동하려는 칸이 파란색 -> 방향만 바꿈
		// 0 : 흰색 * 1 : 빨간색 * 2 : 파란색
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				chess[i][j] = Integer.parseInt(st.nextToken());
				deque[i][j] = new ArrayDeque<>();
			}
		}
		
		// 이동방향
		// 1 : -> // 2 : <- // 3 : up // 4 :down
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken())-1;
			int q = Integer.parseInt(st.nextToken())-1;
			int dir = Integer.parseInt(st.nextToken())-1;
			
			nodes.add(new Node(p,q,dir));
			deque[p][q].offer(i);			
		}
		
		
		int cnt = 1;
		
		// N : 체스판의 크기
		// K : 말의 개수
		while(cnt <= 1000) {
			for(int i=0; i<K; i++) {
				Node n = nodes.get(i);
				
				int p = n.p;
				int q = n.q;
				
				// 가장 아래가 아니면 continue;
				if(deque[p][q].getFirst() != i)
					continue;
				
				// 다음 좌표
				int nextP = p + dir_p[n.dir];
				int nextQ = q + dir_q[n.dir];
				
				// 0 : -> // 1 : <- // 2 : up // 3 :down
				
				// 체스판을 벗어나거나 현재 위치가 파란색인 경우 (체스판 벗어날 수 있기 때문에 제일 먼저 지정함)
				if(nextP < 0 || nextP >= N || nextQ < 0 || nextQ >= N || chess[nextP][nextQ]== BLUE) {
					int newDir = n.dir;
					
					//방향 반대로
					if(newDir % 2 == 0)
						newDir += 1;
					else
						newDir -= 1;
					
					nextP = p + dir_p[newDir];
					nextQ = q + dir_q[newDir];
					
					// 바라보는 방향이 BLUE 인 경우
					if(nextP < 0 || nextP >= N || nextQ < 0 || nextQ >= N ||chess[nextP][nextQ] == BLUE) {
						nextP = p;
						nextQ = q;
					} else {
						int c = chess[nextP][nextQ];
						move(p, q, nextP, nextQ, c, i, n);
					}
					
					nodes.set(i, new Node(nextP, nextQ, newDir));
				}else{
					int c = chess[nextP][nextQ];
					move(p, q, nextP, nextQ,c, i, n);
				}
				
				if(deque[nextP][nextQ].size() >= 4) {
					bw.write((int)cnt +"");
					bw.flush();
					bw.close();
					return ;
				}
			}
			cnt++;
		}
		
		bw.write("-1");
		bw.flush();
		bw.close();
		
		System.out.println(cnt);
	}
	
	// 거꾸로 쌓음
	static void move(int p, int q, int nextP, int nextQ, int c, int i, Node n) {
		if(c == WHITE) {
			while(!deque[p][q].isEmpty()) {
				int idx = deque[p][q].pollFirst();
				nodes.set(idx, new Node(nextP,nextQ,nodes.get(idx).dir));
				deque[nextP][nextQ].offer(idx);
			}
		}else {
			while(!deque[p][q].isEmpty()) {
				int idx = deque[p][q].pollLast();
				nodes.set(idx, new Node(nextP,nextQ,nodes.get(idx).dir));
				deque[nextP][nextQ].offer(idx);
			}
		}
		
		// 맨 밑에 있던 노드 방향 조정
		nodes.set(i, new Node(nextP, nextQ, n.dir));
	}
}

 

Deque의 사용은 처음이었다!

저번에 공부했던 PrioryQueue에 이어서 추가로 알게 되어서 뭔가 기쁘고,

"다들 공부 열심히 해서 이것저것 쓰는구나.."를 새삼 느끼게 되었다.