코딩테스트 스터디 - 백준 19236번: 청소년 상어 (python)

문제

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

19236번: 청소년 상어

요약

4*4 판에 1~16으로 번호가 매겨진 물고기들이 있고, 각 물고기는 8방향 중 1가지 방향을 갖는다.

상어는 0,0에서 시작하며 아래를 반복한다.

1. 상어 위치에 있는 물고기를 잡아먹는다.

2. 1번 물고기부터 순서대로 모든 물고기들이 자신의 방향대로 움직인다.

 2-1. 상어나 벽에 의해 막혀있을 경우 반시계 방향으로 45도 회전한다.

 2-2. 다른 물고기가 있는 방향으로 움직일 땐 그 물고기와 자리를 바꾼다.

3. 상어는 방금 잡아먹은 물고기가 향했던 방향으로 원하는 칸 수만큼 움직일 수 있다. 물고기가 있는 칸으로만 이동 가능하며, 여러칸 이동하면 지나친 물고기는 먹지 않고 건너뛴다. 만약 지정된 방향에 물고기가 있는 칸이 없으면 종료한다.

 

상어가 먹은 물고기 번호의 총합의 최대값을 구하는 문제다.

의식의 흐름

우선 문제를 그대로 구현해야하고, 구현상에서 까다로운 점은 딱히 없어보인다.

상어가 선택 할 수 있는게 여러가지고 최대값을 구하는 문제기 때문에 Best First Search를 이용하려했으나,

F = G + H 에서

G = 현재까지의 점수

H = 현재 판 위에 남은 물고기의 합 = 1~16까지의 합 - 먹은 물고기(=현재까지 점수)

로, G + H가 항상 1~16까지의 합으로 같다.

 

따라서 이 문제는 DFS, BFS등을 이용해 전부 다 해봐야할 것 같다.

DFS를 이용해 Backtracking을 하는게 효율적일것 같다고 생각했지만,

개인적으로 나중에 Best First Search를 잘 쓰기위해 BFS 구현을 연습하기위해 BFS로 했다.

구현

자료구조

4*4 list of list에 물고기들(id와 dir)을 저장했지만,

1~16 순서대로 물고기의 위치를 update 해줘야하는데 매번 탐색할 수 없기 때문에

번호별 물고기의 위치를 저장할 dictionary를 하나 따로 만들었다.

Queue에 저장할 State는 상어가 이동을 마치고 물고기를 먹기 직전 상태로 정했다.

State = 새로운 상어의 위치, 현재까지 점수, 현재 4*4 바다의 상태, 번호별 물고기 위치

알고리즘

BFS 방식을 사용해 모든 경우를 탐색했다.

 

State가 물고기를 먹기 직전이므로,

Queue에서 pop을 한 후

 1. 물고기 먹기

 2. 물고기들 각자 이동하기 (dir2delta 함수 만들어 사용, 현재 방향에 0~7을 더해보며 이동 되는 방향을 찾음)

 3. 상어의 이동 가능한 모든 위치에 대해 새로운 State Enqueue

의 과정을 반복해준다.

최대 점수가 1~16의 합이 되거나 큐가 비면 탐색을 마치고 최대 점수를 출력한다.

코드

복잡한 알고리즘은 아니니 사실상 구현만 잘하면 될 문제인 것 같다.

코딩테스트 문제를 풀 때는 항상 어디까지 철학을 지켜서 코딩해야되는지가 고민인 것 같다.

처음에는 물고기를 그냥 (id, dir)의 tuple로 관리하다가 [0] 과 [1]이 너무 많이 나와 헷갈려서 결국 Fish 클래스를 만들었다.

사실 위치 정보도 튜플이 아니라 클래스로 빼고싶었다.

항상 드는 생각인데 BFS 기반 문제들은 디버깅하기 너무 힘든 것 같다.

list of list of object와 dictionary를 사용하다보니 디버깅하는데 더 오래걸렸다.

문제를 계속 풀다보면 깔끔한 코드를 쓰는데 요령이 생기지 않을까..싶다.

 

'''
    문제 출처: https://www.acmicpc.net/problem/19236
'''

import sys
import copy

input = [list(map(int, sys.stdin.readline().split(' '))) for i in range(4)]

N = 4
sea = []
fish_poses = {}

class Fish:
    def __init__(self, id, dir):
        self.id = id
        self.dir = dir
    def __repr__(self):
        return f"{self.id }/{self.dir}"


def is_in_bound(pos):
    return pos[0] >= 0 and pos[1] >= 0 and pos[0] < N and pos[1] < N
    
def dir2delta(dir):
    if dir == 1 : return (-1, 0)
    elif dir == 2 : return (-1, -1)
    elif dir == 3 : return (0, -1)
    elif dir == 4 : return (1, -1)
    elif dir == 5 : return (1, 0)
    elif dir == 6 : return (1, 1)
    elif dir == 7 : return (0, 1)
    elif dir == 8 : return (-1, 1)
    
for r in range(N):
    row = []
    for c in range(N):
        new_fish = Fish(input[r][2*c], input[r][2*c+1])
        fish_poses[new_fish.id] = (r,c)
        row.append(new_fish)
    sea.append(row)

queue = []
#sharkpos,score,sea,fishposes (물고기 먹기 직전 상태)
queue.append(((0,0), 0, sea, fish_poses))
max_score = 0


while len(queue) > 0:
    shark_pos, score, sea, fish_poses = queue.pop(0)
    #물고기 먹음
    score += sea[shark_pos[0]][shark_pos[1]].id
    max_score = max(score, max_score)
    if max_score == sum(range(1,16)):
        break
    fish_poses.pop(sea[shark_pos[0]][shark_pos[1]].id)
    sea[shark_pos[0]][shark_pos[1]].id = 0
    shark_dir = sea[shark_pos[0]][shark_pos[1]].dir
    
    #물고기 이동
    for i in range(1, N*N+1):
        if not (i in fish_poses.keys()):
            continue
        fish_pos = fish_poses[i]
        for d in range(7):
            new_dir = (sea[fish_pos[0]][fish_pos[1]].dir + d - 1) % 8 + 1
            delta = dir2delta(new_dir)
            next_pos = (fish_pos[0] + delta[0], fish_pos[1] + delta[1])
            if (not is_in_bound(next_pos)) or next_pos == shark_pos:
                continue
            sea[fish_pos[0]][fish_pos[1]].dir = new_dir
            #물고기 교체
            if sea[next_pos[0]][next_pos[1]].id > 0:
                fish_poses[sea[next_pos[0]][next_pos[1]].id] = fish_pos
            fish_poses[i] = next_pos
            temp = sea[next_pos[0]][next_pos[1]]
            sea[next_pos[0]][next_pos[1]] = sea[fish_pos[0]][fish_pos[1]]
            sea[fish_pos[0]][fish_pos[1]] = temp  
            break
    #상어의 다음위치 결정
    shark_delta = dir2delta(shark_dir)
    while True:
        shark_pos = (shark_pos[0] + shark_delta[0], shark_pos[1] + shark_delta[1])
        if is_in_bound(shark_pos):
            if sea[shark_pos[0]][shark_pos[1]].id > 0:
                #sharkpos,score,sea,fishposes (물고기 먹기 직전 상태)
                queue.append((shark_pos, score, copy.deepcopy(sea), dict(fish_poses)))
        else:
            break
        
print(max_score)