[백준][구현] 어른 상어

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

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

19237번: 어른 상어

 

내가 작성한 코드

from collections import defaultdict, deque

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def read_data():
    N, M, k = map(int, input().rstrip().split())
    board = []
    tmp = defaultdict(tuple)
    shark = defaultdict(tuple)
    for r in range(N):
        for c, i in enumerate(list(map(lambda x: x-1, map(int, input().rstrip().split())))):
            tmp[i] = (r, c)

    for i, d in enumerate(list(map(lambda x: x-1, map(int, input().rstrip().split())))):
        r, c = tmp[i]
        shark[(r, c)] = (i, d)

    shark_priority = []
    for _ in range(M):
        priority = []
        for d in range(4):
            priority.append(list(map(lambda x: x - 1, map(int, input().rstrip().split()))))
        shark_priority.append(priority)

    return N, M, k, shark, shark_priority

def make_smell(shark, smell, rm_smell, t, k):
    for pos, tup in shark.items():
        r, c = pos
        n, d = tup

        smell[(r, c)].append(n)
        rm_smell.append((t+k, r, c))

def in_range(r, c, N):
    return 0 <= r < N and 0 <= c < N

def move(shark, smell, shark_priority, N):
    def deployed_no_smell(r, c, n, d, tmp_shark):
        for nw_d in shark_priority[n][d]:
            nw_r, nw_c = r+dir[nw_d][0], c+dir[nw_d][1]
            if in_range(nw_r, nw_c, N) and smell[(nw_r, nw_c)][-1] == -1:
                tmp_shark[(nw_r, nw_c)].append((n, nw_d))
                return True
        return False

    def deployed_my_smell(r, c, n, d, tmp_shark):
        for nw_d in shark_priority[n][d]:
            nw_r, nw_c = r + dir[nw_d][0], c + dir[nw_d][1]
            if in_range(nw_r, nw_c, N) and smell[(nw_r, nw_c)][-1] == n:
                tmp_shark[(nw_r, nw_c)].append((n, nw_d))
                return True
        return False

    tmp_shark = defaultdict(list)
    nw_shark = defaultdict(tuple)

    for pos, tup in shark.items():
        r, c = pos
        n, d = tup

        if deployed_no_smell(r, c, n, d, tmp_shark):
            continue
        deployed_my_smell(r, c, n, d, tmp_shark)

    for pos, lst in tmp_shark.items():
        r, c = pos
        nw_shark[(r,c)] = tuple(sorted(lst)[0])

    return nw_shark

def remove_smell(t, rm_smell, smell):
    while rm_smell and rm_smell[0][0] == t:
        _t, r, c = rm_smell.popleft()
        smell[(r,c)].pop()

def get_answer(N, M, k, shark, shark_priority):
    smell = defaultdict(lambda: [-1])
    rm_smell = deque()

    t = 0
    while len(shark) > 1 and t <= 1000:
        # debug(shark, smell, rm_smell, t)
        make_smell(shark, smell, rm_smell, t, k)
        nw_shark = move(shark, smell, shark_priority, N)
        t += 1
        remove_smell(t, rm_smell, smell)
        shark = nw_shark
    if t > 1000:
        return -1
    return t

def debug(shark, smell, rm_smell, t):
    print(f"=========={t}==========")
    print(f"shark:")
    for k, v in shark.items():
        print(f"{k} : {v}")
    print(f"smell:")
    for k, v in smell.items():
        print(f"{k} : {v}")
    print(f"rm_smell:")
    for x in rm_smell:
        print(x)
    print()

N, M, k, shark, shark_priority = read_data()
print(get_answer(N, M, k, shark, shark_priority))

• 상어
  
  • dict[ (r, c) ] = (n, d)
  • 상어 위치 (r, c)
  • 상어 번호 n
  • 상어 방향 d
• 냄새
  • dict[ (r, c) ] = [-1, ...]
  • stack
    - 냄새가 만들어지면 append
    - 현재 냄새를 top(-1)으로 확인
• 냄세 제거
  • deque([ (t, r, c) ])
  • 제거될 시간 t
  • 제거할 위치 r, c
  • while (t == 현재 시간): pop()

 

다른 사람이 작성한 코드

None

• 강한 구현문제로 다른 코드를 참고하지 않음

 

기억해야할 것

• 자료구조 정리하기
  
  • 비교적 문제를 빨리 풀었고, 디버깅도 빨랐음
  • 위와 같이 사용할 자료구조들을 미리 정리
    - 처음 돌렸을 때 예제 실패
    - debug() 작성하여 상태 변화 확인
    - shark가 이동했을 때, value가 이상함을 감지 : (n, d)인데 위치가 바뀌어 있었음