[11주차_월요일] 팩맨

사이트 : 코드트리(CT)
문제: 팩맨
년도: 2021년

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

🤔 시간복잡도 고려사항

4 ⨉ 4 격자에서의 구현
크기가 작은 격자이기 떄문에 구현할 때, 시간 초과를 고려하지 않았음
- 근데 몬스터들을 HasMap, 각 지점마다 어떤 몬스터가 있는지 HashSet으로 구현하면 시간 초과 발생

전에 백준에서 똑같은 문제를 풀었었고, 이번에 문제 풀이도 저번이랑 비슷하게 했는데, 코드트리에서는 백준에서 맞은 방법으로 풀이했을 때 시초가 발생하더라고요?,,,

HashMap을 사용했을 때 시간이 조금 더 걸려도, 시간 초과는 발생하지 않을거라고 생각했는데,,, 요상하네요 !!,,,

(백준에서는 HashMap이 아닌 ArrayList로 몬스터들을 관리했긴 합니다! 그래도 구현 흐름은 비슷한데,,,, ㅠ!!!)

💡 풀이 아이디어

변수에 대한 설명

몬스터가 향하고 있는 방향과 몬스터가 있는 위치에 대해 정보를 저장함
- int[][][] monsters
- monsters[k][r][c] r, c 지점에서 k 방향을 향하고 있는 몬스터가 몇 마리인지 저장
- int[][][] tmpMonsters
- 몬스터를 이동시킨 후, r, c 지점에서 k 방향을 향하고 있는 몬스터가 몇 마리인지 저장
- int[][][] newMonsters
- 몬스터 복제를 시도할 떄, monsters 배열의 정보를 복제하기 위해 사용하는 변수
int[][] dieTime
- 몬스터가 죽고, 2초를 세기 위해 사용
int[][] packmanMoveCnt: 팩맨이 이동할 떄, 해당 위치를 몇 번 지나갔는지 저정하는 변수
- ex) [상, 하, 상]
- 이전에 갔던 곳을 다시 가는 경우 잡을 수 있는 몬스터 수를 중복해서 셀 수도 있기 때문에 boolean[][] 이 아닌 int[][]로 선언
int[] sel, move: 팩맨의 이동 위치를 파악하기 위한 변수
방향과 관련된 배열
- int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0}, dc = {1, 0, -1, -1, -1, 0, 1, 1};
- 위 방향을 시작(1)으로 반시계 방향으로 돌아가는데, 8번쨰 방향을 0번째 인덱스에 넣어주고, 방향을 사용할 때, (d % 8)로 방향을 구해줌

함수에 대한 설명

void step4(): 시체 소멸
- 턴마다 시간을 1씩 줄여줘야 되기 때문에 루프의 시작 부분에서 사용함
void step1(): 몬스터 복제 시도
- newMonsters에 기존 몬스터들의 정보를 저장함
void step2(): 몬스터 이동
- 이동시킨 후 몬스터의 수에 대한 정보는 tmpMonsters에 저장하고 나중에 monsters을 tmpMonsters로 바꿈
void step3() 팩맨 이동
- findPackManMoveDir(): 순열을 통해 팩맨이 갈 수 있는 모든 위치를 파악하고, 잡을 수 있는 몬스터가 최대일 때, 가야되는 방향 구하기
- movePackMan(): 가야되는 방향이 구해진 뒤, 백맨 이동시키기
void step5(): 몬스터 복제 완성
- monsters에 newMonsters 더해주기

🤔 시간복잡도 고려사항

구현 문제라서 신경쓰지 않음

💡 풀이 아이디어

ArrayList를 이용해서 보드를 만들어서 몬스터 정보를 저장
removeCorpses(): 몬스터 시체의 카운트 감소
- 2턴을 체크하기 위해서 턴 시작 부분에서 호출
addEggs(): 몬스터 복제 시도
- 몬스터 복제는 Queue를 이용해서 임시 저장 후 몬스터 복제가 끝날 때 하나 씩 꺼내서 저장

moveMonster(): 몬스터 이동

8방향 빙글빙글 돌면서 이동 가능한 방향 찾기

next: for (int now : monsters.get(i).get(j)) {
int y = i, x = j, dir = now;
for (int k = 0; k < 8; k++) {
    int ny = y + dy[dir];
    int nx = x + dx[dir];
    // 이동할 수 있는 방향을 찾았다면 이동 후 다음 몬스터 진행
    if (isValid(ny, nx) && canMove(ny, nx)) {
        next.get(ny).get(nx).add(dir);
        continue next;
    }
    // 한바꾸 돌기
    dir++;
    dir %= 9;
    if (dir == 0)
        dir++;
}
// 움직일 수 없었다면 현재 위치에서 대기
next.get(y).get(x).add(now);
}

