https://www.acmicpc.net/problem/17837
17837번: 새로운 게임 2
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하
www.acmicpc.net
코드설명
구현(Implementation) + 시뮬레이션(Simulation) + 스택(Stack) 를 활용하는 문제입니다.
코드로직입니다.
- 말의 정보 입력:
- horse 클래스를 이용하여 각 말의 정보를 저장합니다.
- 각 말의 초기 위치와 방향 정보를 mapStack에 저장합니다.
- 게임 시뮬레이션 (simulate 함수):
- 다음 위치가 체스판을 벗어나는 경우, 혹은 파란색 칸을 만나면 방향을 먼저 변경합니다. 방향을 변경한 후 해당 말을 다시 이동하는데, 다음에도 연속적으로 막힌 벽이라면, 이동하지않습니다.(이때 bluefindflag = false로 다시 갱신시켜주어서 다음에 파란색칸을 만날때도 처리할 수 있게 합니다.) 만약 다른 벽을 만난다면 이동합니다.
- 다음 위치가 빨간색 칸인 경우, 해당 스택에서 말을 꺼내어 새로운 위치의 스택에 삽입합니다.
- 다음 위치가 흰색 칸인 경우, 해당 스택에서 순서를 지키며 말을 꺼내어 새로운 위치의 스택에 삽입합니다.
- 이동 후, 스택 크기가 4 이상인 경우 게임 종료 조건을 만족하므로 결과를 반환합니다.
- 방향 변경 함수 (changeDir 함수):
- 현재 방향을 입력으로 받아 반대 방향으로 변경하여 반환합니다.
문제에서 유의해야할점들입니다.
1. 말은 4개 이상 쌓이는경우 게임이 종료됩니다.
처음에 계속해서 92퍼센트에서 틀렸는데, 이유는 아래와 같습니다. 말의 개수는 K개로, 4개가 아닙니다. 처음에는 무조건 4개인줄알고 size() == 4 로 한점을 이상으로 수정했습니다.
if(mapStack[now.r][now.c].size() >= 4) {
return answer;
}
2. 만약 파란색 칸의 취급을 받는 칸에서 다시 파란색으로 돌아온다면, 해당칸을 다시 blueFindFlag = false로 갱신시켜주어야합니다.
처음에는 마지막에서 처리하도록 처리했지만, 파란색칸이 양옆에 있는경우 해당 칸 내에서 blueFindFlag = false로 바꿔주어 다시 파란색칸의 접촉 flag를 초기화시켜줍니다.
//범위를 벗어난다면 방향전환한 후 한칸 이동시켜야한다.
if(nr < 0 || nr >= N || nc < 0 || nc >=N) {
if(blueFindFlag == false) { //만약 처음으로 파란색을 만났을경우에는 방향을 바꾸고, 기회를 한번 더 준다.
now.dir = changeDir(now.dir);
idx -= 1;
blueFindFlag = true;
}
else if(blueFindFlag == true) {
blueFindFlag = false;
}
if(mapStack[now.r][now.c].size() >= 4) {
return answer;
}
continue;
}
3. 2차원 Stack에서는 해당 배열의 요소들을 미리 Stack() 으로 메모리선언시켜주어야합니다.
public static Stack<horse>[][] mapStack;
mapStack = new Stack[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
mapStack[i][j] = new Stack<horse>();
}
}위와 같은 제너릭을 활용하여 손쉽게 해결할 수 있습니다.
ArrayList<horse>[][] arraylist = new ArrayList[10][10];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
arraylist[i][j] = new ArrayList<horse>();
}
}
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static int N, K;
public static Stack<horse>[][] mapStack;
public static horse[] horse;
public static int[][] map;
public static int answer = 0;
public static int[] dx = {0, 0, -1, 1};
public static int[] dy = {1, -1, 0, 0};
public static int BLUE = 2;
public static int RED = 1;
public static int WHITE = 0;
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());
map = new int[N][N];
mapStack = new Stack[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
mapStack[i][j] = new Stack<horse>();
}
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
horse = new horse[K+1];
//말의 정보
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[i] = new horse(r-1, c-1, i, dir-1);
mapStack[r-1][c-1].add(horse[i]); //서로 주소값으로 연결되어있다.
}
answer = simulate();
if(answer >= 1000)
System.out.println(-1);
else
System.out.println(answer);
}
public static int simulate() {
//1번부터 K번까지.
while(++answer <= 1000) {
boolean blueFindFlag = false;
for(int idx = 1; idx <= K; idx++) {
horse now = horse[idx];
// System.out.println("idx:"+idx+"=========================");
// System.out.println("nowInfo now r: "+ now.r+"now.c" + now.c+ " now.num:"+now.num +"now.dir:"+now.dir);
//다음칸이 무엇인지 파악합니다.
int nr = now.r + dx[now.dir];
int nc = now.c + dy[now.dir];
//범위를 벗어난다면 방향전환한 후 한칸 이동시켜야한다.
if(nr < 0 || nr >= N || nc < 0 || nc >=N) {
if(blueFindFlag == false) { //만약 처음으로 파란색을 만났을경우에는 방향을 바꾸고, 기회를 한번 더 준다.
now.dir = changeDir(now.dir);
idx -= 1;
blueFindFlag = true;
}
else if(blueFindFlag == true) {
blueFindFlag = false;
}
if(mapStack[now.r][now.c].size() >= 4) {
return answer;
}
continue;
}
else if(map[nr][nc] == BLUE) { //만약 파란색칸일경우 방향전환한후 한칸 이동시켜야한다.
if(blueFindFlag == false) { //만약 처음으로 파란색을 만낫을 경우에는 방향을 바꾸고 기회를 한번 더준다.
now.dir = changeDir(now.dir);
idx -= 1;
blueFindFlag = true;
}
else if(blueFindFlag == true) {
blueFindFlag = false;
}
if(mapStack[now.r][now.c].size() >= 4) {
return answer;
}
continue;
}
//빨간색칸일경우. 해당 Stack에서 내가 찾고자하는 현재 idx가 나올때까지 값을 모두 다음 Stack값에 바로 넣어버립니다.
else if(map[nr][nc] == RED) {
while(true) {
horse popTemp = mapStack[now.r][now.c].pop();
// System.out.println("popTemp"+popTemp.num);
popTemp.r = nr; popTemp.c = nc;
mapStack[nr][nc].add(popTemp);
if(popTemp.num == idx) { //만약 찾고자하는 값을 찾았다면 그곳에서 중단시킨다.
break;
}
}
if(mapStack[nr][nc].size() >= 4) {
return answer;
}
}
//흰색칸일경우., 순서를 지키면서 이동시킨다.
else if(map[nr][nc] == WHITE) {
Stack<horse> newStack = new Stack<>();
while(true) {
horse popTemp = mapStack[now.r][now.c].pop();
popTemp.r = nr; popTemp.c = nc;
newStack.add(popTemp);
if(popTemp.num == idx) { //만약 찾고자하는 값을 찾았다면 그곳에서 중단시킨다.
break;
}
}
while(!newStack.isEmpty()) {
horse newPopTemp = newStack.pop();
mapStack[nr][nc].add(newPopTemp);
}
if(mapStack[nr][nc].size() >= 4) {
return answer;
}
}
blueFindFlag = false; //만약 다음칸에 이동을 성공할경우 푸른색칸 기호가 사라진다.
}
}
return answer;
}
public static int changeDir(int dir) {
if(dir == 0) return 1;
else if(dir == 1) return 0;
else if(dir == 2) return 3;
else if(dir == 3) return 2;
//여기까지 올일없음.
return -1;
}
}
class horse{
int r;
int c;
int num;
int dir;
public horse(int r, int c, int num, int dir) {
this.r = r;
this.c = c;
this.num = num;
this.dir = dir;
}
}