4×4 크기의 공간이 1×1 크기의 정사각형으로 나누어져 있다. 각 칸에는 물고기가 한 마리씩 존재하며 각 물고기는 1~16번까지 고유 번호와 (상하좌우, 대각선) 방향을 가지고 있다.
청소년 상어는 `0, 0`칸에 들어가 해당 칸에 있는 물고기를 잡아먹고 해당 물고기의 방향을 갖게 된다. 그 후 물고기의 이동과 청소년 상어의 이동이 반복된다.
물고기는 1번 물고기부터 본인의 방향으로 1칸 이동한다. 다만 이동할 수 없을 경우(구역 밖, 상어가 있는 칸) 반시계 방향으로 45°회전한다. 이동 가능한 칸에 다른 물고기가 있으면 해당 칸에 물고기와 자리를 바꾼다.
모든 물고기의 이동이 끝이 나면 청소년 상어가 이동한다. 상어는 현재 이동 방향으로 거리 상관없이 이동 가능하다. 여러 칸을 이동할 경우 건너뛴 칸에 있는 물고기는 먹지 않는다. 물고기를 잡아먹으면 잡아먹은 물고기의 방향을 갖게 되고 턴을 종료한다.
상어가 먹을 수 있는 물고기가 없을 때 까지 반복할 때, 상어가 잡아먹을 수 있는 물고기 번호의 최댓값을 구하는 문제이다.
풀이방법
구현 자체는 문제를 그대로 구현하면 되기에 상태를 변화시키는 것 말고는 어려운 것이 없다. 다만 문제는 상어가 이동하는 경우의 수가 많다는 것이다. 상어가 1~3칸을 이동 가능한데 모든 경우의 수를 탐색해야 하므로 DFS로 구현하였다.
물고기 클래스를 정의하여 물고기의 번호, 위치, 방향, 생존여부를 저장하였다. 상어가 이동하고 다시 DFS를 호출할 때 각 분기는 독립된 상태를 유지해야 하므로 현재 상태의 맵과 물고기 상태를 계속 복사해서 넘겨주어야 했다. 상태관리만 신경 쓴다면 귀찮지만 어렵지 않은 문제이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class Fish {
int num, dir, r, c;
boolean alive;
public Fish(int num, int dir, int r, int c) {
this.num = num;
this.dir = dir;
this.r = r;
this.c = c;
alive = true;
}
public Fish(int num, int dir, int r, int c, boolean alive) {
this.num = num;
this.dir = dir;
this.r = r;
this.c = c;
this.alive = alive;
}
/**
* 이동 가능한 방향 구하기(물고기)
*
* @param map
* @return
*/
public int getFishMovableDir(int[][] map) {
while (true) {
int nextR = r + dirs[this.dir][0];
int nextC = c + dirs[this.dir][1];
if (nextR < 0 || nextC < 0 || nextR >= 4 || nextC >= 4 || map[nextR][nextC] == -1) {
this.dir = (this.dir + 1) % 8; // 45도 회전
continue;
}
return dir;
}
}
public Fish copyShark(int nextR, int nextC) {
return new Fish(SHARK, this.dir, nextR, nextC);
}
}
static int SHARK = -1;
static int[][] dirs = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
Map<Integer, Fish> fishMap = new HashMap<>();
int[][] originalMap = new int[4][4];
for (int r = 0; r < 4; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 0; c < 4; c++) {
int num = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken()) - 1;
originalMap[r][c] = num;
fishMap.put(num, new Fish(num, dir, r, c));
}
}
// 처음 상어 방향은 0,0 위치의 물고기 방향
Fish shark = new Fish(SHARK, fishMap.get(originalMap[0][0]).dir, 0, 0);
int answer = dfs(shark, originalMap, fishMap);
System.out.println(answer);
}
private static int dfs(Fish shark, int[][] map, Map<Integer, Fish> fishMap) {
int deadFishNum = map[shark.r][shark.c]; // 상어가 먹은 물고기 번호
int eatCount = deadFishNum;
map[shark.r][shark.c] = -1; // 물고기 먹음
Fish deadFish = fishMap.get(deadFishNum);
deadFish.alive = false; // 물고기 죽음
shark.dir = deadFish.dir; // 상어 방향 수정
// 물고기 이동
for (int num = 1; num <= 16; num++) {
Fish nowFish = fishMap.get(num);
if (!nowFish.alive) {
continue;
}
int dir = nowFish.getFishMovableDir(map); // 물고기 이동 가능 방향 구하기
int nextR = nowFish.r + dirs[dir][0];
int nextC = nowFish.c + dirs[dir][1];
if (map[nextR][nextC] != 0) { // 물고기 이동 위치에 물고기 존재하면 위치 바꿔주기
Fish swapFish = fishMap.get(map[nextR][nextC]);
swap(swapFish, nowFish, map);
} else {
fishMove(map, nowFish, nextR, nextC);
}
}
int count = 0;
// 상어 이동
for (int dist = 1; dist <= 3; dist++) {
int nextR = shark.r + dirs[shark.dir][0] * dist;
int nextC = shark.c + dirs[shark.dir][1] * dist;
if (nextR < 0 || nextC < 0 || nextR >= 4 || nextC >= 4 || map[nextR][nextC] == 0) {
continue; // 맵 안에 있으면서 물고기 있는 자리여야함
}
// 상어, 지도, 물고기 목록 복사
Fish newShark = shark.copyShark(nextR, nextC);
int[][] newMap = copyMap(map);
newMap[shark.r][shark.c] = 0;
Map<Integer, Fish> newFishMap = coptMap(fishMap);
count = Math.max(count, dfs(newShark, newMap, newFishMap)); // 가장 큰 물고기 번호 먹어야함
}
return count + eatCount;
}
private static Map<Integer, Fish> coptMap(Map<Integer, Fish> fishMap) {
Map<Integer, Fish> newFishMap = new HashMap<>();
for (int i = 1; i <= 16; i++) {
Fish fish = fishMap.get(i);
newFishMap.put(i, new Fish(fish.num, fish.dir, fish.r, fish.c, fish.alive));
}
return newFishMap;
}
private static int[][] copyMap(int[][] map) {
int[][] newMap = new int[4][4];
for (int r = 0; r < 4; r++) {
newMap[r] = map[r].clone();
}
return newMap;
}
private static void fishMove(int[][] map, Fish nowFish, int nextR, int nextC) {
map[nowFish.r][nowFish.c] = 0;
nowFish.r = nextR;
nowFish.c = nextC;
map[nowFish.r][nowFish.c] = nowFish.num;
}
/**
* 물고기 위치 스왚
*
* @param swapFish
* @param nowFish
* @param map
*/
private static void swap(Fish swapFish, Fish nowFish, int[][] map) {
map[nowFish.r][nowFish.c] = swapFish.num;
map[swapFish.r][swapFish.c] = nowFish.num;
int tempR = swapFish.r;
int tempC = swapFish.c;
swapFish.r = nowFish.r;
swapFish.c = nowFish.c;
nowFish.r = tempR;
nowFish.c = tempC;
}
}
채점 현황을 어쩌다 누르게 됐는데, 아래는 내가 푼 코드, 위는 다른사람의 코드인데 결과 옆으로 메모리, 시간, 언어, 코드 길이이다. 언어의 차이겠지만 C++ 코드보다 메모리는 7배 많이 사용하고, 시간은 C++은 0초인데 내 건... 심지어 코드 길이도 2배가 넘으니 뭔가 내 코드가 엄청 엉망인 거 같고.... 지금 생각해 보니 Map 대신 배열을 사용해 볼걸 하는...
아니근데
그래서 한번 배열로 수정을 해봤다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class Fish {
int num, dir, r, c;
boolean alive;
public Fish(int num, int dir, int r, int c) {
this.num = num;
this.dir = dir;
this.r = r;
this.c = c;
alive = true;
}
public Fish(int num, int dir, int r, int c, boolean alive) {
this.num = num;
this.dir = dir;
this.r = r;
this.c = c;
this.alive = alive;
}
/**
* 이동 가능한 방향 구하기(물고기)
*
* @param map
* @return
*/
public int getFishMovableDir(int[][] map) {
while (true) {
int nextR = r + dirs[this.dir][0];
int nextC = c + dirs[this.dir][1];
if (nextR < 0 || nextC < 0 || nextR >= 4 || nextC >= 4 || map[nextR][nextC] == -1) {
this.dir = (this.dir + 1) % 8; // 45도 회전
continue;
}
return dir;
}
}
public Fish copyShark(int nextR, int nextC) {
return new Fish(SHARK, this.dir, nextR, nextC);
}
}
static int SHARK = -1;
static int[][] dirs = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
Fish[] fishArr = new Fish[17];
int[][] originalMap = new int[4][4];
for (int r = 0; r < 4; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 0; c < 4; c++) {
int num = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken()) - 1;
originalMap[r][c] = num;
fishArr[num] = new Fish(num, dir, r, c);
}
}
// 처음 상어 방향은 0,0 위치의 물고기 방향
Fish shark = new Fish(SHARK, fishArr[originalMap[0][0]].dir, 0, 0);
int answer = dfs(shark, originalMap, fishArr);
System.out.println(answer);
}
private static int dfs(Fish shark, int[][] map, Fish[] fishArr) {
int deadFishNum = map[shark.r][shark.c]; // 상어가 먹은 물고기 번호
int eatCount = deadFishNum;
map[shark.r][shark.c] = -1; // 물고기 먹음
Fish deadFish = fishArr[deadFishNum];
deadFish.alive = false; // 물고기 죽음
shark.dir = deadFish.dir; // 상어 방향 수정
// 물고기 이동
for (int num = 1; num <= 16; num++) {
Fish nowFish = fishArr[num];
if (!nowFish.alive) {
continue;
}
int dir = nowFish.getFishMovableDir(map); // 물고기 이동 가능 방향 구하기
int nextR = nowFish.r + dirs[dir][0];
int nextC = nowFish.c + dirs[dir][1];
if (map[nextR][nextC] != 0) { // 물고기 이동 위치에 물고기 존재하면 위치 바꿔주기
Fish swapFish = fishArr[map[nextR][nextC]];
swap(swapFish, nowFish, map);
} else {
fishMove(map, nowFish, nextR, nextC);
}
}
int count = 0;
// 상어 이동
for (int dist = 1; dist <= 3; dist++) {
int nextR = shark.r + dirs[shark.dir][0] * dist;
int nextC = shark.c + dirs[shark.dir][1] * dist;
if (nextR < 0 || nextC < 0 || nextR >= 4 || nextC >= 4 || map[nextR][nextC] == 0) {
continue; // 맵 안에 있으면서 물고기 있는 자리여야함
}
// 상어, 지도, 물고기 목록 복사
Fish newShark = shark.copyShark(nextR, nextC);
int[][] newMap = copyMap(map);
newMap[shark.r][shark.c] = 0;
Fish[] newFishArr = copyArr(fishArr);
count = Math.max(count, dfs(newShark, newMap, newFishArr)); // 가장 큰 물고기 번호 먹어야함
}
return count + eatCount;
}
private static Fish[] copyArr(Fish[] fishArr) {
Fish[] newFishArr = new Fish[17];
for (int i = 1; i <= 16; i++) {
Fish fish = fishArr[i];
newFishArr[i] = new Fish(fish.num, fish.dir, fish.r, fish.c, fish.alive);
}
return newFishArr;
}
private static int[][] copyMap(int[][] map) {
int[][] newMap = new int[4][4];
for (int r = 0; r < 4; r++) {
newMap[r] = map[r].clone();
}
return newMap;
}
private static void fishMove(int[][] map, Fish nowFish, int nextR, int nextC) {
map[nowFish.r][nowFish.c] = 0;
nowFish.r = nextR;
nowFish.c = nextC;
map[nowFish.r][nowFish.c] = nowFish.num;
}
/**
* 물고기 위치 스왚
*
* @param swapFish
* @param nowFish
* @param map
*/
private static void swap(Fish swapFish, Fish nowFish, int[][] map) {
map[nowFish.r][nowFish.c] = swapFish.num;
map[swapFish.r][swapFish.c] = nowFish.num;
int tempR = swapFish.r;
int tempC = swapFish.c;
swapFish.r = nowFish.r;
swapFish.c = nowFish.c;
nowFish.r = tempR;
nowFish.c = tempC;
}
}
약간이라도 시간이 줄거라 예상했는데 이게 웬걸?
메모리만 약간 줄고 시간이 더 늘었다? 우선 해보고 결과를 보니 든 생각은, 고작 16개의 물고기 데이터를 Map에서 배열로 바꾼다고 의미가 없는 수준의 성능 차이일 거라는 것. 하기 전에 생각해 봤으면 좋았을 것을!
