코딩하는 덕구 🐶

148. [삼성기출44]Python 백준 23290 마법사 상어와 복제 본문

알고리즘 문제 풀이

148. [삼성기출44]Python 백준 23290 마법사 상어와 복제

코딩하는 덕구 🐶 2023. 10. 4. 14:49
728x90
반응형

안녕하세요 코딩하는 덕구입니다.

파이썬 백준 23290 마법사 상어와 복제 입니다.

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

 

23290번: 마법사 상어와 복제

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향

www.acmicpc.net

 

from copy import deepcopy
M, S = map(int, input().split())
board = [[[0]*8 for _ in range(4)] for _ in range(4)]
for _ in range(M):
    x, y, d = map(lambda k: int(k) - 1, input().split())
    board[x][y][d] += 1
sx, sy = map(lambda k:int(k) - 1, input().split())

sdx = [-1, 0, 1, 0]
sdy = [0, -1, 0, 1]
fdx = [0, -1, -1, -1, 0, 1, 1, 1]
fdy = [-1, -1, 0, 1, 1, 1, 0, -1]
smell = [[0 for _ in range(4)] for _ in range(4)]
max_eaten = -1
max_path = []

def copy():
    copied = deepcopy(board)
    return copied

def fish_move():
    after_move = [[[0]*8 for _ in range(4)] for _ in range(4)]
    for x in range(4):
        for y in range(4):
            for d in range(8):
                if board[x][y][d]:
                    moved = False
                    for i in range(8):
                        nd = (d - i + 8) % 8
                        nx, ny = x + fdx[nd], y + fdy[nd]
                        if 0 <= nx < 4 and 0 <= ny < 4:
                            if (nx, ny) != (sx, sy):
                                if not smell[nx][ny]:
                                    after_move[nx][ny][nd] += board[x][y][d]
                                    moved = True
                                    break
                    if not moved:
                        after_move[x][y][d] += board[x][y][d]
    return after_move

def shark_move(depth, eaten, path, x, y):
    if depth > 2:
        global max_eaten, max_path, board
        if eaten > max_eaten:
            max_eaten = eaten
            max_path = path
        return

    for d in range(4):
        nx, ny = sdx[d] + x, sdy[d] + y
        if 0 <= nx < 4 and 0 <= ny < 4:
            tmp = board[nx][ny]
            board[nx][ny] = [0]*8
            shark_move(depth + 1, eaten + sum(tmp), path + [[nx, ny]], nx, ny)
            board[nx][ny] = tmp

def eat_fish():
    global sx, sy
    for x, y in max_path:
        if sum(board[x][y]):
            smell[x][y] = 3
        board[x][y] = [0]*8
    sx, sy = max_path[-1]

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

def paste(copied):
    for i in range(4):
        for j in range(4):
            for k in range(8):
                board[i][j][k] += copied[i][j][k]

def solve():
    global board, max_eaten
    for _ in range(S):
        copied = copy()
        board = fish_move()
        shark_move(0, 0, [], sx, sy)
        eat_fish()
        max_eaten = -1
        remove_smell()
        paste(copied)

    ans = 0
    for i in range(4):
        for j in range(4):
            for k in range(8):
               ans += board[i][j][k]
    return ans

def debug():
    for i in range(4):
        for j in range(4):
            print(sum(board[i][j]), end=" ")
        print()
    print()
print(solve())

 

문제 접근

구현 문제라서 버그가 생길 수 있는 부분을 조심하면서 구현하면 된다.

shark_move는 DFS로 완전 탐색했다.

def solve():
    global board, max_eaten
    for _ in range(S):
        copied = copy()
        board = fish_move()
        shark_move(0, 0, [], sx, sy)
        eat_fish()
        max_eaten = -1
        remove_smell()
        paste(copied)

    ans = 0
    for i in range(4):
        for j in range(4):
            for k in range(8):
               ans += board[i][j][k]
    return ans

 

복제는 단순하게 deepcopy로 구현했다. 만약 = 연산자를 사용하면 복제가 아니라 포인터 처럼 적용된다.

def copy():
    copied = deepcopy(board)
    return copied

 

물고기의 움직임이다.

모든 좌표를 돌면서 물고기가 존재하고 이동조건에 맞다면 이동시켰다.

def fish_move():
    after_move = [[[0]*8 for _ in range(4)] for _ in range(4)]
    for x in range(4):
        for y in range(4):
            for d in range(8):
                if board[x][y][d]:
                    moved = False
                    for i in range(8):
                        nd = (d - i + 8) % 8
                        nx, ny = x + fdx[nd], y + fdy[nd]
                        if 0 <= nx < 4 and 0 <= ny < 4:
                            if (nx, ny) != (sx, sy):
                                if not smell[nx][ny]:
                                    after_move[nx][ny][nd] += board[x][y][d]
                                    moved = True
                                    break
                    if not moved:
                        after_move[x][y][d] += board[x][y][d]
    return after_move

 

