[Java] 백준 17837번 : 새로운 게임 2

코딩테스트/구현(Implementation)

[Java] 백준 17837번 : 새로운 게임 2

sujin7837 2022. 4. 30. 17:23

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

A번 말이 이동하려는 칸이
- 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
  - A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
  - 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
- 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
  - A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
  - A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
- 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
- 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

첫 번째 턴은 다음과 같이 진행된다.

두 번째 턴은 다음과 같이 진행된다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.

입력

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.

다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.

같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

출력

게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.

제한

4 ≤ N ≤ 12
4 ≤ K ≤ 10

예제 입력 1

예제 출력 1

-1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

예제 입력 5

6 10
0 1 2 0 1 1
1 2 0 1 1 0
2 1 0 1 1 0
1 0 1 1 0 2
2 0 1 2 0 1
0 2 1 0 2 1
1 1 1
2 2 2
3 3 4
4 4 1
5 5 3
6 6 2
1 6 3
6 1 2
2 4 3
4 2 1

예제 출력 5

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int N, K;
	private static int[][] board;	// 체스판의 색 저장
	private static Deque<Integer> [][]queue;	// 체스판에 놓인 말의 번호 저장
	private static int[] dx = { 0, 0, 0, -1, 1 };
	private static int[] dy = { 0, 1, -1, 0, 0 };
	private static Horse []horses;

	static class Horse {
		int r, c, dir;

		public Horse(int r, int c, int dir) {
			super();
			this.r = r;
			this.c = c;
			this.dir = dir;
		}

		@Override
		public String toString() {
			return "Horse [r=" + r + ", c=" + c + ", dir=" + dir + "]";
		}

	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		horses=new Horse[K+1];
		queue=new LinkedList[N+1][N+1];
		for(int r=1;r<=N;r++) {
			for(int c=1;c<=N;c++) {
				queue[r][c]=new LinkedList<>();
			}
		}

		board = new int[N+1][N+1];
		for(int r=1;r<=N;r++) {	// 체스판의 색
			st=new StringTokenizer(br.readLine());
			for(int c=1;c<=N;c++) {
				board[r][c]=Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=1;i<=K;i++) {	// 말의 정보와 체스판 위 놓인 말의 번호
			st=new StringTokenizer(br.readLine());
			int r=Integer.parseInt(st.nextToken());
			int c=Integer.parseInt(st.nextToken());
			int dir=Integer.parseInt(st.nextToken());
			horses[i]=new Horse(r, c, dir);
			queue[r][c].add(i);
		}
		
		System.out.println(startGame());
	}

	private static int startGame() {
		int cnt=0;
		while(cnt<1000) {	// 1000번 미만이면 게임 진행
			cnt++;
			for(int i=1;i<=K;i++) {	// 1번부터 K번 말까지 이동 수행
				int r=horses[i].r;
				int c=horses[i].c;
				
				Deque<Integer> q=new LinkedList<>();
				q.addAll(queue[r][c]);
				queue[r][c].clear();	// 현재 위치에서 이동할 것이기 때문에 현재 위치의 말 정보는 초기화함
				List<Integer> tmp=new ArrayList<>();	// 현재 말 아래에 있는 말들을 임시 저장
				int get;
				while(q.peek()!=i) {	// i번 말부터 그 위에 놓인 말들만 덱에 저장
					get=q.poll();
					tmp.add(get);
				}
				queue[r][c].addAll(tmp);	// i번 말 아래에 있는 말들은 이동하지 않을 것이기 때문에 현재 위치에 다시 넣어줌 
				move(i, q);
				for(int j=1;j<=K;j++) {	// 말이 4개 이상 쌓인 경우 게임 종료
					if(queue[horses[j].r][horses[j].c].size()>=4) return cnt;
				}
			}
		}
		
		return -1;	// 반복문을 빠져나왔다는 것은 1000번 내에 말이 4개 이상 쌓일 수 없다는 것이므로 -1 리턴
	}
	
	private static void move(int x, Deque<Integer> q) {
		int r=horses[x].r;
		int c=horses[x].c;
		int dir=horses[x].dir;
		int nx=r+dx[dir];
		int ny=c+dy[dir];
		
		if(!isIn(nx, ny)) {	// 범위를 벗어남
			horses[x].dir=change(dir);	// 방향을 전환
			dir=horses[x].dir;
			nx=r+dx[dir];
			ny=c+dy[dir];
			if(board[nx][ny]==2) {	// 새로운 방향에 파란색이 있으면 이동하지 않음
				queue[r][c].addAll(q);
				return;
			}
			else move(x, q);	// 새로운 방향으로 이동함
		} else {
			int color=board[nx][ny];
					
			if(color==0) {	// 흰
				while(!q.isEmpty()) {
					int get=q.poll();
					queue[nx][ny].add(get);
					horses[get]=new Horse(nx, ny, horses[get].dir);
				}
			} else if(color==1) {	// 빨
				while(!q.isEmpty()) {
					int get=q.pollLast();
					queue[nx][ny].add(get);
					horses[get]=new Horse(nx, ny, horses[get].dir);
				}
			} else if(color==2) {	// 파
				horses[x].dir=change(dir);		// 방향을 전환
				dir=horses[x].dir;
				nx=r+dx[dir];
				ny=c+dy[dir];
				if(!isIn(nx, ny)) {	// 새로운 방향이 범위를 벗어나면 이동하지 않음
					queue[r][c].addAll(q);
					return;
				}
				else if(board[nx][ny]==2) {	// 새로운 방향에 파란색이 있으면 이동하지 않음
					queue[r][c].addAll(q);
					return;
				}
				else move(x, q);	// 새로운 방향으로 이동함
			}
		}
	}
	
	private static int change(int dir) {	// 방향 전환
		if(dir==1) return 2;
		else if(dir==2) return 1;
		else if(dir==3) return 4;
		else return 3;
	}
	private static boolean isIn(int r, int c) {
		return r>=1 && r<=N && c>=1 && c<=N;
	}
}