movePackMan(): 팩맨 이동
- makeMove(): 팩맨의 이동 경로 정하기 위한 재귀 함수
- 재귀로 깊이가 3
- 상-좌-하-우의 우선순위를 가지며 이동
- 이동 경로에 몬스터를 2번 이상 참조하지 않도록 방문 처리
- 팩맨의 이동 경로 결정이 끝났으면 이동 경로에 있는 몬스터 슥.삭. 및 시체 추가
popEggs(): 몬스터 복제 시 Queue에 저장했던 정보를 꺼내 보드에 추가

설명 쓰기 빡세군요.. 엄청난 구현 문제였습니다.

🤔 시간복잡도 고려사항

4 * 4
턴 수: t ≤ 25
팩맨 이동 경우의 수 : 4^3 = 64
최대 몬스터 개수 <= 100만개

턴이 진행되는 동안 살아있는 몬스터의 수가 100만개가 넘는 입력은 주어지지 않는다고 가정해도 좋습니다.
단, 몬스터들은 한칸에 여러개가 있을 수 있므로 총 4 * 4= 16칸만 확인하면 모든 몬스터들을 확인할 수 있음

=> 최대 경우의 수 : O( t 64 16) => 완전탐색 가능

💡 풀이 아이디어

알과 몬스터는 한 칸에 여러개씩 존재할 수 있으므로 배열리스트로 관리

2차원 배열을 1차원으로 관리하기

N = 4

g[1][1] = a[1 * N + 1]


// 알 리스트 배열
static List<Integer>[] egg;
// 몬스터 리스트 배열
static List<Integer>[] mrr;

** 각각의 배열 리스트에는 알, 몬스터의 방향이 저장됨



**1. 몬스터 복제 시도** : `makeEgg()` 
- 알 생성하기
- 살아있는 몬스터들과 동일한 위치와 동일한 방향으로 알 생성하기

**2. 몬스터 이동** : `moveMonster()` 
- 몬스터들이 움직여야 하므로 임시 배열 생성해서 몬스터 움직임 저장하기
    - `List<Integer>[] tmp = new ArrayList[N*N];`
- 몬스터 반복
-  이동 할 곳이 범위에 벗어나지 않고 && 팩맨의 위치가 아니고 && 시체의 위치가 아니라면 이동
    - 시체 위치 => `ghost[i][j]`는 (i, j)에서 죽은 몬스터의 턴 수가 기록됨  
- 8방향 모두 돌았는데 이동할 곳이 없다면 원래 위치 저장
- 이동한 몬스터의 임시배열을 원본배열로 저장
    - `mrr = tmp`

**3. 팩맨 이동** : `movePacman()`
- `makePacDir()`: **중복 순열** 구하기
    - `dList` : 우선순위에 따른 팩맨의 이동경로
        - [(상상상), (상상좌), .......] => 64개
    - 미리 팩맨의 이동 경로 구해놓고 반복
- `countMonster(drr)` : 이동경로 drr에 따른 먹을 수 있는 몬스터 개수 구하기
    - ❗  이때 주의해야 할 점은,  경로에서 먹었던 몬스터를 또 먹으면 안되므로 방문배열로 기록하기
- 가장 많이 먹을 수 있는 이동 경로를 구하고, 팩맨 이동시키기
- 시체 기록하기
    - `ghost[i][j] = nowTurn` : 팩맨이 (i, j)에서 몬스터를 먹은 턴수 기록
    - (시체는 같은 위치에 또 다른 시체가 생기면 가장 최근에 생긴 턴 수에 +2 만큼 후에 없어지므로 갱신해도 됨)

**4. 몬스터 시체 소멸** : `removeGhost()`
- `ghost[i][j] + 2`가 nowTurn과 같으면 해당 시체는 소멸됨

**5. 몬스터 복제 완성**
- `egg`에 있던 알들을 몬스터 배열 리스트 `mrr`에추가

> 팩맨의 이동 경로에서 먹었던 몬스터를 다시 먹지 않는 것을 주의해야 하는 문제인 것 같습니다

GreatAlgorithm-Study / AlgorithmStudy

[11주차_월요일] 팩맨 #143

🤔 시간복잡도 고려사항

💡 풀이 아이디어

🤔 시간복잡도 고려사항

💡 풀이 아이디어

🤔 시간복잡도 고려사항

💡 풀이 아이디어