백준 17780 - 새로운 게임
Updated:
Java
17780 번 - 새로운 게임
문제
접근 방법
총 2개의 자료구조를 통해 문제를 해결하였다.
먼저 체스판의 색을 나타내는 2차원 int 배열을 사용하였고,
실제 말들의 위치를 나타내기 위해 nxn의 deque<int[]> 2차원 list를 사용하였다. (List<List<Deque<int[]>>>)
각 말은 중첩 될 수 있으므로, Deque을 사용하여 한 칸에 있는 말들을 나타내었다.
즉, Deque의 front가 제일 밑에 있는 말이며, 이동하는 주체가 된다.
이후 다음과 같은 동작으로 해결하였다.
- 한 턴을 시작한다. while(1000회 반복)
- nxn만큼 탐색한다. null이 아닌 deque의 크기가 4이면 종료, 턴 횟수 반환 (4마리의 말이 쌓여있는 경우)
- 1부터 k번째 말까지 하나씩 nxn deque 리스트 배열 탐색.
각 노드 값이 null이 아니며 그 deque의 peek()가 해당 말이면 동작 - 각 말이 방향에 따라 이동할 좌표를 구한다. 다음으로 갈 바닥의 색깔에 따라 다음과 같이 동작한다. (현재 위치 y,x 좌표에서 이동한 ny,nx의 체스판 색 탐색)
a. 하얀색이며 null인 곳일 때 : 해당 노드에 현재 덱 대입, 이전 노드는 null
b. 하얀색이며 null이 아닐 때 : 해당 노드를 불러와, 현재 말의 값을 하나씩 pollFirst();
c. 빨간색일 때 : deque 순서를 바꾸고(앞으로 갈 칸에 위에서 부터 하나씩 pollLast()하여 넣는다), 해당 노드에 겹치거나 이동
d. 파란색 일때(범위를 벗어 났을 때)- 해당 말의 방향을 반대로 바꾼다.
- 다시 반대방향으로 ny,nx값을 구한다
- 해당 노드가 파란색인지 아닌지 확인
-> 파란색 or 범위 외 이면 이동 x - 해당 노드에 이미 말이 존재하는지 확인
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, k, result;
static int[][] board;
static List<List<Deque<int[]>>> horses;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
n = stoi(stk.nextToken());
k = stoi(stk.nextToken());
board = new int[n][n];
for(int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
board[i][j] = stoi(stk.nextToken());
}
}
horses = new ArrayList<>();
for(int i = 0; i < n; i++) {
horses.add(new ArrayList<>());
for(int j = 0; j < n; j++) {
horses.get(i).add(null);
}
}
// 입력
int inY, inX, dir;
for(int i = 0; i < k; i++) {
stk = new StringTokenizer(br.readLine());
inY = stoi(stk.nextToken()) - 1;
inX = stoi(stk.nextToken()) - 1;
dir = stoi(stk.nextToken()) - 1;
horses.get(inY).set(inX, new ArrayDeque<>());
horses.get(inY).get(inX).add(new int[] {i + 1, dir});
}
int turn = 0, curH, ny, nx;
boolean isEnd = false;
// 우 좌 상 하
int[] dy = {0, 0, -1, 1};
int[] dx = {1, -1, 0, 0};
end : while(turn <= 999) {
// 말의 수가 1이면 종료, 턴 횟수 반환
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(horses.get(i).get(j) != null) {
if(horses.get(i).get(j).size() >= 4) {
isEnd = true;
break end;
}
}
}
}
// 1부터 k번째 말까지 하나씩 nxn deque 리스트 배열 탐색.
curH = 1;
while(curH <= k) {
next: for(int y = 0; y < n; y++) {
for(int x = 0; x < n; x++) {
// 각 노드 값이 null이 아니며 그 deque의 peek()가 해당 말이면 동작
if(horses.get(y).get(x) != null && horses.get(y).get(x).getFirst()[0] == curH) {
dir = horses.get(y).get(x).getFirst()[1];
ny = y + dy[dir];
nx = x + dx[dir];
// 파란색일 경우
if(!isIn(ny,nx) || board[ny][nx] == 2) {
// 해당 말의 방향을 반대로 바꾼다.
dir = turnDir(dir);
horses.get(y).get(x).getFirst()[1] = dir;
// 다시 반대방향으로 ny,nx값을 구한다
ny = y + dy[dir];
nx = x + dx[dir];
// 빨간색일 경우
if(isIn(ny,nx) && board[ny][nx] == 1) {
moveRed(y,x,ny,nx);
}
// 하얀색일 경우
else if(isIn(ny,nx) && board[ny][nx] == 0) {
moveWhite(y,x, ny,nx);
}
}
else if(board[ny][nx] == 1) { // 빨간색일 경우
moveRed(y,x,ny,nx);
}
else { // 하얀색일 경우
moveWhite(y,x, ny,nx);
}
// 해당 말을 찾고, 이동하였으므로 종료한다.
break next;
}
}
}
curH++;
}
turn++;
}
System.out.println(isEnd ? turn : -1);
br.close();
}
// 빨간색 칸으로 갈 때
public static void moveRed( int y, int x, int ny, int nx) {
Deque<int[]> temp;
// 앞으로 갈 곳이 비어있을 때
if(horses.get(ny).get(nx) == null) {
temp = horses.get(y).get(x);
horses.get(ny).set(nx, new ArrayDeque<int[]>());
while(!temp.isEmpty()) {
horses.get(ny).get(nx).add(temp.pollLast());
}
}
else {
temp = horses.get(y).get(x);
while(!temp.isEmpty()) {
horses.get(ny).get(nx).add(temp.pollLast());
}
}
horses.get(y).set(x, null);
}
// 하얀색 칸으로 갈 때
public static void moveWhite( int y, int x, int ny, int nx) {
Deque<int[]> temp;
// 앞으로 갈 곳이 비어있을 때
if(horses.get(ny).get(nx) == null) {
horses.get(ny).set(nx, horses.get(y).get(x));
}
// 다른 말이 있는 경우
else {
temp = horses.get(y).get(x);
while(!temp.isEmpty()) {
horses.get(ny).get(nx).add(temp.pollFirst());
}
}
horses.get(y).set(x, null);
}
public static int turnDir(int dir) {
if(dir == 1) // 좌
dir = 0;
else if(dir == 0) // 우
dir = 1;
else if(dir == 2) // 상
dir = 3;
else if(dir == 3) // 하
dir = 2;
return dir;
}
// 주어진 범위 안에 있는가
public static boolean isIn(int y, int x){
if(y < 0 || y >= n || x < 0 || x >= n)
return false;
return true;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
후기
자잘한 실수가 많았으며, else if의 부재, break문 위치
종료 조건을 제대로 읽지 않아 시간이 걸렸던 문제이다.
이런 구현 문제는 1시간 30분을 잡고 집중해서 푸는 습관을 길러야겠다.
