백준 23290

결국 3차원 배열로 풀어야 했던 문제..

🐟 같은 방향 보고 있는 물고기 2마리 이상이 같은 칸에 존재할 수도 있다. 이걸 되게 고민했는데 3차원 배열 쓰는게 더 편한것 같다... 

🐟그리고 계속 실수했던 부분이 냄새를 삭제하는거... 상어가 움직이기 전에 각 smell[][] 감소시켜줘야한다. 상어가 움직이고 나서 감소해주면 갱신된 상태에서 감소시키는거라 계속 답이 틀림 

 

진짜 너무 복잡했다... ㅎ 

아직 코딩 멀었다~.~...

---

 

🐟 변수

temp는 방향까지 저장한 것

fishAmountMap은 단순 해당 좌표에 몇마리 있는지만 저장한 것 (상어가 먹을 때는 방향상관없이 같은 칸에 있는거 다먹으니까)

static int m, s;

// 물고기의 8방향
public static int[] fishX= {0, -1, -1, -1, 0, 1, 1, 1};
public static int[] fishY = {-1, -1, 0, 1, 1, 1, 0, -1};

// 상어의 4방향, 상좌하우 순서
public static int[] sharkX = {-1, 0, 1, 0};
public static int[] sharkY = {0, -1, 0, 1};

// 상어 현재 위치 
static Pos shark;

static int answer;

// 가장 많이 먹을 수 있는 이동방향 
static int[] maxEatWay;

// 물고기 총 마리 수 
static int fishAmount;

// 각 칸 당 물고기 수 
static int[][] fishAmountMap;

// 원본 배열, 마지막 단계에서 복제된 물고기 합쳐주기 위해 사용 
static int[][][] map = new int[4][4][8];

// 냄새 배열, 상어가 지나간 자리는 2로 만든다. 
static int[][] smell = new int[4][4];

// 물고기 이동시마다 temp를 초기화하여 사용, 상어이동까지 끝나면 temp와 map을 합침 
static int[][][] temp;

🐟 로직 순서 

물고기 움직이기(여기서 temp 배열 만든다)  

상어가 가장 많이 먹을 수 있는 방법, 먹을 수 있는 물고기 수 초기화

냄새 제거 

상어의 경로 탐색

상어 실제로 움직이기

temp와 map 합치기

public static void magic() {
        fishMove();
        maxEatWay = new int[3];
        fishAmount = -11;
        removeSmell();
        findSharkWay();
        sharkMove();
        mergeArray();
}

 

1. 물고기 움직이기 

public static void fishMove() {
        fishAmountMap = new int[4][4];
        temp = new int[4][4][8];
        // 모든 칸에 대해
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {

                // 8방향 탐색 시작
                for (int d = 0; d < 8; d++) {
                    if (map[i][j][d] == 0) {
                        continue;
                        // i, j 칸에 d 방향의 물고기는 없다는 뜻
                    } else {
                        int tempDir = d;
                        while (true) {
                            int nextX = i + fishX[tempDir];
                            int nextY = j + fishY[tempDir];

                            if (!isValid(nextX, nextY)
                                    || smell[nextX][nextY] > 0
                                    || (nextX == shark.x && nextY == shark.y)) {
                                tempDir--; // 반시계방향으로 돌기 때문에 -1
                                if (tempDir == -1) {
                                    tempDir = 7;
                                }
                                // 탐색 다 해봤는데도 안나와서 원래 방향으로 돌아온 케이스
                                // 오리지널 맵에서 다시 데이터 꺼내와서 저장
                                if (tempDir == d) {
                                    temp[i][j][d] += map[i][j][d];
                                    fishAmountMap[i][j] += map[i][j][d];
                                    break;
                                }
                                continue;
                            }
                            // 갈 수 있는 경우 현 위치의 것을 이동할 위치에다가 옮겨서 저장
                            temp[nextX][nextY][tempDir] += map[i][j][d];
                            fishAmountMap[nextX][nextY] += map[i][j][d];
                            break;
                        }
                    }
                }
            }
        }
}

 2. 냄새 없애기 

public static void removeSmell() {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (smell[i][j] > 0) {
                    smell[i][j]--;
                }
            }
        }
}

3. 상어의 경로 찾기 

maxEatWay = new int[3];
fishAmount = -11;

public static void findSharkWay() {
        // 현재 상어 위치
        int x = shark.x;
        int y = shark.y;
        // 먹은양
        int eaten = 0;
        
        // 총 3칸을 이동하므로 3중 for문을 4번씩 돌린다(4방향 탐색)
        // 갔던 곳을 또 갈 수 있다. 이 때 물고기 카운트 중복해서 세면 안된다. 
        for (int i = 0; i < 4; i++) {
            int firstX = x + sharkX[i];
            int firstY = y + sharkY[i];
            if (!isValid(firstX, firstY)) {
                continue;
            }
            eaten += fishAmountMap[firstX][firstY];
            for (int j = 0; j < 4; j++) {
                int secondX = firstX + sharkX[j];
                int secondY = firstY + sharkY[j];
                if (!isValid(secondX, secondY)) {
                    continue;
                }
                eaten += fishAmountMap[secondX][secondY];
                for (int k = 0; k < 4; k++) {
                    int thirdX = secondX + sharkX[k];
                    int thirdY = secondY + sharkY[k];

                    if (!isValid(thirdX, thirdY)) {
                        continue;
                    }
                    
                    // 왔던 좌표가 아닌 경우에만 third 포지션의 물고기 먹기
                    if (firstX != thirdX || firstY != thirdY) {
                        eaten += fishAmountMap[thirdX][thirdY];
                    }
                    
					// 현재 경로가 더 많이 먹은거면 갱신후 그 방향들 저장
                    if (fishAmount < eaten) {
                        fishAmount = eaten; 
                        maxEatWay[0] = i;
                        maxEatWay[1] = j;
                        maxEatWay[2] = k;
                    }

                    // 먹은거 차례로 빼주면서 최대값 찾기
                    if (firstX != thirdX || firstY != thirdY) {
                        eaten -= fishAmountMap[thirdX][thirdY];
                    }
                }
                eaten -= fishAmountMap[secondX][secondY];
            }
            eaten -= fishAmountMap[firstX][firstY];
        }
}

4. 상어를 해당 경로대로 이동 시키며 먹기 

상어 지나간 칸에 temp에 새로운 배열 할당하고, fishAmountMap 도 0으로 초기화, 냄새 남기기 

public static void sharkMove() {
        int x = shark.x;
        int y = shark.y;

        // 최대 물고기 먹을 수 있는 경로대로 상어 움직임
        for (int i = 0; i < 3; i++) {
            int dir = maxEatWay[i];
            x += sharkX[dir];
            y += sharkY[dir];

            if (fishAmountMap[x][y] != 0) {
                temp[x][y] = new int[8]; // 오리지널 맵 바로 조작하는거 아님!!
                fishAmountMap[x][y] = 0;
                smell[x][y] = 2;
            }
        }
        // 다 먹으면 이동!
        shark = new Pos(x, y);
}

5. 복사된 원본과 상어가 먹은 배열 합치기 

public static void mergeArray() {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (fishAmountMap[i][j] != 0) {
                    for (int d = 0; d < 8; d++) {
                        map[i][j][d] += temp[i][j][d];
                    }
                }
            }
        }
}