상어가 이동할 수 있는 경우의 수는, 우선순위를 고려해야함.
만일, 3번 이동안에 물고기가 없다면? 이동 우선순위 숫자를 정해진데로 해야함.
이동 가능한 경우의 수 중에, 각 칸에서 가장 우선순위가 높은 경우의 수
또한, 한번 이동하고 원위치로도 다시 이동이 가능하다. 다만, 이미 물고기를 먹기 위해 이동을 한번이상 했다면, 물고기 수는 카운트 X
처음에 boolean으로 방문 기록을 체크했다가, dfs형태로 구현하면서 함수 리턴시 visited를 다시 false로 하는 과정에서 중복으로 방문하는 곳도 같이 초기화가 되어서 값이 한번 꼬임.
또한, 커스텀 클래스를 사용하여 내부 자료구조를 활용하려 했으나 깊은 복사/ 얕은 복사 이슈로 인스턴스를 구분하는데서 실수함.
import java.util.*;
import java.io.*;
public class BackJoonMemo2 {
static class Fish{
int x, y;
Deque<Integer> fishes;
Fish(int x, int y){
this.x = x;
this.y = y;
this.fishes = new LinkedList<>();
}
}
static int[][] visited;
static int[][] shark;
static int[][] smell;
static Fish[][] fishState;
static String sharksPath;
static int sx, sy;
static int pathMaxFishes;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 물고기 수
int m = Integer.parseInt(st.nextToken());
// 상어 마법 연습 횟수
int s = Integer.parseInt(st.nextToken());
fishState = new Fish[5][5];
initFishFields(fishState);
// 물고기 첫 위치
for(int i = 0; i< m; i++){
st = new StringTokenizer(br.readLine());
int fx = Integer.parseInt(st.nextToken());
int fy = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
fishState[fx][fy].fishes.add(d);
}
// 상어 첫 위치
st = new StringTokenizer(br.readLine());
sx = Integer.parseInt(st.nextToken());
sy = Integer.parseInt(st.nextToken());
shark = new int[5][5];
shark[sx][sy] = 1;
visited = new int[5][5];
// 물고기 냄새
smell = new int[5][5];
// 물고기 복사 마법 실행(횟수 만큼)
for(int i = 0; i< s; i++){
System.out.print("Practice <" + (i +1) + "> \n" );
// 1. 물고기 복사
Fish[][] fishCopy = fishCopy();////
// 2. 물고기 이동
fishMove(i+1);////
System.out.println("fish Moved");
printFields(fishState);
// 3. 상어 이동
System.out.println("shark Moved : ");
System.out.println("before -> sx : " + sx + ", sy : " + sy);
sharkExceptsFish(i+1);////
System.out.println("shark Path : " + sharksPath);
System.out.println("after -> sx : " + sx + ", sy : " + sy);
System.out.println("\nsmell gone");
System.out.println("before");
for(int x = 1; x<=4; x++){
for(int y = 1; y<= 4; y++){
System.out.print(smell[x][y] + " ");
}
System.out.println();
}
// 4. 두번 전물고기 냄새 사라짐
smellGone(i+1); ////
System.out.println("after");
for(int x = 1; x<=4; x++){
for(int y = 1; y<= 4; y++){
System.out.print(smell[x][y] + " ");
}
System.out.println();
}
// 5. 물고기 복사 완료
for(int x = 1; x <= 4; x++){
for(int y = 1; y <= 4; y++){
fishState[x][y].fishes.addAll(fishCopy[x][y].fishes);
}
}
System.out.println("\nfish Cloned");
printFields(fishState);
}
// 마법 종료 후 남아있는 물고기 수 확인
int result = 0;
for(int x = 1; x <= 4; x++){
for(int y = 1; y <= 4; y++){
result += fishState[x][y].fishes.size();
}
}
System.out.println("result : " + result);
}
static Fish[][] fishCopy(){ // 1) 물고기 복사
Fish[][] copy = new Fish[5][5];
initFishFields(copy);
for(int i = 1; i<= 4; i++){
for(int j =1; j<=4; j++){
copy[i][j].fishes.addAll(fishState[i][j].fishes);
}
}
return copy;
}
static void fishMove(int pracCount){ // 2) 물고기 한칸 이동
Fish[][] movedFishFields = new Fish[5][5];
initFishFields(movedFishFields);
for(int i = 1; i<= 4; i++){
for(int j = 1; j<=4; j++){
Deque<Integer> fieldsFish = fishState[i][j].fishes;
int remainFish = fieldsFish.size(); // 실수부분
for(int f = 0; f<remainFish; f++){
int[] whereToMove = getFishDirection(i, j, fieldsFish.poll(), 1); // return moved R, C, Dir
int movedI = whereToMove[0];
int movedJ = whereToMove[1];
int movedD = whereToMove[2];
movedFishFields[movedI][movedJ].fishes.add(movedD);
}
}
}
fishState = movedFishFields;
}
static int[] getFishDirection(int i, int j, int dir, int spin){ // 2-1) 물고기 이동 방향 설정
if(spin > 8){
return new int[]{i, j, dir};
}
int movedR = i;
int movedC = j;
if(dir == 1){ // 왼쪽
movedC--;
}else if (dir == 2){ // 왼쪽 대각선 위
movedR--;
movedC--;
}else if (dir == 3){ // 위
movedR--;
}else if (dir == 4){ // 오른쪽 대각선 위
movedR--;
movedC++;
}else if (dir == 5){ // 오른쪽
movedC++;
}else if (dir == 6){ // 오른쪽 대각선 아래
movedR++;
movedC++;
}else if (dir == 7){ // 아래
movedR++;
}else if (dir == 8){ // 왼쪽 대각선 아래
movedR++;
movedC--;
}
if(movedR < 1 || movedR > 4 || movedC < 1 || movedC > 4){
return getFishDirection(i, j, dir - 1 == 0 ? 8 : dir -1, spin + 1);
}
else if(smell[movedR][movedC] != 0){
return getFishDirection(i, j, dir - 1 == 0 ? 8 : dir -1, spin + 1);
}
else if(shark[movedR][movedC] != 0){
return getFishDirection(i, j, dir - 1 == 0 ? 8 : dir -1, spin + 1);
}
return new int[]{movedR, movedC, dir};
}
// 3) 상어 이동
static void sharkExceptsFish(int pracCount){
sharksPath = "555";
pathMaxFishes = 0;
if(sx-1 >= 1 && sx <= 4){
sharksMoving(sx-1, sy, "1", fishState[sx-1][sy].fishes.size()); // 상
}
if(sy - 1 >= 1 && sy <= 4){
sharksMoving(sx, sy-1, "2", fishState[sx][sy-1].fishes.size()); // 좌
}
if(sx + 1 <= 4 && sx >= 1){
sharksMoving(sx+1, sy, "3", fishState[sx+1][sy].fishes.size()); // 하
}
if(sy + 1 <= 4 && sy >= 1){
sharksMoving(sx, sy+1, "4", fishState[sx][sy+1].fishes.size()); // 우
}
char[] pathSeq = sharksPath.toCharArray();
// 물고기 냄새
fishSmell(pracCount, pathSeq);
}
// 3-1) 상어 상/하/좌/우 이동
static void sharksMoving(int i, int j, String path, int exceptFishes){
int currPathFishes = exceptFishes;
if(visited[i][j] >= 1) {
currPathFishes = exceptFishes - fishState[i][j].fishes.size();
}
visited[i][j]++;
/*for(int x= 1; x<=4 ;x++){
for(int y = 1; y <= 4; y++){
System.out.print(visited[x][y] + " ");
}
System.out.println();
}*/
System.out.println();
if(path.length() == 3){
if(pathMaxFishes < currPathFishes){
pathMaxFishes = currPathFishes;
sharksPath = path;
System.out.println("1 " + path + " fishes : " + pathMaxFishes);
}else if(pathMaxFishes == currPathFishes && path.compareTo(sharksPath) < 0){
pathMaxFishes = currPathFishes;
sharksPath = path;
System.out.println("2 " + path + " fishes : " + pathMaxFishes);
}
else{
System.out.println("0 " + path + " fishes : " + pathMaxFishes);
}
System.out.println("---------------");
visited[i][j]--;
return;
}
if(i - 1 >= 1 && i <= 4) {
sharksMoving(i - 1, j, path + "1", currPathFishes + fishState[i - 1][j].fishes.size()); // 상
}
if(j - 1 >= 1 && j <= 4) {
sharksMoving(i, j - 1, path + "2", currPathFishes + fishState[i][j - 1].fishes.size()); // 좌
}
if(i + 1 <= 4 && i >= 1){
sharksMoving(i+1, j, path + "3", currPathFishes + fishState[i+1][j].fishes.size()); // 하
}
if(j + 1 <= 4 && j >= 1){
sharksMoving(i, j+1, path + "4", currPathFishes + fishState[i][j+1].fishes.size()); // 우
}
visited[i][j]--;
}
// 3-2) 상어 지나간 자리 물고기 있으면 물고기 냄새
static void fishSmell(int pracCount, char[] pathSeq){
shark[sx][sy] = 0;
for(char s : pathSeq){
if(s == '1'){
sx--;
}else if(s == '2'){
sy--;
}else if(s == '3'){
sx++;
}else if(s == '4'){
sy++;
}
if(fishState[sx][sy].fishes.size() >= 1){
fishState[sx][sy].fishes = new LinkedList<>();
smell[sx][sy] = pracCount;
}
}
shark[sx][sy] = 1;
}
static void smellGone(int pracCount){ //
for(int i = 1; i<=4 ; i++){
for(int j = 1; j<= 4; j++){
if(smell[i][j] <= pracCount - 2){
smell[i][j] = 0;
}
}
}
}
static void printFields(Fish[][] fList){
for(int i = 1; i<=4 ; i++){
for(int j =1 ; j<=4; j++){
System.out.print(fList[i][j].fishes);
}
System.out.println();
}
System.out.println();
}
static void printFieldsSize(Fish[][] fList){
for(int i = 1; i<=4 ; i++){
for(int j =1 ; j<=4; j++){
System.out.print(fList[i][j].fishes.size()+ " ");
}
System.out.println();
}
System.out.println();
}
static void initFishFields(Fish[][] field){ // 물고기 필드 초기화
for(int i = 1; i<= 4; i++){
for(int j = 1; j<= 4; j++){
field[i][j] = new Fish(i, j);
}
}
}
}
