[백준 17837번] 새로운 게임 2 (java)

17837번: 새로운 게임 2

 

다른 삼성역량테스트 문제에 비해 쉬운 편이었으나, 문제를 잘못 이해해서 몇시간을 삽질했다.

이동하려는 위치가 파란색이면, 방향을 바꾸고 반대편으로 이동해야 한다.

이 때, 반대편이 파란색이라면 이동하지 않는다.

여기까지는 제대로 이해했는데, 만약 반대편이 흰색이나 빨간색이면 A번 말 혼자만 이동하는 것이 아니라

A번 위에 있던 말들까지 같이 이동해야 한다. 하지만 문제에는 이 부분에 대해서는 설명이 생략되어 있어서 나는 계속 A번 말 혼자서만 이동시켰다.

 

이 부분을 해결하고나니 '맞았습니다' 가 떴다.

 

 

생성한 변수

내가 문제를 해결하기 위해 선언한 변수들은 다음과 같다.

 

1. 칸의 색 정보를 담는 board 2차원 배열을 생성했다.

    int[][] board = new int[N+1][N+1];

 

2. 각각의 체스칸 위에 어떤 말들이 올라가있는지 정보를 담는 pos 2차원 배열을 만들었다.

   단, 각각의 칸마다 여러 말들을 저장할 수 있게 Vector<Integer> 형으로 선언하였다.

   특정 칸(r,c)에 n번 말이 올라간다고 하면, pos[r][c].add(n)를 통해 말의 번호를 추가하였다.

   Vector<Integer>[][] pos = new Vector[N+1][N+1];

 

3. 각각의 말마다 현재 위치(r,c)와 방향(d) 정보를 저장하기 위해 Mal 이라는 클래스를 하나 생성했다.

   그리고 말의 개수가 K개이므로 K+1개만큼의 Mal 배열을 만들었다.

   Mal[] mal = new Mal[K+1];

   mal[i] = new Mal(r, c, d);

public static class Mal {

	int r, c, d;

	Mal(int r, int c, int d) {

		this.r = r;
		this.c = c;
		this.d = d;
	}
}

 

알고리즘

1. 1번 말부터 K번 말까지 반복문을 통해 차례대로 이동한다.

    i번 째 말의 다음에 이동할 위치를 미리 구한다. (r, c) -> (nr, nc)

    이 때, 방향 정보를 저장하는 int[] mr = { 0, 0, 0, -1, 1 }; int[] mc = { 0, 1, -1, 0, 0 }; 배열을 만들어서

    i번째 말의 방향 정보 d를 인덱스로 한다. 

   

    nr = r + mr[d];

    nc = c + mc[d];

 

2. 이동할 위치의 체스칸(board[r][c])이 흰색일 때, 빨간색일 때, 파란색 일 때를 조건문을 나눈다. 

if ((nr < 1 || nr > N) || (nc < 1 || nc > N) || board[nr][nc] == 2) {
   // 체스판을 벗어나거나, 파란색인 경우
}

if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && board[nr][nc] == 0) {
   // 흰색인 경우
}

else if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && board[nr][nc] == 1) {
   // 빨간색인 경우
}

   2-1. 체스판을 벗어나거나, 파란색인 경우 : 

         방향을 반대로 바꾸고 반대 방향으로 한 칸 이동한 위치로 (nr, nc)를 변경한다.

         이렇게 변경된 (nr, nc)는 다음의 if문과 else if문에서 흰색이냐 빨간색이냐에 따라 행동을 달리 한다.

if ((nr < 1 || nr > N) || (nc < 1 || nc > N) || board[nr][nc] == 2) {
	int d = changeDirect(m.d); // 방향 반대로 바꿈
	nr = m.r + mr[d]; // 방향 바뀐 후, 반대쪽으로 한칸 이동한 위치
	nc = m.c + mc[d];

	m.d = d;
}

 

   2-2. 흰색인 경우 : 

         현재 i번째 말의 위치(r, c)에 존재하는 말들의 정보는 pos[r][c]에 있다.

         따라서 pos[r][c]의 Vector의 원소를 반복문을 통해 돌면서 i번째 말부터 그 위에 있는 모든 말들을

         새로운 위치의 pos[nr][nc]에 추가해준다.

         그리고 pos[r][c]에는 이동을 완료한 말들의 번호는 제거해준다.(이동했으므로)

if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && board[nr][nc] == 0) {

	List<Integer> tmp = new ArrayList<>();
	boolean flag = false;

	for (int n : pos[m.r][m.c]) { // 원래 위치에서 vector에서 저장된 아래에 말부터 꺼냄
		if (n == i)
			flag = true;

		if (flag) {
			pos[nr][nc].add(n);
			tmp.add(n);
		}
	}

	for (int n : tmp) {
		pos[mal[n].r][mal[n].c].remove((Integer) n);
		mal[n].r = nr;
		mal[n].c = nc;
	}
}

 

   2-3. 빨간색인 경우 : 

         현재 i번째 말의 위치(r, c)에 존재하는 말들의 정보는 pos[r][c]에 있다.

         따라서 pos[r][c]의 Vector의 원소를 반복문을 통해 돌면서 i번째 말부터 그 위에 있는 모든 말들을

         새로운 위치의 pos[nr][nc]에 추가해준다.

         단, 이번에는 가장 위에 있는 말부터 이동할 위치에 추가해야 하므로, 2-2와 달리 pos[r][c]의 원소를

         역순으로 접근해준다.

         그리고 원래 있던 pos[r][c]에는 이동을 완료한 말들의 번호는 제거해준다.

