알고리즘 풀이/Java
[알고리즘] 새로운 게임 2
Dong's Universe
2024. 3. 19. 22:36
https://www.acmicpc.net/problem/17837
17837번: 새로운 게임 2
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하
www.acmicpc.net
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static int[] dr = {0, 0, -1, 1};
static int[] dc = {1, -1, 0, 0};
static int[][] map;
static Deque<Horse>[][] horse;
static int N;
static int K;
static int[][] loc;
static int cnt;
static Deque<Horse> temp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
loc = new int[K + 1][2];
map = new int[N + 1][N + 1];
horse = new Deque[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
horse[i][j] = new ArrayDeque<>();
}
}
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
map[i][j] = 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());
horse[r][c].add(new Horse(i, dir-1));
loc[i] = new int[]{r, c};
}
cnt = 1;
while (cnt <= 1000) {
if (playGame()) {
System.out.println(cnt);
return;
}
cnt++;
}
System.out.println(-1);
}
private static boolean playGame() {
for (int i = 1; i <= K; i++) {
int r = loc[i][0];
int c = loc[i][1];
temp = new ArrayDeque<>();
Deque<Horse> horses = horse[r][c];
while (true) {
Horse horse = horses.pollFirst();
temp.add(horse);
if (horse.id == i) {
break;
}
}
Horse cur = temp.getLast();
int nr = r + dr[cur.dir];
int nc = c + dc[cur.dir];
// 파란색 or 넘을때
if (!(1 <= nr && nr <= N && 1 <= nc && nc <= N) || map[nr][nc] == 2) {
int newDir;
if (cur.dir <= 1) {
newDir = 1 - cur.dir;
} else {
newDir = 5 - cur.dir;
}
nr = r + dr[newDir];
nc = c + dc[newDir];
temp.getLast().dir = newDir;
if (!(1 <= nr && nr <= N && 1 <= nc && nc <= N) || map[nr][nc] == 2){
while (!temp.isEmpty()) {
Horse hor = temp.pollLast();
horse[r][c].addFirst(hor);
}
continue;
}
if (map[nr][nc] == 0) {
while (!temp.isEmpty()) {
Horse hor = temp.pollLast();
horse[nr][nc].addFirst(hor);
loc[hor.id] = new int[]{nr, nc};
}
if (horse[nr][nc].size() >= 4) {
return true;
}
} else {
while (!temp.isEmpty()) {
Horse hor = temp.pollFirst();
horse[nr][nc].addFirst(hor);
loc[hor.id] = new int[]{nr, nc};
}
if (horse[nr][nc].size() >= 4) {
return true;
}
}
}
// 흰색
else if (map[nr][nc] == 0) {
while (!temp.isEmpty()) {
Horse hor = temp.pollLast();
horse[nr][nc].addFirst(hor);
loc[hor.id] = new int[]{nr, nc};
}
if (horse[nr][nc].size() >= 4) {
return true;
}
}
// 빨간색
else {
while (!temp.isEmpty()) {
Horse hor = temp.pollFirst();
horse[nr][nc].addFirst(hor);
loc[hor.id] = new int[]{nr, nc};
}
if (horse[nr][nc].size() >= 4) {
return true;
}
}
}
return false;
}
private static void print() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
System.out.print(horse[i][j]);
}
System.out.println();
}
}
static class Horse {
int id;
int dir;
public Horse(int id, int dir) {
this.id = id;
this.dir = dir;
}
@Override
public String toString() {
return
"id=" + id +
", dir=" + dir
;
}
}
}나의 풀이
- 문제를 잘못 이해하여 거의 1시간 30분을 날렸다.
- 이게 파란색일때 이동을 하면 흰색, 빨간색이어서 그에 따라 바꿔줘야 하는데 그걸 고려를 안하고 무조건 흰색처럼 되게 했다.
- 이런 오류는 어떻게 잡아야 할까? 도저히 생각이 안나는데.
- 이런 건 경험인 거 같기도 하다.
이건 리팩토링한 코드
- 이동할 칸이 파란색이라면 방향만 바꿔주고 나머지는 동일하게 진행하면 된다.
package baekjoon.solution17837;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static int[] dr = {0, 0, -1, 1};
static int[] dc = {1, -1, 0, 0};
static int[][] map;
static Deque<Horse>[][] horse;
static int N;
static int K;
static int[][] loc;
static int cnt;
static Deque<Horse> temp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
loc = new int[K + 1][2];
map = new int[N + 1][N + 1];
horse = new Deque[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
horse[i][j] = new ArrayDeque<>();
}
}
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
map[i][j] = 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());
horse[r][c].add(new Horse(i, dir-1));
loc[i] = new int[]{r, c};
}
cnt = 1;
while (cnt <= 1000) {
if (playGame()) {
System.out.println(cnt);
return;
}
cnt++;
}
System.out.println(-1);
}
private static boolean playGame() {
for (int i = 1; i <= K; i++) {
int r = loc[i][0];
int c = loc[i][1];
temp = new ArrayDeque<>();
Deque<Horse> horses = horse[r][c];
while (true) {
Horse horse = horses.pollFirst();
temp.add(horse);
if (horse.id == i) {
break;
}
}
Horse cur = temp.getLast();
int nr = r + dr[cur.dir];
int nc = c + dc[cur.dir];
// 파란색 or 넘을때
if (!(1 <= nr && nr <= N && 1 <= nc && nc <= N) || map[nr][nc] == 2) {
int newDir;
if (cur.dir <= 1) {
newDir = 1 - cur.dir;
} else {
newDir = 5 - cur.dir;
}
nr = r + dr[newDir];
nc = c + dc[newDir];
temp.getLast().dir = newDir;
}
if (!(1 <= nr && nr <= N && 1 <= nc && nc <= N) || map[nr][nc] == 2){
while (!temp.isEmpty()) {
Horse hor = temp.pollLast();
horse[r][c].addFirst(hor);
}
}
else if (map[nr][nc] == 0) {
while (!temp.isEmpty()) {
Horse hor = temp.pollLast();
horse[nr][nc].addFirst(hor);
loc[hor.id] = new int[]{nr, nc};
}
if (horse[nr][nc].size() >= 4) {
return true;
}
} else {
while (!temp.isEmpty()) {
Horse hor = temp.pollFirst();
horse[nr][nc].addFirst(hor);
loc[hor.id] = new int[]{nr, nc};
}
if (horse[nr][nc].size() >= 4) {
return true;
}
}
}
return false;
}
private static void print() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
System.out.print(horse[i][j]);
}
System.out.println();
}
}
static class Horse {
int id;
int dir;
public Horse(int id, int dir) {
this.id = id;
this.dir = dir;
}
@Override
public String toString() {
return
"id=" + id +
", dir=" + dir
;
}
}
}