백준 23290 : 마법사 상어와 복제

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

23290번: 마법사 상어와 복제

1. 차근차근해봅시다.

 반년만에 다시 풀어보는 문제. 구현할게 너무나도 많다. 본 문제에서는 크게 3가지로 쪼개서 생각했다.

• copy() : 초기에 물고기 위치들을 복사해준다.
• move() : 물고기 먼저 움직여주고, 그다음 상어가 이동할 곳을 찾아 이동한다.
• diminish() : 냄새를 하나씩 지워준다.

 먼저 copy().

복사하는 것은 어렵지 않다. 굳이 함수로 안 만들어도 되긴 하는데 그냥 만들었다.

def copy():
    return [arr for arr in f_info]

 

두 번째로 move().

물고기의 새로운 위치들을 담을 b_temp 배열을 만들었다. board에 있는 것들을 가져다가 할 수도 있지만 알아보기 쉽게 하기 위해서 임시 보드에다가 새 좌표를 넣어주고 그것을 board에 다시 업데이트하는 식으로 했다. 블로그 작성하면서 생각해보니 그냥 board만 활용해도 될 듯?

f_info에서 물고기 위치 정보들을 불러와서 길을 탐색한다. 8방향을 다 탐색해도 갈 곳이 없을 때에는 자기 자리에서 그대로 있도록 한다. 

# fish
b_temp = [[[] for _ in range(4)] for _ in range(4)]
for i, (x, y, d) in enumerate(f_info) :
    cnt = 0
    while True :
        nx = x + fdx[d]
        ny = y + fdy[d]
        if cnt == 8 : break
        if nx < 0 or nx >= 4 or ny < 0 or ny >= 4 :
            d = (d - 1) % 8
            cnt += 1
            continue
        if 0 <= nx < 4 and 0 <= ny < 4 :
            if smell[nx][ny] > 0 or [nx, ny] == [sx, sy] :
                d = (d - 1) % 8
                cnt += 1
                continue
            elif smell[nx][ny] == 0 :
                b_temp[nx][ny].append(d)
                break
    if cnt == 8 :
        b_temp[x][y].append(d)
# Board Update
for i in range(4):
    for j in range(4):
        board[i][j] = b_temp[i][j]

 이제 상어를 움직여줘야 한다. 상어의 움직임에 관한 정보는 64가지 밖에 안되니, 완전 탐색으로 확인해주었다. 여기서 주의해야 할 것은 상어가 갔던 길을 다시 돌아갈 수도 있다는 점이다! [상, 하, 상] 같은 경우가 가능하니 이점 주의해주어야 한다. 이것 때문에 좀 헤맸다. 상어가 가는 길에 따른 물고기 먹을 수 있는 수는 딕셔너리로 관리했다. try & except을 이용해서 쉽게 만들 수 있고, 사전 순서에 맞게 경우의 수를 배치했으니 물고기를 먹을 수 있는 가장 큰 값의 0번째 인덱스를 사용하면 된다. 소스코드는 다음과 같다.

# shark : Count 3, Fish
temp = {}
for d1, d2, d3 in comb :
    cnt = 0
    check = True
    x, y = sx, sy
    visited = [[False for _ in range(4)] for _ in range(4)]
    for d in [d1, d2, d3] :
        nx = x + dx[d]
        ny = y + dy[d]
        if nx < 0 or nx >= 4 or ny < 0 or ny >= 4 :
            check = False
            break
        elif 0 <= nx < 4 and 0 <= ny < 4 :
            if not visited[nx][ny] :
                if len(board[nx][ny]) >= 1 :
                    cnt += len(board[nx][ny])
                    visited[nx][ny] = True
                x, y = nx, ny
            else :
                x, y = nx, ny
    if check :
        try :
            temp[cnt] += [[d1, d2, d3]]
        except :
            temp[cnt] = [[d1, d2, d3]]
    else :
        continue
maxKey = max(temp)
x, y = sx, sy
for d in temp[maxKey][0] :
    nx = x + dx[d]
    ny = y + dy[d]
    if len(board[nx][ny]) >= 1 :
        board[nx][ny] = []
        smell[nx][ny] = 3
    x, y = nx, ny
sx, sy = nx, ny
size = len(f_info)
del f_info[:size]
for i in range(4):
    for j in range(4):
        if len(board[i][j]) >= 1 :
            for k in range(len(board[i][j])):
                f_info.append([i, j, board[i][j][k]])

