[BOJ/백준] 23290 마법사 상어와 복제

import sys
def input():
    return sys.stdin.readline().rstrip()

def make_aqua():
    return [[[0 for _ in range(8)] for _ in range(4)] for _ in range(4)]
def outOfBound(x,y):
    if 0<=x<4 and 0<=y<4:
        return False
    return True

def move_fish(arr,T):
    new_aqua = make_aqua()
    for x in range(4):
        for y in range(4):
            for d in range(8):
                if arr[x][y][d]:
                    copy_d = d
                    for _ in range(8):
                        nx = x + dx[copy_d]
                        ny = y + dy[copy_d]
                        if outOfBound(nx,ny) or (nx,ny) == sharks or smells[nx][ny] >= T-2:
                            copy_d = (copy_d-1)%8
                        else:
                            new_aqua[nx][ny][copy_d] += arr[x][y][d]
                            break
                    else:
                        new_aqua[x][y][d] += arr[x][y][d]
    return new_aqua

def shark_swim(x,y,move,shark_dict,kill,visited):
    if len(move) == 3:
        shark_dict[move] = kill
        return
    else:
        for i in range(1,5):
            nx = x + shark_dx[i]
            ny = y + shark_dy[i]
            if outOfBound(nx,ny):continue
            if (nx,ny) not in visited:
                new_kill = sum(aqua[nx][ny])
                visited.add((nx,ny))
                shark_swim(nx,ny,move+str(i),shark_dict,kill + new_kill,visited)
                visited.remove((nx,ny))
            else:
                shark_swim(nx,ny,move+str(i),shark_dict,kill,visited)
def sharks_move(sharks,T):
    x,y = sharks
    shrks_dict = {}
    shark_swim(x,y,'',shrks_dict,0,set())
    move_sort = sorted(shrks_dict.keys(),key= lambda x : (-shrks_dict[x],x))
    for d in move_sort[0]:
        d = int(d)
        nx = x + shark_dx[d]
        ny = y + shark_dy[d]
        for i in range(8):
            if aqua[nx][ny][i]:
                aqua[nx][ny][i] = 0
                smells[nx][ny] = T
        x,y = nx,ny
    return x,y



N,S = map(int,input().split())
aqua = make_aqua()

for _ in range(N):
    x,y,d = map(int,input().split())
    aqua[x-1][y-1][d-1] += 1

dx = [0,-1,-1,-1,0,1,1,1]
dy = [-1,-1,0,1,1,1,0,-1]
shark_dx = [0,-1,0,1,0]
shark_dy = [0,0,-1,0,1]
smells = [[-float('inf') for _ in range(4)] for _ in range(4)]
sharks = tuple(map(lambda x: x-1,map(int,input().split())))
time = 0
while time<S:
    copy_aqua = [[col[:] for col in row] for row in aqua]
    aqua = move_fish(aqua,time)
    sharks = sharks_move(sharks,time)
    for x in range(4):
        for y in range(4):
            for d in range(8):
                aqua[x][y][d] += copy_aqua[x][y][d]

    time += 1

result = 0

for x in range(4):
    for y in range(4):
        result += sum(aqua[x][y])
print(result)

 

이 문제는 문제를 읽어보면 물고기의 개개로 움직이게 되면, 시간의 소모가 많이 되는것을 알 수 있다.

 

만약 물고기가 100만개를 일일히 전부 움직이고

 

최악의 경우를 생각해보면 1턴마다 100만*8의 이동이 되게 되고, 그것이 최대 100턴 지속되면 1억을 넘어가게 되서 시간초가가 날수도 있는 점을 생각해보면, 이 문제는 물고기의 위치와 방향에 따라 한꺼번에 움직이는 방식으로 해결해야함 을 알 수 있다.

 

먼저 4*4*8 크기의 aqua라는 수족관 배열을 만들어놓는다. 이 배열안에 입력으로 주어진 물고기의 위치와 방향에 맞게

 

넣어주면 된다.

 

이 문제도 삼성 기출 대부분이 그런것처럼 각 단계별이 있고, 그 단계에 맞게 시키는 것을 진행하면 된다.

 

그렇기 때문에 이 문제에서도 최대한 단계별에 맞게, 함수로 만들어서 진행을 했다.

 

1단계는 현재 수족관에 있는 물고기에게 복제 마법을 하는 것이다.

 

그렇다는 것은 현재 aqua에 있는 물고기 정보를 어디에 저장을 해야하기 때문에, 나는 copy_aqua라는 배열에,

 

현재 aqua의 물고기 정보를 저장해두었다.

 

여기서 deepcopy를 써도 되지만, 시간적으로 더 늦게 복사되기 때문에 list comprehension를 통해 복사를 해두었다.

 

2단계는 물고기가 움직이는 단계이다. 

 

물고기는 범위를 벗어나서도 안되고, 상어와 위치가 겹쳐서도 안되며, 물고기의 냄새가 있으면 안된다고 되어있다.

 

그리고 움직일 방향이 있을때까지 반시계 45도 방향으로 회전을 하며, 만약에 움직일 방향이 없으면 그 자리에 있는다.

 

라는 조건이 있다.

 

이 이동을 해결한 방법은 다음과 같다. 현재 물고기의 위치 x,y 와 방향 d가 있다하면,

 

우리는 문제에서 주어진 1~8의 이동방향이 숫자가 늘어남에 따라 시계방향으로 회전한다는 것을 알 수 있다.

 

