23290 - 마법사 상어와 복제

 

---

 

문제

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

23290번: 마법사 상어와 복제

 

풀이

문제에서 명시한대로 스텝을 밞아나가면서 구현하면 풀 수 있다. (단순하지 않아서 그렇지..)

 

우선 나는 입력값을 배열에 저장해뒀다. 그리고 해당 위치에 특정 방향으로 바라보는 물고기가 몇개 있는지 저장해뒀다.

처음에는 물고기를 하나하나당 요소로 저장해뒀는데 이게 시간초과의 주범이었다. 그래서 [1,1] 위치에 1의 방향으로 바라보는 물고기가 몇 개 있는지, 이런식으로 구현해서 풀이했다. 

 

1. 복제 마법을 선언한다.
   • 현재 존재하는 물고기의 위치와, 방향을 저장해둔다.
   • 특별한 로직은 없다, 기존에 저장해둔 물고기 배열을 탐색하면서 위치, 방향, 개수를 체크해두고 저장해두면 된다.
2. 모든 물고기가 이동한다.
   • 우선 기존 배열과 별개로, 이동후의 결과를 저장할 배열을 만든다.
     
     • 이렇게 하는 이유는 내 코드는 0,0에서 n-1, n-1의 물고기들의 이동 검사를 모두 수행하는데 0, 0에서 1,1 로 이동한 경우 물고기가 1,1에서 또 이동할 수 있기 때문이다.
   • 반시계방향으로 이동하면서 물고기 냄새가 없고, 상어가 없는곳으로 이동한다. 
     • 현재 바라보는 방향부터 시작해서 반시계방향으로 돌면서 갈 수 있다면 이동시켜준다. 단 8번 돌아서 제자리에 올 때 까지 이동되지 않았다면, 결과 배열에 지금 위치값을 그대로 넘겨준다.
     • 결과 배열에 넘겨줄때는 += 연산자를 사용해야한다. = 을 사용하면 누적된 값이 아니니까 유의하자.
3. 상어가 연속해서 3칸 이동한다.
   • 우선 상어는 물고기와 달리 상하좌우로만 이동이 가능하다.
   • 상어는 방문했던 칸을 다시 방문할 수 있다. (그러나 물고기가 두번 체킹되면 안된다.)
   • 상어가 있는 위치의 물고기는 먹지 않는다. 이동했던 3칸의 물고기만 먹는다.
   • dfs를 활용해서 방문한 칸이 3칸일 경우에 비교를 해서 최적의 루트를 찾으면 된다.
     • 최적의 루트를 찾기 위해 필요한것은 상어가 먹은 물고기, 상어의 이동방법 이다. 상어가 방문한 칸의 좌표들도 저장해둔다.
     • 상어가 먹은 물고기 같은 경우에는 상어가 방문한 좌표를 참고해서 계산하면 된다. 단 이때 상어가 "상하상" 으로 방문한 곳을 또 방문했을 수 있다. 물고기는 중복되서 체크되면 안되기에 이 때 set으로 중복을 없앤후에 물고기 수를 계산했다.
     • 방향 결과값 같은 경우에는 dfs를 하면서 문자열로 추가해주고, 마지막에 비교할때 int로 바꾸어서 비교해준다.
     • 기존의 루트보다 현재 루트가 물고기를 많이 먹었다면 갱신해준다.
     • 만약 먹은 물고기는 같은데, 상어의 이동방법이 사전순으로 앞선다면 갱신해주면 된다.
   • dfs 로 최적의 결과를 냈다면 상어가 지나온 곳은 물고기를 없애주고, 냄새를 남긴다.
     • 냄새는 물고기가 있었던 곳에만 남겨야한다. 
     • 상어가 방문한 칸의 좌표들을 체크하면서 물고기가 있었다면 빈값으로 만들어주고 냄새를 남겨주면 된다.
4. 물고기 냄새가 옅어진다.
   • 물고기 냄새가 존재하는곳은 -1씩 해주면 된다.
5. 복제마법이 수행된다.
   • 1에서 저장해두었던 배열을 활용해서 물고기 배열에 물고기들을 추가해주면 된다.

 

코드

import copy

def changeDir(val):
    if val == 1: return 8
    return val-1

def copyFish():
    global board
    temp = []
    for i in range(4):
        for j in range(4):
            # 방향 모두를 체크한다.
            for k in range(1, 9):
                if board[i][j][k] == 0: continue
                # board[i][j][k] 의 수를 기억한다.
                temp.append([i, j, k, board[i][j][k]])
    return temp