마지막으로 diminish(),

이것 또한 쉽게 할 수 있다.

def diminish():
    for i in range(4):
        for j in range(4):
            if smell[i][j] > 0 :
                smell[i][j] -= 1

2. 전체 코드

메모리 : 361892 KB, 시간 : 952 ms, 풀이 시간 : 90분

M, S = map(int, input().split())
f_info = [list(map(int, input().split())) for _ in range(M)]
board = [[[] for _ in range(4)] for _ in range(4)]
smell = [[0 for _ in range(4)] for _ in range(4)]
sx, sy = map(int, input().split())
sx -= 1
sy -= 1
for i in range(len(f_info)):
    f_info[i][0] -= 1
    f_info[i][1] -= 1
    f_info[i][2] -= 1

# 초기조건
for i in range(len(f_info)):
    board[f_info[i][0]][f_info[i][1]].append(f_info[i][2]) # fish
comb = []
for i in range(4):
    for j in range(4):
        for k in range(4):
            comb.append([i, j, k])

# 상, 좌, 하, 우 for shark
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# 좌, 좌상, 상, 상우, 우, 우하, 하, 하좌 for fish
fdx = [0, -1, -1, -1, 0, 1, 1, 1]
fdy = [-1, -1, 0, 1, 1, 1, 0, -1]
def copy():
    return [arr for arr in f_info]

def move():
    global sx, sy
    # fish
    b_temp = [[[] for _ in range(4)] for _ in range(4)]
    for i, (x, y, d) in enumerate(f_info) :
        cnt = 0
        while True :
            nx = x + fdx[d]
            ny = y + fdy[d]
            if cnt == 8 : break
            if nx < 0 or nx >= 4 or ny < 0 or ny >= 4 :
                d = (d - 1) % 8
                cnt += 1
                continue
            if 0 <= nx < 4 and 0 <= ny < 4 :
                if smell[nx][ny] > 0 or [nx, ny] == [sx, sy] :
                    d = (d - 1) % 8
                    cnt += 1
                    continue
                elif smell[nx][ny] == 0 :
                    b_temp[nx][ny].append(d)
                    break
        if cnt == 8 :
            b_temp[x][y].append(d)
    # Board Update
    for i in range(4):
        for j in range(4):
            board[i][j] = b_temp[i][j]
    # shark : Count 3, Fish
    temp = {}
    for d1, d2, d3 in comb :
        cnt = 0
        check = True
        x, y = sx, sy
        visited = [[False for _ in range(4)] for _ in range(4)]
        for d in [d1, d2, d3] :
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or nx >= 4 or ny < 0 or ny >= 4 :
                check = False
                break
            elif 0 <= nx < 4 and 0 <= ny < 4 :
                if not visited[nx][ny] :
                    if len(board[nx][ny]) >= 1 :
                        cnt += len(board[nx][ny])
                        visited[nx][ny] = True
                    x, y = nx, ny
                else :
                    x, y = nx, ny
        if check :
            try :
                temp[cnt] += [[d1, d2, d3]]
            except :
                temp[cnt] = [[d1, d2, d3]]
        else :
            continue
    maxKey = max(temp)
    x, y = sx, sy
    for d in temp[maxKey][0] :
        nx = x + dx[d]
        ny = y + dy[d]
        if len(board[nx][ny]) >= 1 :
            board[nx][ny] = []
            smell[nx][ny] = 3
        x, y = nx, ny
    sx, sy = nx, ny
    size = len(f_info)
    del f_info[:size]
    for i in range(4):
        for j in range(4):
            if len(board[i][j]) >= 1 :
                for k in range(len(board[i][j])):
                    f_info.append([i, j, board[i][j][k]])

def diminish():
    for i in range(4):
        for j in range(4):
            if smell[i][j] > 0 :
                smell[i][j] -= 1

def solve():
    it = 0
    while it < S :
        copy_fish = copy()
        move()
        diminish()
        for x, y, d in copy_fish :
            f_info.append([x, y, d])
            board[x][y].append(d)
        it += 1
    result = 0
    for i in range(4):
        for j in range(4):
            if len(board[i][j]) > 0 :
                result += len(board[i][j])
    print(result)

solve()