그러면 우리는 반시계 45도 방향이라는 것은 주어진 이동방향 1~8을 각각 0~7로 변화시켰을때, 

 

(현재 이동방향-1)%8 을 하면, 반시계 45도 회전한 이동방향이 나옴을 알 수 있다.

 

그러면 우리는 총 8번의 반복을 하면서 범위를 벗어나거나, 상어가 존재하거나, 물고기 시체가 있을때에는

 

(이동방향 -1)%8을 해주면서 물고기를 계속 회전 시켜주면 된다는 것을 알 수 있다.

 

여기서 주의해야할 점은 원본의 이동방향은 그대로 냅두어야하기 때문에, copy_d라는 변수를 만들어 회전을 담당하는 변수를 새로 만들어줬다.

 

이렇게 해서 위의 3조건에 만족하지 않는 공간이 있을때에는 새 수족관에 더해주면 된다.

 

그리고 여기서도 for else문을 통해 8번의 방향전환동안, 물고기가 움직일 공간이 없을때에는,

 

현재 위치에 더해주는 로직을 해주었다.

 

여기서 중요한 물고기 시체와 관련된 사항은 밑에서 적도록 하겠다.

 

 

3번째 단계는 상어가 이동하는 단계이다.

 

상어는 상하좌우로 인접한 곳으로 이동을 하며, 이동하는 도중에 격자 범위를 벗어나는 이동은 무시한다고 되어있다.

 

이 상어 이동은 재귀를 통해 구현을 했으며, 재귀를 함에 있어서 주의해야할 점은

 

한번 물고기 먹은 곳을 당신 방문했을 때, 물고기를 먹는것을 중복해서 하지 않도록 방문 표시를 제대로 해주면 된다.

 

 

이렇게 상어의 모든 이동에 대해, 판별을 해준뒤 sort를 통해 물고기를 가장 많이 먹으면서,

 

이동방향이 사전순이 녀석으로 이동을 시켜준다.

 

여기서 물고기의 시체를 남겨두는 작업을 해야하는데, 이 물고기의 시체는 2턴뒤에 사라져야한다.

 

이 것을 따로 하나하나 초기화 하기에는 복잡하다고 생각되어,

 

4*4 크기의 smells라는 배열을 만들고, 거기에 물고기 시체가 생긴 턴을 적어두는 것으로 문제점을 해결했다.

 

 

smells[x][y] >= T- 2

 

특정위치의 냄새의 값이 현재턴에서 -2 한 값보다 크거나 같다는 것은 1턴전 혹은 2턴전에 물고기 시체가 되었다는 것을 의미하게 되고,

 

이렇게 표시하는 것만으로 자동적으로 2턴이 지난후에는 냄새가 사라지는것처럼 구현을 할 수 있다는 장점이 있다.

 

마지막으로 우리가 제일 첫번째에 해놓았던, copy_aqua를 원래 aqua에 더해주는 것으로

 

한 턴을 마무리 하면 된다.

 

문제에 주어진 턴을 모든 소모한뒤에 aqua에 남아있는 물고기의 수를 구해서 출력해주면 된다.

 

이 문제에서 주의해야했던 점은 몇가지가 있는데,

 

물고기의 시체가 2턴마다 사라지는 것을 어떻게 구현할 것인가와

 

상어의 이동방향은 어떻게 구현할것인가

 

그리고 물고기의 이동은 어떻게 구현할 것인가이다.

 

였다. 이 3부분에 대한 효율적으로 로직을 짜야했던 문제였다.

 

이 문제를 풀 때 1시간 30분이 걸렸는데, 30분동안 디버깅한게 tuple하고 list를 비교연산자로 비교해서 틀렸던 거였다..

 

list와 tuple은 타입이 다른 것을 다시 깨닫게 되었다.. 망할

 

 

 

def shark_swim(x,y,move,kill,visited):
    if len(move) == 3:
        return (kill,move)
    else:
        temp = (0,'000')
        for i in range(1,5):
            nx = x + shark_dx[i]
            ny = y + shark_dy[i]
            if outOfBound(nx,ny):continue
            if (nx,ny) not in visited:
                new_kill = sum(aqua[nx][ny])
                visited.add((nx,ny))
                temp = max(temp,shark_swim(nx,ny,move+str(i),kill + new_kill,visited))
                visited.remove((nx,ny))
            else:
                temp = max(temp,shark_swim(nx,ny,move+str(i),kill,visited))
        return temp

def sharks_move(sharks,T):
    x,y = sharks
    _,max_move = shark_swim(x,y,'',0,set())
    for d in max_move:
        d = int(d)
        nx = x + shark_dx[d]
        ny = y + shark_dy[d]
        for i in range(8):
            if aqua[nx][ny][i]:
                aqua[nx][ny][i] = 0
                smells[nx][ny] = T
        x,y = nx,ny
    return x,y
    
    
shark_dx = [0,0,1,0,-1]
shark_dy = [0,1,0,-1,0]

dict를 사용하지 않고, 재귀를 통해 max값을 되돌려주는 방식으로도 풀수 있다.

 

튜플로 max를 비교할수 있기 때문에 가능한 것이고, 이때는 앞에서는 1,2,3,4에 맞춰서 상좌우하를 만들었는데, 여기서는 반대로 더 높은숫자가 나올수 있도록 상좌우하를 4,3,2,1에 매핑을 시켜두었다.