def moveFish():
    global board, smell, dx, dy, sp
    tempBoard = [[[0 for _ in range(9)] for _ in range(1) for _ in range(4)] for _ in range(4)]

    for i in range(4):
        for j in range(4):
            for k in range(1, 9):

                direction = k
                moved = False
                for _ in range(8):
                    nx = i + dx[direction]
                    ny = j + dy[direction]
                    # 격자에 들어가면서, 상어가 없고, 냄새가 없는칸으로 물고기가 이동이 가능하다.
                    if 0<=nx<4 and 0<=ny<4 and smell[nx][ny] == 0 and not (nx == sp[0] and ny == sp[1]) :
                        tempBoard[nx][ny][direction] += board[i][j][k]
                        moved = True
                        break
                    else:
                        direction = changeDir(direction)

                if not moved:
                    tempBoard[i][j][k] += board[i][j][k]
    return tempBoard


def dfs(x, y, dis, way, positions):
    global board, globalWay, globalFishCnt, globalPositions

    if dis == 3:
        fishCnt = 0
        # 지나온 길 중복을 막기 위해 set을 사용
        setPosition = set()
        for p in positions:
            setPosition.add(p)

        # 지나온 길에 존재했던 총 물고기의 개수를 체크한다.
        for p in setPosition:
            for v in board[p[0]][p[1]]:
                fishCnt += v

        if fishCnt > globalFishCnt:
            globalFishCnt = fishCnt
            globalWay = int(way)
            globalPositions = copy.deepcopy(positions)
        elif fishCnt == globalFishCnt and int(way) < globalWay:
            globalFishCnt = fishCnt
            globalWay = int(way)
            globalPositions = copy.deepcopy(positions)
        return

    # 상어는 상하좌우만 가능하다.
    for i in square:
        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<4 and 0<=ny<4:
            positions.append((nx, ny))
            dfs(nx, ny, dis+1, way+transition[i], positions)
            positions.pop()

def moveShark():
    global board, sp, smell, globalWay, globalFishCnt, globalPositions

    # globalPositions => 상어가 지나온 좌표들
    # globalFishCnt => 상어가 지나온 좌표들에 존재했던 물고기 개수
    # globalWay => 상어가 지나온 길, 사전순 정렬 필요

    dfs(sp[0], sp[1], 0, '', copy.deepcopy(globalPositions))

    # 상어가 지나온 길 중 물고기가 있다면 해당 위치엔 냄새를 추가해주고, 물고기를 비워준다.
    for p in globalPositions:
        for v in board[p[0]][p[1]]:
            if v >= 1:
                board[p[0]][p[1]] = [0] * 9
                smell[p[0]][p[1]] = 3
                break

    # 상어 위치를 이동시켜준다.
    sp = (globalPositions[-1][0], globalPositions[-1][1])

def fadeSmell():
    global smell
    for i in range(4):
        for j in range(4):
            if smell[i][j] != 0: smell[i][j] -=1

def excuteMagic(copyValue):
    global board
    for x, y, k, val in copyValue:
        board[x][y][k] += val

def getFish():
    global board
    ans = 0
    for i in range(4):
        for j in range(4):
            for k in range(1, 9):
                ans += board[i][j][k]
    return ans

globalWay = 999
globalFishCnt = 0
globalPositions = []

transition = {1:'2', 3:'1', 5:'4', 7:'3'}
dx = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dy = [0, -1, -1, 0, 1, 1, 1, 0, -1]
square = [1,3,5,7]

m, s = map(int, input().split())

# [x][y][n방향으로 바라보는 물고기의 수]
board = [ [ [ 0 for _ in range(9) ] for _ in range(1) for _ in range(4)] for _ in range(4) ]
smell = [ [0] * 4 for _ in range(4) ]

# 초기화
for _ in range(m):
    x, y, d = map(int, input().split())
    board[x-1][y-1][d] += 1
x,y = map(int, input().split())
sp = (x - 1, y - 1)


for _ in range(s):
    globalWay = 999
    globalFishCnt = 0
    globalPositions = []

    # 1. 모든 물고기를 복제한다.
    copyValue = copyFish()

    # 2. 모든 물고기는 반시계 방향으로 돌면서 이동 위치를 찾고 이동한다.
    board = moveFish()

    # 3. 상어가 최적의 위치로 이동한다.
    moveShark()

    # 4. 냄새가 옅어진다.
    fadeSmell()

    # 5. 복제마법이 수행된다.
    excuteMagic(copyValue)

print(getFish())

 

후기

 

놓칠 수 있는 조건들이 정말 많다. 

1. 상어가 지나간 곳 이 아니라, 지나간 곳 중 물고기가 있는곳만 냄새 남기기.

2. 상어가 방문한 칸을 다시 방문할 수 있음.

3. 상어가 초기에 위치한 칸에서는 물고기를 먹지 않음.

4. 상어는 8방향이 아니라 상하좌우로만 이동 가능함.

 

난 풀면서 위 조건들을 한번씩 다 놓쳤고, 마지막에는 += 연산자를 사용해야하는데 = 를 사용해서 틀렸다.

 

조건을 꼼꼼히 정리한다고 하고 작성했는데도 아직 쉽지않다. 코드의 분량이 많아지니 디버깅도 정말 어렵다. 

 

명시되어있는 행동과 아닌 행동들을 잘 파악하며 구현연습을 계속 해야겠다.