else if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && board[nr][nc] == 1) {

	List<Integer> tmp = new ArrayList<>();

	for (int j = pos[m.r][m.c].size() - 1; j >= 0; j--) {
		int n = pos[m.r][m.c].get(j);

		pos[nr][nc].add(n);
		tmp.add(n);

		if (n == i)
			break;
	}

	for (int n : tmp) {
		pos[mal[n].r][mal[n].c].remove((Integer) n);
		mal[n].r = nr;
		mal[n].c = nc;
	}
}

 

         

3. 하나의 말이 이동을 마칠 때마다 4개 이상의 말들이 같은 위치에 있는지를 확인해줘야 한다.

   말들의 위치를 하나씩 확인하면서, 그 위치에 말들의 개수가 4개 이상인 경우가 있는지 확인한다.

for (int k = 1; k <= K; k++) {
	if (pos[mal[k].r][mal[k].c].size() >= 4)
		return cnt;
}

 

4. 1번 말부터 K번 말까지 모두 이동을 마지면, 다시 1번으로 돌아가서 새로운 턴을 시작한다.

   하나의 턴을 마쳤으므로 cnt를 하나 증가시킨다.

   만약, cnt>1000이면 불가능한 경우이므로 -1를 반환하고 종료한다.

 

 

 

전체 코드 : 

	import java.io.*;
	import java.util.*;
	public class n17837 {
	static int N, K;
	static int[][] board;
	static Vector<Integer>[][] pos; // 0번으로 갈수록 아래에 있고, 번호가 커질수록 위에 있음
	static Mal[] mal;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] input = br.readLine().split(" ");
	N = Integer.parseInt(input[0]);
	K = Integer.parseInt(input[1]);
	board = new int[N + 1][N + 1];
	mal = new Mal[K + 1];
	pos = new Vector[N + 1][N + 1];
	for (int i = 1; i <= N; i++) {
	input = br.readLine().split(" ");
	for (int j = 1; j <= N; j++) {
	board[i][j] = Integer.parseInt(input[j - 1]);
	pos[i][j] = new Vector<>();
	}
	}
	for (int i = 1; i <= K; i++) {
	input = br.readLine().split(" ");
	int r = Integer.parseInt(input[0]);
	int c = Integer.parseInt(input[1]);
	int d = Integer.parseInt(input[2]);
	mal[i] = new Mal(r, c, d);
	pos[r][c].add(i);
	}
	bw.write(solve() + "\n");
	bw.flush();
	}
	public static int solve() {
	int[] mr = { 0, 0, 0, -1, 1 };
	int[] mc = { 0, 1, -1, 0, 0 };
	int cnt = 0;
	while (true) {
	if (cnt > 1000)
	return -1;
	cnt++;
	for (int i = 1; i <= K; i++) {
	Mal m = mal[i];
	int nr = m.r + mr[m.d];
	int nc = m.c + mc[m.d];
	if ((nr < 1 || nr > N) || (nc < 1 || nc > N) || board[nr][nc] == 2) {
	int d = changeDirect(m.d); // 방향 반대로 바꿈
	nr = m.r + mr[d]; // 방향 바뀐 후, 반대쪽으로 한칸 이동한 위치
	nc = m.c + mc[d];
	m.d = d;
	}
	if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && board[nr][nc] == 0) {
	List<Integer> tmp = new ArrayList<>();
	boolean flag = false;
	for (int n : pos[m.r][m.c]) { // 원래 위치에서 vector에서 저장된 아래에 말부터 꺼냄
	if (n == i)
	flag = true;
	if (flag) {
	pos[nr][nc].add(n);
	tmp.add(n);
	}
	}
	for (int n : tmp) {
	pos[mal[n].r][mal[n].c].remove((Integer) n);
	mal[n].r = nr;
	mal[n].c = nc;
	}
	}
	else if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && board[nr][nc] == 1) {
	List<Integer> tmp = new ArrayList<>();
	for (int j = pos[m.r][m.c].size() - 1; j >= 0; j--) {
	int n = pos[m.r][m.c].get(j);
	pos[nr][nc].add(n);
	tmp.add(n);
	if (n == i)
	break;
	}
	for (int n : tmp) {
	pos[mal[n].r][mal[n].c].remove((Integer) n);
	mal[n].r = nr;
	mal[n].c = nc;
	}
	}
	for (int k = 1; k <= K; k++) {
	if (pos[mal[k].r][mal[k].c].size() >= 4)
	return cnt;
	}
	}
	}
	}
	public static int changeDirect(int i) {
	if (i == 1)
	return 2;
	else if (i == 2)
	return 1;
	else if (i == 3)
	return 4;
	else
	return 3;
	}
	public static class Mal {
	int r, c, d;
	Mal(int r, int c, int d) {
	this.r = r;
	this.c = c;
	this.d = d;
	}
	}
	}

view raw 17837.java hosted with ❤ by GitHub