19236 - 청소년 상어

 

---

 

문제

https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

 

풀이

 

구현 + 완전탐색 문제다.

 

처음에는 greedy로 시도해봤으나, 맞지않았고 완탐이 맞았다.

재귀로 구현했는데, 스케일이 굉장히 큰 재귀라.. 굉장히 까다로웠다.

 

흐름자체는 간단하다.

 

1. 물고기 작은 순서대로 swap 실행
   • 나는 dictionary를 활용하여 [물고기번호] = [좌표] 식으로 저장했고, 번호순으로 오름차순 정렬하여 작은 물고기부터 swap할 수 있도록 구성했다. 그리고 저장해놓은 방향부터 반시계방향으로 돌면서 이동할 수 있으면 바로 이동하고, 8번 다 돌았는데도 이동 못했다면 이동하지 않도록 했다.
2. 상어가 갈 수 있는 모든 곳을 방문한다.
   • 상어가 만약 오른쪽을 바라보고 있고, 갈 수 있는 칸이 3개있다고 하자. 그러면 1번째 칸에 가서 다시 재귀적으로 함수를 수행하고, 경계를 벗어날때까지 반복한다. 그 때야 되돌아와서 2번째 칸을 방문하고... 해당 과정을 반복하면 된다. 물고기를 먹은곳은 [0, 0]으로 표시, 상어가 존재하는곳은 [-1, -1]로 표시했다. 
     재귀에서 중요한건 값이 흐트러지지 않는것이다. depth에 따라서 프린트해보면서 디버깅을 섬세하게 하면서 코드를 작성해야한다.
     
     
   • 이동시 굉장히 주의해야할게 하나 있다.  상어는 빈칸으로 이동하지 못한다(물고기가 없는 빈곳),  그러나 빈칸 다음에 물고기가 있다면 그쪽으로는 이동할 수 있다!  ([상어] [빈칸] [물고기] 같은 경우)
     따라서 바로 옆칸이 빈칸이라고 이동할수 없다고 치부하면 안된다. 더이상 이동할수 없는 경우는 배열 범위를 벗어났을때 뿐이다.
     
     이런거 보면 지문을 잘 읽어야한다. 말장난아닌 말장난이 섞여있는 느낌이었다.

 

 

코드

import copy
from sys import stdin
from collections import deque
import heapq

def dfs(fishPosition, sharkPosition, sd, space, total,depth):
    global answer
    # swap 로직
    while True:
        # 물고기 번호 작은 순대로
        for fish in fishPosition:
            x, y = fishPosition[fish]
            v, d = space[x][y]
            cnt = 0
            while True:
                # 이동할 수 있는 방향이 없다면 나간다.
                if cnt == 8: break
                nx = x + dx[d]
                ny = y + dy[d]
                # 범위내이면서, 상어가 없다면 swap해준다.
                if 0 <= nx < 4 and 0 <= ny < 4:
                    if space[nx][ny][0] != -1:

                        # space Swap -> 값을 변경해야한다.
                        tv, td = space[nx][ny]
                        space[x][y] = [tv, td]
                        space[nx][ny] = [v, d]

                        # 빈칸이 아닐경우에만 값 갱신해준다.
                        if tv != 0:
                            fishPosition[tv] = [x, y]
                            fishPosition[v] = [nx, ny]
                        # 빈칸일경우, 한쪽만 값 갱신해주자.
                        if tv == 0:
                            fishPosition[v] = [nx, ny]
                        break
                    else:
                        d = changeDir(d)
                        cnt+=1
                else:
                    d = changeDir(d)
                    cnt += 1

        ox, oy = sharkPosition
        sx, sy = sharkPosition

        # ox, oy => 현재 depth에서 상어가 있는 곳
        # nx, ny => 목표 물고기가 있는곳
        # sx, sy => nx, ny를 만들기 위하여 더하는 중간값

        # 상어가 물고기를 먹는다.
        while True:
            nx = sx + dx[sd]
            ny = sy + dy[sd]
            # 범위에 들어가 있으며, 빈칸이 아닌경우에 갈 수 있다.
            if 0 <= nx < 4 and 0 <= ny < 4:
                if space[nx][ny][0] != 0:

                    # 먹을 물고기의 크기와 방향
                    tv, td = space[nx][ny]

                    # 상어가 원래 있던곳은 빈칸으로 만들어준다.
                    # 또한 우리가 먹을 물고기의 칸은 상어가 위치하는 칸으로 만들어준다.
                    t_space = copy.deepcopy(space)
                    t_space[ox][oy] = [0, 0]
                    t_space[nx][ny] = [-1, -1]

                    # 먹은 물고기는 제거해줌.
                    t_position = copy.deepcopy(fishPosition)
                    t_position.pop(tv)

                    dfs(t_position, [nx ,ny], td, t_space, total + tv, depth+1)

            # 범위를 벗어나면 값 갱신
            else:
                answer = max(answer, total)
                return
            sx = nx
            sy = ny

def changeDir(d):
    if d == 8:
        return 1
    return d+1

# empty, ↑, ↖, ←, ↙, ↓, ↘, →, ↗
dx = [0, -1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 0, -1, -1, -1, 0, 1, 1, 1]

space = [[0] * 4 for _ in range(4)]
fishPosition = {}

for i in range(4):
    temp = list(map(int ,stdin.readline().rstrip().split()))
    space[i][0] = temp[0:2]
    fishPosition[temp[0]] = [i, 0]

    space[i][1] = temp[2:4]
    fishPosition[temp[2]] = [i, 1]

    space[i][2] = temp[4:6]
    fishPosition[temp[4]] = [i, 2]

    space[i][3] = temp[6:8]
    fishPosition[temp[6]] = [i, 3]

fishPosition = dict(sorted(fishPosition.items()))
sharkPosition = [0, 0]
fishPosition.pop(space[0][0][0])
answer = space[0][0][0]
sd = space[0][0][1]
initVal = space[0][0][0]
space[0][0] = [-1, -1]

# dfs로 가능한 곳 모두 가본다.
# 갈곳 없다면 return 한다.
dfs(fishPosition, sharkPosition, sd, space, initVal, 0)

print(answer)

 

후기

 

스케일이 큰 dfs문제.. 재귀같은 경우엔 디버깅 하기가 정말 빡세다. 최대한 조심히 섬세하게 구현해야겠다.

또한 지문에서 명확히 드러나지 않는 부분을 잘 캐치하는것이 중요하다고 느꼈다.