Live Today
[백준]17837. 새로운 게임2 (Java) 본문
반응형
https://www.acmicpc.net/problem/17837
17837번: 새로운 게임 2
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하
www.acmicpc.net
- Queue는 First - In - First - Out 으로 가장 먼저 들어온 데이터가 가장 먼저 나간다.
- Queue의 2차원 배열로 처음에 구현했었는데 이렇게 하면 현재 탐색하는 말 번호와 같은 칸에 있는 말들 중, 그 위에 있는 말들이 아닌 그 아래 있는 말들이 빠져나오기 때문에 통과하지 못했다.
- 따라서 ArrayList타입으로 2차원 배열을 만들어서 for문으로 현재 탐색하는 말의 인덱스를 찾아서 그 위에 있는 말들을 담을 자료구조를 ArrayList타입으로 만들어준다.
✔️ 틀렸던 풀이
더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static int N,K,result;
// 우 좌 상 하
static int[] dx = {0,0,0,-1,1};
static int[] dy = {0,1,-1,0,0};
static int[][] board;
static Queue<Integer>[][] q;
static ArrayList<Horse> hList = new ArrayList<>();
static class Horse {
int x,y,d;
public Horse(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
board = new int[N][N];
q = new LinkedList[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
q[i][j] = new LinkedList<Integer>();
}
}
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=0;i<K;i++) { // k개의 말 정보 입력
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken())-1;
int d = Integer.parseInt(st.nextToken());
hList.add(new Horse(r, c, d));
q[r][c].add(i);
} // input end
result = solve();
System.out.println(result);
}
private static int solve() {
int turn = 1;
while(turn <= 1000) {
// 1. 1번 말부터 k번 말까지 순서대로 이동
for(int i=0;i<K;i++) {
// 현재 탐색하는 말의 번호와 상태
Horse now = hList.get(i);
int nx = now.x + dx[now.d];
int ny = now.y + dy[now.d];
if(isValid(nx, ny)) {
moveHorse(nx,ny,i);
} else { // 이동하려는 칸이 범위를 벗어난 경우 = 파란색의 경우
now.d = changeDir(now.d);
nx = now.x + dx[now.d];
ny = now.y + dy[now.d];
if(board[nx][ny] == 2) continue;
else moveHorse(nx, ny, i);
}
// 2. 4개 이상 쌓이는 순간 게임 종료
if(q[now.x][now.y].size() >= 4) return turn;
}
turn++;
}
return -1;
}
private static void moveHorse(int nx, int ny, int i) {
int x = hList.get(i).x;
int y = hList.get(i).y;
if(board[nx][ny] == 0) { // 흰색인 경우
while(!q[x][y].isEmpty()) {
int temp = q[x][y].poll();
q[nx][ny].add(temp);
hList.get(temp).x = nx;
hList.get(temp).y = ny;
}
} else if(board[nx][ny] == 1) { // 빨간색인 경우
Stack<Integer> stack = new Stack<Integer>();
int size = q[x][y].size();
for(int k=0;k<size;k++) {
stack.add(q[x][y].poll());
}
while(!stack.isEmpty()) {
int temp = stack.pop();
q[nx][ny].add(temp);
hList.get(temp).x = nx;
hList.get(temp).y = ny;
}
} else if(board[nx][ny] == 2) { // 파란색인 경우
hList.get(i).d = changeDir(hList.get(i).d);
nx = x + dx[hList.get(i).d];
ny = y + dy[hList.get(i).d];
if(isValid(nx, ny)&& board[nx][ny] != 2) {
moveHorse(nx, ny, i);
}
}
}
private static int changeDir(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 isValid(int r, int c) {
if(r<0 || c<0 || r>=N || c>=N) return false;
return true;
}
}✅ 정답 풀이
package algo;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main_bj_17837_새로운게임2 {
static int N,K,result;
// 우 좌 상 하
static int[] dx = {0,0,0,-1,1};
static int[] dy = {0,1,-1,0,0};
static int[][] board;
static ArrayList<Integer>[][] list;
static ArrayList<Horse> hList = new ArrayList<>();
static class Horse {
int x,y,d;
public Horse(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
board = new int[N][N];
list = new ArrayList[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
list[i][j] = new ArrayList<Integer>();
}
}
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=0;i<K;i++) { // k개의 말 정보 입력
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken())-1;
int d = Integer.parseInt(st.nextToken());
hList.add(new Horse(r, c, d));
list[r][c].add(i);
} // input end
result = solve();
System.out.println(result);
}
private static int solve() {
int turn = 1;
while(turn <= 1000) {
// 1. 1번 말부터 k번 말까지 순서대로 이동
for(int i=0;i<K;i++) {
// 현재 탐색하는 말의 번호와 상태
Horse now = hList.get(i);
ArrayList<Integer> up_horse = new ArrayList<>();
int start_idx = 0;
int x = now.x;
int y = now.y;
for(int p=0;p<list[x][y].size();p++) {
if(list[x][y].get(p) == i) {
start_idx = p;
break;
}
}
for(int p=start_idx;p<list[x][y].size();p++) {
up_horse.add(list[x][y].get(p));
}
int nx = now.x + dx[now.d];
int ny = now.y + dy[now.d];
if(!isValid(nx, ny) || board[nx][ny] == 2) {
hList.get(i).d = changeDir(hList.get(i).d);
nx = now.x + dx[hList.get(i).d];
ny = now.y + dy[hList.get(i).d];
if(!isValid(nx, ny) || board[nx][ny] == 2) continue;
else {
if(board[nx][ny] == 0) {
for(int h : up_horse) {
list[nx][ny].add(h);
hList.get(h).x = nx;
hList.get(h).y = ny;
}
}
else if(board[nx][ny] == 1) {
for(int p=up_horse.size()-1;p>=0;p--) {
list[nx][ny].add(up_horse.get(p));
hList.get(up_horse.get(p)).x = nx;
hList.get(up_horse.get(p)).y = ny;
}
}
}
}
else if(board[nx][ny] == 0) {
for(int h : up_horse) {
list[nx][ny].add(h);
hList.get(h).x = nx;
hList.get(h).y = ny;
}
}
else if(board[nx][ny] == 1) {
for(int p=up_horse.size()-1;p>=0;p--) {
list[nx][ny].add(up_horse.get(p));
hList.get(up_horse.get(p)).x = nx;
hList.get(up_horse.get(p)).y = ny;
}
}
// 2. 4개 이상 쌓이는 순간 게임 종료
if(list[now.x][now.y].size() >= 4) return turn;
for(int p=list[x][y].size()-1;p>=start_idx;p--) {
list[x][y].remove(p);
}
}
turn++;
}
return -1;
}
private static int changeDir(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 isValid(int r, int c) {
if(r<0 || c<0 || r>=N || c>=N) return false;
return true;
}
}
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
| [백준] 2902. KMP는 왜 KMP일까? (Java) (0) | 2023.02.12 |
|---|---|
| [백준] 1445. 일요일 아침의 데이트 (Java) (0) | 2023.02.05 |
| [백준] 2493. 탑 (Java) (0) | 2023.02.04 |
| [백준] 12919. A와B 2 (Java) (0) | 2023.02.04 |
| [백준] 1253. 좋다 (Java) (0) | 2023.01.25 |
'알고리즘/백준 문제풀이' Related Articles
more
