[백준][구현] 마법사 상어와 복제

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

23290번: 마법사 상어와 복제

 

내가 작성한 코드

import sys
from collections import deque, defaultdict

read = sys.stdin.readline

fish_dir = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]
shark_dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]

def read_data():
    M, S = map(int, read().rstrip().split())
    fish = defaultdict(deque)

    for _ in range(M):
        r, c, d = map(lambda x: x-1, map(int, read().rstrip().split()))
        fish[(r, c)].append(d)

    shark = tuple(map(lambda x: x-1, map(int, read().rstrip().split())))

    return M, S, fish, shark

def duplicate_fish(fish):
    dup = defaultdict(deque)
    for k, v in fish.items():
        dup[k] = v.copy()
    return dup

def fish_move(fish, shark, smell):
    nw_fish = defaultdict(deque)
    for k, q in fish.items():
        while q:
            r, c = k
            d = q.popleft()
            dd = d

            for _ in range(8):
                d_r, d_c = fish_dir[d]
                nw_r, nw_c = r+d_r, c+d_c

                if not (shark[0] == nw_r and shark[1] == nw_c) and\
                    not smell[(nw_r, nw_c)][-1] and\
                    0 <= nw_r < 4 and 0 <= nw_c <4:
                    r = nw_r
                    c = nw_c
                    break
                d = d-1 if d-1>=0 else 7

            nw_fish[(r, c)].append(d)
    return nw_fish

def is_shark_move(move):
    for r, c in move:
        if not (0 <= r < 4 and 0 <= c < 4):
            return False
    return True

def shark_move(fish, shark, smell, rm_smell, S):
    r, c = shark
    move = []
    final_move = []
    mx_fish = -1
    for d_r1, d_c1 in shark_dir:
        nw_r1, nw_c1 = r+d_r1, c+d_c1
        move.append((nw_r1, nw_c1))
        for d_r2, d_c2 in shark_dir:
            nw_r2, nw_c2 = move[-1][0]+d_r2, move[-1][1]+d_c2
            move.append((nw_r2, nw_c2))
            for d_r3, d_c3 in shark_dir:
                nw_r3, nw_c3 = move[-1][0]+d_r3, move[-1][1]+d_c3
                move.append((nw_r3, nw_c3))

                if is_shark_move(move):
                    num_fish = 0
                    for i, j in set(move):
                        num_fish += len(fish[(i, j)])
                    if num_fish > mx_fish:
                        mx_fish = num_fish
                        final_move = move[:]

                move.pop()
            move.pop()
        move.pop()

    for r, c in final_move:
        if fish[(r, c)]:
            smell[(r, c)].append(True)
            rm_smell.append((S + 2, (r, c)))
            while fish[(r, c)]:
                fish[(r, c)].pop()

    return final_move[-1]

def remove_smell(smell, rm_smell, S):
    while rm_smell and S == rm_smell[0][0]:
        s, t = rm_smell.popleft()
        smell[t].pop()

def release_fish(dup, fish):
    for k, q in dup.items():
        while q:
            fish[k].append(q.popleft())

def get_answer(M, S, fish, shark):
    smell = defaultdict(lambda : [False])
    rm_smell = deque()
    for s in range(S):
        dup = duplicate_fish(fish)
        fish = fish_move(fish, shark, smell)
        shark = shark_move(fish, shark, smell, rm_smell, s)
        remove_smell(smell, rm_smell, s)
        release_fish(dup, fish)

    return sum([len(q) for q in fish.values()])


M, S, fish, shark = read_data()
print(get_answer(M, S, fish, shark))

• 상어 이동
  
  • 3차원 for문에서 우선순위 순서대로 탐색
  • 물고기의 최대보다 넘는 경우만 업데이트 할 경우 우선순위를 고려할 수 있음
• 물고기 냄새
  • 좌표에 물고기 냄새를 bool로 표현할 경우, 냄새가 2번 겹치는 처리가 불가능
  • Stack을 이용 -> [False]를 시작으로 -1 인덱스의 값으로 비교
  • [False, True, True]일 경우, 냄새가 제거되도 냄새가 남아있음(두번째 True)

 

다른 사람이 작성한 코드

None

• 강한 구현 문제로 더 간단한 방법을 찾지 않음

 

기억해야할 것

• 조건에 부합하는 구현 확인
  
  • 구현한 코드에서 조건에 맞는 기능을 수행하는지 확인할 것 (구현이 잘못되어 디버깅하게됨)