1. K개 말의 정보를 저장할 클래스 구현

2. 체스판의 색깔 정보를 저장할 2차원 배열과 체스판에 놓인 말의 번호를 저장할 덱 구현

말이 한 칸에 여러 개 쌓일 수 있으며, 쌓인 순서도 고려해주어야 하므로 덱을 이용하였습니다.

3. 색깔별로 이동 메서드 구현

3-1. 현재 말부터 위에 존재하는 모든 말들을 함께 이동시켜줍니다.

3-2. 흰색은 순방향, 빨간색은 역방향으로 말의 쌓인 순서를 변경합니다.

3-3. 파란색이나 범위가 벗어난 경우는 방향 전환 메서드를 이용하여 한번 더 이동할 방향을 구해줍니다.

4. 1000번 이내에 말 4개가 쌓이게 되는 경우가 발생하면 현재 턴을 리턴합니다.

한번에 구현을 성공하는 것이 아직은 많이 어렵습니다 ㅠㅠㅠ

체스판에서 색깔과 말을 각각 관리해주는 방식을 생각해내는 것이 중요했고, 색깔별로 조건을 빠짐없이 고려하여 이동을 구현해내야 하는 문제였습니다.

'코딩테스트 > 구현(Implementation)' 카테고리의 다른 글

[Java] 백준 1138번 : 한 줄로 서기 (0)	2022.05.30
[Java] 백준 17822번 : 원판 돌리기 (0)	2022.04.30
[Java] 백준 20056번 : 마법사 상어와 파이어볼 (0)	2022.04.27
[Java] 백준 17143번 : 낚시왕 (0)	2022.04.23
[Java] 백준 21608번 : 상어 초등학교 (0)	2022.04.22

현재글[Java] 백준 17837번 : 새로운 게임 2

sujin's 개발 로그