백준 23290 - 마법사 상어와 복제
Updated:
Java
23290 번 - 새로운 게임
문제
접근 방법
주의해야할 조건
- 4 * 4 격자
- 물고기는 8방향으로 이동 ( ←, ↖, ↑, ↗, →, ↘, ↓, ↙ )
- 물고기와 상어가 중첩될 수 있다.
- 물고기 냄새는 상어가 물고기를 제외한 곳에서만 생성
- 상어가 3칸 이동할 때 중복해서 물고기를 카운트 하면 안된다 ex) 우 => 하 => 상
동작
- (복제할)모든 물고기가 이동 ( 상어, 냄새, 범위 밖 이동 불가)
- 현재 방향이 이동 불가 위치면 45도 회전(반시계)
- 이동 불가면 그 자리에서 고정
- 상어는 3칸을 이동( 상, 하, 좌, 우 ) ( 범위 밖 이동 불가)
- 가는 방향 중, 물고기가 많은 곳으로 간다. ( 방법이 여러가지면 사전 순)
- 그 위치의 물고기는 물고개 냄새를 남긴다
- 2번전 연습에서 생긴 냄새는 사라진다.
- 새로운 물고기들이 복제된다. 1번 상태의 물고기가 원래 있던 자리에 생성되는 것이다.
구현
- 물고기의 상태를 나타내는건, 4*4 Queue<int(방향)>이다.
- 이동하기 전, 물고기의 상태를 나타내야 하므로, 이전 상태를 저장할 4*4 Queue
에 백업 - 이동해야할 물고기의 수를 세야하므로, 각 칸마다 물고기의 수를 센다 4*4 int 배열
- 각 칸에 위 배열의 값 만큼, 물고기를 이동한다.(반시계)
- 물고기 한마리를 poll 하고, 이동할 칸에 add 한다.
- 이동하기 전, 물고기의 상태를 나타내야 하므로, 이전 상태를 저장할 4*4 Queue
- 상어의 이동
- permutation을 사용하여 이동할 수 있는 모든 경우의 수를 구한다.
상상상부터 시작하여우우우까지 DFS 돌려보며, 가장 물고기의 수가 많으면 그 이동 방향 3개를 기록, 물고기가 더 큰수가 나오면 갱신. -> 상상상 부터 시작하므로, 처음 갱신된게 가장 사전순에 빠름- 상어가 이동하고, 이동하는 칸은 empty로 만든다.
- 그리고 그 칸은 냄새로 기록
- 냄새를 나타내는 4*4 queue 배열 <int(순서)>
- 상어가 지나가서 냄새가 발생하면, 그 자리에 add(현재 연습 순서)
- 3번째 연습 부터, 각 칸을 탐색하며 현재 연습 순서 -2 인 값을 peek() 하여 찾아 poll()한다.
- 백업한 Queue 배열을 가져와 물고기를 다시 생성한다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, result, maxCnt;
static int sY, sX;
static List<List<Queue<Integer>>> fish;
static List<List<Queue<Integer>>> bak;
static List<List<Queue<Integer>>> smell;
static int[][] fishCnt;
static int[] sel, nextMove;
static boolean[][] vis;
// 상 좌 하 우
static int[] dSy = new int[] {-1,0,1,0};
static int[] dSx = new int[] {0,-1,0,1};
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());
int turn = stoi(stk.nextToken());
// init
fish = new ArrayList<List<Queue<Integer>>>();
bak = new ArrayList<List<Queue<Integer>>>();
smell = new ArrayList<List<Queue<Integer>>>();
for(int i = 0; i < 4; i++) {
fish.add(new ArrayList<Queue<Integer>>());
bak.add(new ArrayList<Queue<Integer>>());
smell.add(new ArrayList<Queue<Integer>>());
for(int j = 0; j < 4; j++) {
fish.get(i).add(new LinkedList<Integer>());
bak.get(i).add(new LinkedList<Integer>());
smell.get(i).add(new LinkedList<Integer>());
}
}
int inputY,inputX,inputDir;
boolean isMoved;
for(int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
inputY = stoi(stk.nextToken()) - 1;
inputX = stoi(stk.nextToken()) - 1;
inputDir = stoi(stk.nextToken()) - 1;
fish.get(inputY).get(inputX).add(inputDir); // 물고기 추가
}
// 상어의 상태 기록
stk = new StringTokenizer(br.readLine());
sY = stoi(stk.nextToken()) - 1;
sX = stoi(stk.nextToken()) - 1;
// ←, ↖, ↑, ↗, →, ↘, ↓, ↙
int[] dy = {0,-1,-1,-1,0,1,1,1};
int[] dx = {-1,-1,0,1,1,1,0,-1};
sel = new int[3];
nextMove = new int[3]; // 다음 상어가 움직일 방향
// 턴 시작
int curT = 1, curFish, lastTurn;
while(curT <= turn) {
// 백업, 및 물고기 세기
fishCnt = new int[4][4];
for(int y = 0; y < 4; y++) {
for(int x = 0; x < 4; x++) {
bak.get(y).get(x).clear();
fishCnt[y][x] = fish.get(y).get(x).size();
for(int k = 0; k < fishCnt[y][x]; k++) {
curFish = fish.get(y).get(x).poll();
bak.get(y).get(x).add(curFish);
fish.get(y).get(x).add(curFish);
}
}
}
// 물고기의 이동
int ny = -1, nx, nDir;
for(int y = 0; y < 4; y++) {
for(int x = 0; x < 4; x++) {
for(int k = 0; k < fishCnt[y][x]; k++) {
curFish = fish.get(y).get(x).poll(); // 이동할 물고기를 하나 가져온다
isMoved = false;
// 반 시계 방향으로 돌린다.
for(int dir = 0; dir < 8; dir++) {
nDir = curFish - dir;
if(nDir < 0)
nDir += 8;
ny = y + dy[nDir];
nx = x + dx[nDir];
// 범위 내부이고, 물고기의 냄새가 없고, 상어가 있는 곳이 아니면
if(isIn(ny,nx) && smell.get(ny).get(nx).isEmpty() && !withShark(ny, nx)) {
fish.get(ny).get(nx).add(nDir);
isMoved = true;
break;
}
}
// 이동할 수 있는 칸이 없으면 이동을 하지 않는다
if(!isMoved)
fish.get(y).get(x).add(curFish);
}
}
}
// 상어의 이동
// 물고기의 수를 다시 센다
for(int y = 0; y < 4; y++) {
for(int x = 0; x < 4; x++) {
fishCnt[y][x] = fish.get(y).get(x).size();
}
}
maxCnt = -1;
DFS(0); // 상어가 움직일 방향을 정한다.
// 상어가 이동하고,
for(int dir : nextMove) {
sY += dSy[dir];
sX += dSx[dir];
if(!fish.get(sY).get(sX).isEmpty()) {
smell.get(sY).get(sX).add(curT); //물고기가 죽은 칸은 냄새로 기록
}
fish.get(sY).get(sX).clear(); // 이동하는 칸의 물고기는 empty로 만든다.
}
// 백업한 물고기를 가져온다
for(int y = 0; y < 4; y++) {
for(int x = 0; x < 4; x++) {
while(!bak.get(y).get(x).isEmpty()) {
fish.get(y).get(x).add(bak.get(y).get(x).poll());
}
}
}
if(curT >= 3) {
lastTurn = curT - 2;
// 3번째 연습 부터 2단계 전의 연습 때 발생한 냄새를 제거한다.
for(int y = 0; y < 4; y++) {
for(int x = 0; x < 4; x++) {
if(!smell.get(y).get(x).isEmpty() && smell.get(y).get(x).peek() == lastTurn) {
smell.get(y).get(x).poll();
}
}
}
}
curT++; // 다음 연습 횟수
}
// 최종 물고기의 수를 센다
int result = 0;
for(int y = 0; y < 4; y++) {
for(int x = 0; x < 4; x++) {
result += fish.get(y).get(x).size();
}
}
System.out.println(result);
br.close();
}
// 상어가 움직일 수 있는 모든 방향을 구한다.
public static void DFS(int lv) {
if(lv == 3) {
// 범위를 벗어나지 않고, 이전 방향보다 개수가 많으면
int rst = cntEatFish();
if(rst != -1 && maxCnt < rst) {
maxCnt = rst;
nextMove = sel.clone(); // 다음 움직일 방향 갱신
}
return;
}
for(int i = 0; i < 4; i++) {
sel[lv] = i;
DFS(lv + 1);
}
}
// 상어가 이동하며 먹을 수 있는 물고기의 수를 센다.
public static int cntEatFish() {
int cnt = 0;
int y = sY;
int x = sX;
int ny,nx;
vis = new boolean[4][4];
for(int dir : sel) {
ny = y + dSy[dir];
nx = x + dSx[dir];
if(!isIn(ny,nx)) {
return -1;
}
if(!vis[ny][nx])
cnt += fishCnt[ny][nx];
if(fishCnt[ny][nx] > 0)
vis[ny][nx] = true;
y = ny;
x = nx;
}
return cnt;
}
// 주어진 범위 안에 있는가
public static boolean isIn(int y, int x){
if(y < 0 || y >= 4 || x < 0 || x >= 4)
return false;
return true;
}
// 해당 자리에 상어가 있는지
public static boolean withShark(int y, int x){
if(sY == y && sX == x)
return true;
return false;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
후기
자잘한 실수가 많았으며, else if의 부재, break문 위치
종료 조건을 제대로 읽지 않아 시간이 걸렸던 문제이다.
이런 구현 문제는 1시간 30분을 잡고 집중해서 푸는 습관을 길러야겠다.
