[백준][구현] 청소년 상어

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

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

19236번: 청소년 상어

 

내가 작성한 코드

from collections import defaultdict, deque

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

def eat(fish, fish_pos, r, c):
    score, f_d = fish[(r, c)]
    fish[(r, c)] = ()
    fish_pos[score] = ()
    return (r, c, f_d), score

def read_data():
    fish = defaultdict(tuple)
    fish_pos = defaultdict(tuple)
    for r in range(4):
        c = 0
        crnt = list(map(int, input().rstrip().split()))
        for i in range(0, 8, 2):
            n, d = crnt[i], crnt[i+1]-1
            fish[(r, c)] = (n, d)
            fish_pos[n] = (r, c)
            c += 1

    shark, score = eat(fish, fish_pos, 0, 0)
    return fish, shark, score, fish_pos

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

def move_fish(shark, fish, fish_pos):
    def move(n, r, c, d, shark):
        i, j, _d = shark
        nw_r, nw_c = r+dir[d][0], c+dir[d][1]

        if in_range(nw_r, nw_c) and not (nw_r == i and nw_c == j):
            if fish[(nw_r, nw_c)]:
                nw_n, nw_d = fish[(nw_r, nw_c)]
                fish[(r, c)], fish[(nw_r, nw_c)] = fish[(nw_r, nw_c)], (n, d)
                fish_pos[n], fish_pos[nw_n] = fish_pos[nw_n], fish_pos[n]
            else:
                fish[(r, c)], fish[(nw_r, nw_c)] = fish[(nw_r, nw_c)], (n, d)
                fish_pos[n] = (nw_r, nw_c)
            return True
        return False

    for n in range(1, 16+1):
        if not fish_pos[n]:
            continue
        r, c = fish_pos[n]
        _n, d = fish[(r, c)]

        for k in range(8):
            if move(n, r, c, (d+k)%8, shark):
                break

def get_answer(fish, shark, score, fish_pos):
    mx = -float('inf')
    q = deque([(fish, shark, score, fish_pos)])
    while q:
        _fish, _shark, _score, _fish_pos = q.popleft()
        mx = max(mx, _score)

        move_fish(_shark, _fish, _fish_pos)

        i, j, d = _shark
        nw_i, nw_j = i+dir[d][0], j+dir[d][1]
        while in_range(nw_i, nw_j):
            if _fish[(nw_i, nw_j)]:
                nw_fish, nw_fish_pos = _fish.copy(), _fish_pos.copy()
                nw_shark, nw_score = eat(nw_fish, nw_fish_pos, nw_i, nw_j)
                q.append((nw_fish, nw_shark, _score+nw_score, nw_fish_pos))

            nw_i, nw_j = nw_i + dir[d][0], nw_j + dir[d][1]

    return mx


fish, shark, score, fish_pos = read_data()
print(get_answer(fish, shark, score, fish_pos))

• BFS
  • 상어가 움직일 수 있는 모든 경우의 수
  • [주의] 상어가 이동 가능한 모든 범위를 탐색
    - 물고기가 없으면 다음 범위 탐색
    - 물고기가 있으면 queue에 push
• 물고기 정보
  • dict[위치] = (번호, 방향)
  • dict[번호] = (위치)

 

다른 사람이 작성한 코드

None

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

 

기억해야할 것

• defaultdict의 복사
  • defaultdict(list)는 value들이 shallow copy
  • defaultdict(tuple)은 value들도 deep copy