DFS로 상어가 이동하는 것을 구현했다. 상어가 물고기를 최대한 많이 먹는 이동을 찾는다.

def shark_move(depth, eaten, path, x, y):
    if depth > 2:
        global max_eaten, max_path, board
        if eaten > max_eaten:
            max_eaten = eaten
            max_path = path
        return

    for d in range(4):
        nx, ny = sdx[d] + x, sdy[d] + y
        if 0 <= nx < 4 and 0 <= ny < 4:
            tmp = board[nx][ny]
            board[nx][ny] = [0]*8
            shark_move(depth + 1, eaten + sum(tmp), path + [[nx, ny]], nx, ny)
            board[nx][ny] = tmp

 

상어의 이동을 이용해 물고기를 잡아먹고, 냄새를 남긴다.

상어의 좌표는 상어 이동의 가장 마지막 좌표로 업데이트 해줬다.

def eat_fish():
    global sx, sy
    for x, y in max_path:
        if sum(board[x][y]):
            smell[x][y] = 3
        board[x][y] = [0]*8
    sx, sy = max_path[-1]

 

냄새가 존재하면 1씩 제거해줬다.

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

 

Python 정답 코드

from copy import deepcopy
M, S = map(int, input().split())
board = [[[0]*8 for _ in range(4)] for _ in range(4)]
for _ in range(M):
    x, y, d = map(lambda k: int(k) - 1, input().split())
    board[x][y][d] += 1
sx, sy = map(lambda k:int(k) - 1, input().split())

sdx = [-1, 0, 1, 0]
sdy = [0, -1, 0, 1]
fdx = [0, -1, -1, -1, 0, 1, 1, 1]
fdy = [-1, -1, 0, 1, 1, 1, 0, -1]
smell = [[0 for _ in range(4)] for _ in range(4)]
max_eaten = -1
max_path = []

def copy():
    copied = deepcopy(board)
    return copied

def fish_move():
    after_move = [[[0]*8 for _ in range(4)] for _ in range(4)]
    for x in range(4):
        for y in range(4):
            for d in range(8):
                if board[x][y][d]:
                    moved = False
                    for i in range(8):
                        nd = (d - i + 8) % 8
                        nx, ny = x + fdx[nd], y + fdy[nd]
                        if 0 <= nx < 4 and 0 <= ny < 4:
                            if (nx, ny) != (sx, sy):
                                if not smell[nx][ny]:
                                    after_move[nx][ny][nd] += board[x][y][d]
                                    moved = True
                                    break
                    if not moved:
                        after_move[x][y][d] += board[x][y][d]
    return after_move

def shark_move(depth, eaten, path, x, y):
    if depth > 2:
        global max_eaten, max_path, board
        if eaten > max_eaten:
            max_eaten = eaten
            max_path = path
        return

    for d in range(4):
        nx, ny = sdx[d] + x, sdy[d] + y
        if 0 <= nx < 4 and 0 <= ny < 4:
            tmp = board[nx][ny]
            board[nx][ny] = [0]*8
            shark_move(depth + 1, eaten + sum(tmp), path + [[nx, ny]], nx, ny)
            board[nx][ny] = tmp

def eat_fish():
    global sx, sy
    for x, y in max_path:
        if sum(board[x][y]):
            smell[x][y] = 3
        board[x][y] = [0]*8
    sx, sy = max_path[-1]

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

def paste(copied):
    for i in range(4):
        for j in range(4):
            for k in range(8):
                board[i][j][k] += copied[i][j][k]

def solve():
    global board, max_eaten
    for _ in range(S):
        copied = copy()
        board = fish_move()
        shark_move(0, 0, [], sx, sy)
        eat_fish()
        max_eaten = -1
        remove_smell()
        paste(copied)

    ans = 0
    for i in range(4):
        for j in range(4):
            for k in range(8):
               ans += board[i][j][k]
    return ans

def debug():
    for i in range(4):
        for j in range(4):
            print(sum(board[i][j]), end=" ")
        print()
    print()
print(solve())

 

백준 23290 마법사 상어와 복제 Python 코드였습니다.

감사합니다.

728x90
반응형
저작자표시 (새창열림)

'알고리즘 문제 풀이' 카테고리의 다른 글

149. [삼성기출45]Python 백준 23291 어항 정리  (0) 2024.09.06
147. [삼성기출43]Python 백준 23289 온풍기 안녕! + 디버깅 과정  (0) 2023.09.11
146. [삼성기출42]Python 백준 23288 주사위 굴리기 2  (1) 2023.09.08
145. [삼성기출41]Python 백준 21611 마법사 상어와 블리자드  (0) 2023.09.08
144. [삼성기출40]Python 백준 21610 마법사 상어와 비바라기 시간초과 관련  (0) 2023.09.06
'알고리즘 문제 풀이' Related Articles more