상어가 잡어먹고 → 물고기 이동하고 → 상어가 이동한다
dfs로 감싸다보니까
상어가 잡아먹고 → dfs로 들어가서 → 다시 잡아먹고 → 이동한다 → 다시 잡아먹고 → 이동하고
상어 잡아먹고 →dfs로 들어가서 → 이동하고 → 다시 잡아먹고 → dfs → 이동하고 → 잡아먹고
2번 싸이클로 가야함 원래 잡아먹고 → 이동하고니까
[잘못된 사이클 코드]
public static void dfs(List<Fish> originFishList, Shark shark) {
int nx, ny;
if (maxSum < shark.eat) {
maxSum = shark.eat;
}
for(int dist=1; dist<4; dist++) {
nx = shark.x + dx[shark.dir]*dist;
ny = shark.y + dy[shark.dir]*dist;
//상어가 먹는다
if(nx>=0 && nx<4 && ny>=0 && ny<4 && findByCoord(nx,ny,originFishList).alive ==true) {
List<Fish> copiedFish = deepCopyArrayList(originFishList);
Fish fish= findByCoord(nx,ny,copiedFish);
Shark newShark = new Shark(fish.dir, shark.eat + fish.id, nx, ny);
fish.alive = false;
print2DArray(copiedFish);
System.out.println();
//물고기가 이동한다.
for(int i=0; i<copiedFish.size(); i++) {
if(copiedFish.get(i).alive == true) {
moveFish(copiedFish.get(i), newShark, copiedFish); // 여기 shark로 되어있었음 -> newShark이어야 함
}
}
dfs(copiedFish, newShark);
}
}
}
→ 결론적으로는 아니었지만, 사이클을 신경써야 하는건 맞다
[Copy를 잘 했다고 생각했는데 순서가 어그러져 있다]
import java.util.*;
import java.io.*;
class Fish implements Cloneable{
int id, dir, x, y;
boolean alive;
public Fish(int id, int dir, int x, int y, boolean alive) {
this.id = id;
this.dir = dir;
this.x = x;
this.y = y;
this.alive = alive;
}
@Override
public String toString() {
return "Fish [id=" + id + ", dir=" + dir + ", x=" + x + ", y=" + y + ", alive=" + alive + "]";
}
}
class Shark implements Cloneable{
int dir, eat, x, y;
public Shark(int dir, int eat, int x, int y) {
this.dir = dir;
this.eat = eat;
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Shark [dir=" + dir + ", eat=" + eat + ", x=" + x + ", y=" + y + "]";
}
}
public class TennagerShark{
// static List<Fish> fishList = new ArrayList<>();
//direction
static int[] dx = {-1,-1,0,1,1,1,0,-1};
static int[] dy = {0,-1,-1,-1,0,1,1,1};
static int maxSum = 0;
static int size=0;
static int[][] fishes = new int[4][4];
public static Fish findByCoord(int x, int y, List<Fish> fishList) {
for(int i=0; i<fishList.size(); i++) {
if(fishList.get(i).x == x && fishList.get(i).y ==y) {
return fishList.get(i);
}
}
return null;
}
public static Fish findById(int id, List<Fish> fishList) {
for(int i=0; i<fishList.size(); i++) {
if(fishList.get(i).id == id) {
return fishList.get(i);
}
}
return null;
}
public static void print2DArray(List<Fish> fishList) {
for(int i=0; i<4; i++) {
for(int j=0; j<4; j++) {
if(findByCoord(i,j, fishList).alive ==true) {
fishes[i][j] = findByCoord(i, j, fishList).id;
}else {
fishes[i][j] = -1;
}
}
}
for(int i=0; i<4; i++) {
for(int j=0; j<4; j++) {
System.out.print(fishes[i][j] + " ");
}
System.out.println();
}
}
public static List<Fish> deepCopyArrayList(List<Fish> arrayList) {
List<Fish> copyList = new ArrayList<Fish>();
for(Fish fish: arrayList) {
copyList.add(fish);
}
return copyList;
}
public static void main(String[] args) throws IOException {
List<Fish> fishList = new ArrayList<>();
//input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int a,b;
for(int i=0; i<4; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<4; j++) {
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
fishList.add(new Fish(a, b-1, i, j, true));
}
}
//System.out.println(fishList);
Collections.sort(fishList, new Comparator<Fish>() {
@Override
public int compare(Fish o1, Fish o2) {
return o1.id - o2.id;
}
});
//System.out.println(fishList);
//solution
solution(fishList);
}
public static void solution(List<Fish> fishList) {
//상어가 먹는다
//초기 조건 (0,0)
Fish firstFish = findByCoord(0,0,fishList);
Shark shark = new Shark(firstFish.dir, firstFish.id, 0, 0);
firstFish.alive = false;
List<Fish> copiedFish = deepCopyArrayList(fishList);
//물고기가 이동한다
for(int i=0; i<fishList.size(); i++) {
if(fishList.get(i).alive == true) {
//System.out.println(i+1 + "번째 입니다");
moveFish(fishList.get(i), shark, fishList);
//System.out.println();
}
}
//상어가 이동한다.
size = 0;
dfs(fishList, shark, size);
System.out.println(maxSum);
}
public static void dfs(List<Fish> originFishList, Shark shark,int size) {
int nx, ny;
if (maxSum < shark.eat) {
maxSum = shark.eat;
}
for(int dist=1; dist<4; dist++) {
//복제한다 (3개의 경우의수마다 모두 deepCopy한 경우를 기억해야한다)
//List<Fish> copiedFish = deepCopyArrayList(originFishList);
//여기서 처음에 copiedFish를 맨 마지막에 놨었는데 위치를 여기에 놔야 한다. 3가지 경우의 수 모두 copy해서 다르게 갈거니까 여기서 copy해서 보내는게 맞다.
//아래 원래 originFishList로 옮겨다녔었는데 그러면 안됨.
nx = shark.x + dx[shark.dir]*dist;
ny = shark.y + dy[shark.dir]*dist;
//상어가 먹는다
if(nx>=0 && nx<4 && ny>=0 && ny<4) {
if(findByCoord(nx,ny,originFishList).alive ==true) {
List<Fish> copiedFish = deepCopyArrayList(originFishList);
Fish fish= findByCoord(nx,ny,copiedFish);
Shark newShark = new Shark(fish.dir, shark.eat + fish.id, nx, ny);
fish.alive = false;
System.out.println(copiedFish);
//물고기가 이동한다.
for(int i=0; i<copiedFish.size(); i++) {
if(copiedFish.get(i).alive == true) {
moveFish(copiedFish.get(i), newShark, copiedFish); // 여기 shark로 되어있었음 -> newShark이어야 함
}
}
size+=1;
System.out.println("추적" +" " + size);
System.out.println(shark.eat + " " + fish.id);
dfs(copiedFish, newShark, size);
}
}
}
}
public static void moveFish(Fish fish, Shark shark, List<Fish> fishList) {
int nx, ny;
int newDir;
for(int dir=0; dir<8; dir++) {
newDir = (fish.dir + dir)%8;
nx = fish.x + dx[newDir];
ny = fish.y + dy[newDir];
//이동하지 못할 조건
if(nx>3 || nx<0 || ny>3 || ny<0) {
continue;
}else if(shark.x == nx && shark.y ==ny){
continue;
}else {
//이동할수 있는 조건
int tempX, tempY;
fish.dir = newDir;
Fish targetfish = findByCoord(nx, ny, fishList);
//교환 -> 내가 실수한 부분 -> 새로운 방향으로 집어 넣어야 하는데
tempX = fish.x; tempY = fish.y;
fish.x = targetfish.x; fish.y = targetfish.y;
targetfish.x = tempX; targetfish.y = tempY;
return;
}
}
}
}
7 6 2 3 15 6 9 8
3 1 1 8 14 7 10 1
6 1 13 6 4 3 11 4
16 1 8 7 5 2 12 2
[Fish [id=1, dir=7, x=1, y=2, alive=true], Fish [id=2, dir=3, x=0, y=1, alive=true], Fish [id=3, dir=3, x=3, y=0, alive=true], Fish [id=4, dir=2, x=3, y=1, alive=true], Fish [id=5, dir=1, x=2, y=1, alive=true], Fish [id=6, dir=0, x=1, y=0, alive=true], Fish [id=7, dir=5, x=0, y=0, alive=false], Fish [id=8, dir=6, x=3, y=3, alive=true], Fish [id=9, dir=2, x=0, y=2, alive=true], Fish [id=10, dir=0, x=0, y=3, alive=true], Fish [id=11, dir=3, x=3, y=2, alive=true], Fish [id=12, dir=1, x=1, y=1, alive=false], Fish [id=13, dir=0, x=2, y=3, alive=true], Fish [id=14, dir=6, x=1, y=3, alive=true], Fish [id=15, dir=5, x=2, y=2, alive=true], Fish [id=16, dir=0, x=2, y=0, alive=true]]
추적 1
7 12
[Fish [id=1, dir=7, x=1, y=3, alive=true], Fish [id=2, dir=3, x=2, y=1, alive=true], Fish [id=3, dir=6, x=3, y=0, alive=true], Fish [id=4, dir=6, x=3, y=1, alive=true], Fish [id=5, dir=1, x=2, y=0, alive=true], Fish [id=6, dir=2, x=0, y=0, alive=false], Fish [id=7, dir=5, x=1, y=2, alive=false], Fish [id=8, dir=0, x=2, y=3, alive=true], Fish [id=9, dir=2, x=0, y=1, alive=true], Fish [id=10, dir=0, x=0, y=2, alive=true], Fish [id=11, dir=6, x=3, y=2, alive=true], Fish [id=12, dir=1, x=1, y=1, alive=false], Fish [id=13, dir=0, x=2, y=2, alive=true], Fish [id=14, dir=0, x=0, y=3, alive=true], Fish [id=15, dir=6, x=3, y=3, alive=true], Fish [id=16, dir=0, x=1, y=0, alive=true]]
추적 2
19 6
[Fish [id=1, dir=0, x=0, y=3, alive=true], Fish [id=2, dir=3, x=2, y=0, alive=true], Fish [id=3, dir=6, x=2, y=2, alive=false], Fish [id=4, dir=6, x=3, y=1, alive=true], Fish [id=5, dir=4, x=3, y=0, alive=true], Fish [id=6, dir=2, x=0, y=0, alive=false], Fish [id=7, dir=5, x=1, y=2, alive=false], Fish [id=8, dir=0, x=3, y=3, alive=true], Fish [id=9, dir=3, x=1, y=0, alive=true], Fish [id=10, dir=2, x=0, y=2, alive=true], Fish [id=11, dir=6, x=3, y=2, alive=true], Fish [id=12, dir=1, x=2, y=1, alive=false], Fish [id=13, dir=0, x=1, y=1, alive=true], Fish [id=14, dir=0, x=1, y=3, alive=true], Fish [id=15, dir=0, x=2, y=3, alive=true], Fish [id=16, dir=2, x=0, y=1, alive=true]]
추적 2
7 3
[Fish [id=1, dir=2, x=1, y=3, alive=true], Fish [id=2, dir=4, x=1, y=1, alive=true], Fish [id=3, dir=6, x=2, y=2, alive=false], Fish [id=4, dir=6, x=3, y=1, alive=true], Fish [id=5, dir=4, x=3, y=0, alive=true], Fish [id=6, dir=2, x=0, y=0, alive=false], Fish [id=7, dir=5, x=1, y=2, alive=false], Fish [id=8, dir=0, x=3, y=3, alive=true], Fish [id=9, dir=4, x=2, y=0, alive=true], Fish [id=10, dir=2, x=0, y=2, alive=true], Fish [id=11, dir=6, x=3, y=2, alive=true], Fish [id=12, dir=1, x=2, y=1, alive=false], Fish [id=13, dir=0, x=0, y=1, alive=true], Fish [id=14, dir=0, x=0, y=3, alive=true], Fish [id=15, dir=0, x=2, y=3, alive=false], Fish [id=16, dir=2, x=1, y=0, alive=true]]
추적 3
10 15
[Fish [id=1, dir=2, x=1, y=2, alive=true], Fish [id=2, dir=4, x=1, y=0, alive=true], Fish [id=3, dir=6, x=3, y=3, alive=false], Fish [id=4, dir=6, x=3, y=2, alive=true], Fish [id=5, dir=6, x=3, y=1, alive=true], Fish [id=6, dir=2, x=0, y=0, alive=false], Fish [id=7, dir=5, x=1, y=3, alive=false], Fish [id=8, dir=1, x=2, y=2, alive=true], Fish [id=9, dir=4, x=3, y=0, alive=true], Fish [id=10, dir=2, x=0, y=3, alive=false], Fish [id=11, dir=6, x=2, y=1, alive=true], Fish [id=12, dir=1, x=1, y=1, alive=false], Fish [id=13, dir=2, x=0, y=1, alive=true], Fish [id=14, dir=2, x=0, y=2, alive=true], Fish [id=15, dir=0, x=2, y=3, alive=false], Fish [id=16, dir=4, x=2, y=0, alive=true]]
추적 4
25 10
[Fish [id=1, dir=2, x=2, y=1, alive=true], Fish [id=2, dir=4, x=1, y=0, alive=true], Fish [id=3, dir=6, x=3, y=0, alive=false], Fish [id=4, dir=6, x=3, y=3, alive=true], Fish [id=5, dir=6, x=3, y=2, alive=true], Fish [id=6, dir=2, x=0, y=2, alive=false], Fish [id=7, dir=5, x=1, y=3, alive=false], Fish [id=8, dir=1, x=1, y=1, alive=true], Fish [id=9, dir=6, x=3, y=1, alive=true], Fish [id=10, dir=2, x=0, y=3, alive=false], Fish [id=11, dir=6, x=2, y=2, alive=true], Fish [id=12, dir=1, x=1, y=2, alive=false], Fish [id=13, dir=2, x=0, y=0, alive=true], Fish [id=14, dir=2, x=0, y=1, alive=false], Fish [id=15, dir=0, x=2, y=3, alive=false], Fish [id=16, dir=4, x=2, y=0, alive=true]]
추적 5
35 14
[Fish [id=1, dir=2, x=1, y=1, alive=true], Fish [id=2, dir=4, x=2, y=0, alive=true], Fish [id=3, dir=6, x=3, y=0, alive=false], Fish [id=4, dir=0, x=2, y=2, alive=true], Fish [id=5, dir=6, x=3, y=3, alive=true], Fish [id=6, dir=2, x=0, y=2, alive=false], Fish [id=7, dir=5, x=1, y=3, alive=false], Fish [id=8, dir=1, x=0, y=0, alive=false], Fish [id=9, dir=6, x=3, y=2, alive=true], Fish [id=10, dir=2, x=0, y=3, alive=false], Fish [id=11, dir=6, x=2, y=3, alive=true], Fish [id=12, dir=1, x=1, y=2, alive=false], Fish [id=13, dir=2, x=1, y=0, alive=true], Fish [id=14, dir=2, x=0, y=1, alive=false], Fish [id=15, dir=0, x=2, y=1, alive=false], Fish [id=16, dir=4, x=3, y=1, alive=true]]
추적 6
49 8
[Fish [id=1, dir=2, x=1, y=1, alive=true], Fish [id=2, dir=4, x=3, y=0, alive=true], Fish [id=3, dir=6, x=2, y=0, alive=false], Fish [id=4, dir=0, x=1, y=2, alive=true], Fish [id=5, dir=0, x=2, y=3, alive=true], Fish [id=6, dir=2, x=0, y=2, alive=false], Fish [id=7, dir=5, x=1, y=3, alive=false], Fish [id=8, dir=1, x=0, y=0, alive=false], Fish [id=9, dir=6, x=3, y=1, alive=true], Fish [id=10, dir=2, x=0, y=3, alive=false], Fish [id=11, dir=6, x=3, y=3, alive=false], Fish [id=12, dir=1, x=2, y=2, alive=false], Fish [id=13, dir=2, x=1, y=0, alive=true], Fish [id=14, dir=2, x=0, y=1, alive=false], Fish [id=15, dir=0, x=2, y=1, alive=false], Fish [id=16, dir=6, x=3, y=2, alive=true]]
추적 3
7 11
57
결괄르보면 첫 번째는 12로 잘 갔다 하지만 추적 2번째를 보면 7, 3으로 되어 있다. 15가 되어야 하는데 뭔가 순서가 어그러짐