백준 #19236 - [G2] 청소년 상어 : 구현, back tracking

(python3)

아이디어

까다로운 상어 시리즈의 청소년 버전입니다.

이 문제는 시뮬레이션의 조건이 많기 떄문에 코딩 과정에서 스텝이 꼬이지 않도록 기능을 잘 분리해서 접근해주는게 좋습니다.

 

저는 위치가 2차원 행렬로 표현되는 경우 x,y 보다 r,c 를 사용하는게 명료해서 더 선호합니다. 방향 역시 1~8 의 숫자로 문제에서 주어졌지만 배열로 접근할때의 편의성을 위해 0~7 로 변환하여 사용했습니다. 이런 디테일한 변수 설정들이 헷갈리지 않도록 메모하거나 체계를 잡아두는게 좋은 것 같습니다.

 

상어가 이동할 수 있는 모든 경우의 수를 탐색해야하고, 이전의 선택 뒤에 다음 선택지가 가지치듯 갈라지는게 반복되기 때문에 백트레킹을 사용하는게 좋습니다. 재귀를 활용해서 단순하게 구현이 가능합니다.

 

백트래킹은 트리를 떠올렸을 때 루트에서 리프로 방향으로 연산하면서 모든 리프의 값을 구한 후, 리프에서 루트로 올라오는 과정에서 여러 자식들이 모이는 부모 노드마다 각 자식의 최대값을 선택하는 방식을 취해서 최종적으로 모든 리프의 최대값이 루트 노드로 올라오게 되는 형태의 알고리즘 이라고 설명할 수 있겠습니다.

 

백트레킹 함수는 현재 스테이지에서 가능한 경우의 수들 에 대해 각각 백트래킹을 수행하고, 각각의 케이스 이후에 벌어지는 모든 경우의 수에서 최대값을 반환하는 함수로 구현할 수 있습니다.

def backtrack(R) :
    자식노드들_결과 = []
    for 자식노드 in "R 다음에 가능한 모든 경우의 수" : 
    	자식노드들_결과 배열에 backtrack(자식노드) 결과 추가
    return max(자식노드들_결과)

dfs 나 백트래킹의 경우 구현 과정에서  항상 주의해야 할 것은 하나의 스테이지에서 변경되지 않고, 다음 스테이지로만 넘겨줘야 하는 변경 사항들에 대해서는 깊은 복사로 처리해야한다는 부분 입니다.

 

구현 디테일

모든 정보를 2차원 배열로 관리하게 되면 가장 작은 번호의 물고기부터 이동해야할때 맵 전체를 매번 둘러봐야하기 때문에 좀 더 효율적인 탐색을 위해  물고기 번호를 키로 가지는 dict 로 물고기 정보를 관리하기로 했습니다. 맵상에서 물고기의 위치가 필요한 경우 참고하기 위해 dict 를 보고 map 을 그리는 함수를 작성하여 추가로 사용했습니다.

import copy
def solution(input) : 
    """
    공간 칸 : (r,c)
    물고기 번호 = 1~16
    방향 8개 : D = []
    물고기 이동. 물고기 번호 오름차순, 이동가능 = 빈칸/다른 물고기가 있는 칸, 이동불가 = 상어, 경계밖
    이동 가능할때까지 반시계 회전, 이동 불가시 이동 x
    다른 물고기가 있으면 자리를 바꿈
    상어이동 (그 방향의 모든 칸으로 이동 가능)
    가능한 모든 경우의 수 계산
    """
    
    # 물고기 정보 받기
    fdict = {} # (방향, 위치)

    def make_pair(li) :
        pairs = []
        for i in range(0,len(li),2) :
            pairs.append((li[i], li[i+1]))
        return pairs
    
    for r in range(4) :
        temp = list(map(int, input().split()))
        for c,p in enumerate(make_pair(temp)) :
            fdict[p[0]] = (p[1]-1, (r,c))

    # 물고기 dict 로 물고기 맵 만들기
    def make_fmap(fdict) :
        fmap = [[0 for _ in range(4)] for _ in range(4)]
        for f in fdict :
            r,c = fdict[f][1]
            fmap[r][c] = f
        return fmap
    
    # 물고기 이동
    def fish_move(fdict) :
        fmap = make_fmap(fdict)
        fish_sorted = list(fdict.keys())
        fish_sorted.sort() # 번호가 작은 순서로 움직인다.
        for f in fish_sorted : # 상어를 제외한 모든 물고기에 대해
            if f == -1 : continue
            (d,(r,c)) = fdict[f]
            for i in range(8) : # 8뱡에 대해서
                nd = (d+i) % 8
                dr, dc = DIR[nd]
                nr, nc = r+dr, c+dc
                # 이동 가능 체크
                if nr >=0 and nr < 4 and nc >= 0 and nc < 4 :# 벽 안에 있나요?
                    if fmap[nr][nc] != -1 : # 상어와 부딪히지 않나요?
                        if fmap[nr][nc] == 0 : # 이동하려는 곳이 빈칸이면 그냥 이동
                            fdict[f] = (nd, (nr,nc))
                        else : # 물고기가 있다면 위치 바꾸기
                            nf = fmap[nr][nc]
                            fdict[nf] = (fdict[nf][0], (r,c))
                            fdict[f] = (nd,(nr,nc))
                        fmap[r][c], fmap[nr][nc] = fmap[nr][nc], fmap[r][c] # 맵 갱신
                        break
        return fdict
    
    # 백트래킹
    def back_track(FDICT, point) :
        max_point = point
        fish_move(FDICT)
        # 상어 이동 경우의 수
        FMAP = make_fmap(FDICT)
        (d, (r,c)) = FDICT[-1]
        dr, dc = DIR[d]
        for i in range(1,5) :
            nr, nc = r + i*dr, c + i*dc
            if nr >= 0 and nr < 4 and nc >= 0 and nc < 4 : # 상어가 벽 안에 있다면
                if FMAP[nr][nc] != 0 : # 먹을 물고기가 있다면
                    n_fdict = copy.deepcopy(FDICT)
                    nf = FMAP[nr][nc]
                    npoint = point + nf
                    n_fdict[-1] = copy.deepcopy(n_fdict[nf])
                    del n_fdict[nf]
                    max_point = max(max_point,back_track(n_fdict, npoint))
            else : break
        return max_point
    
    DIR = [(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1)]
    
    # 상어 입장
    fmap = make_fmap(fdict)
    ff = fmap[0][0]
    fdir = fdict[ff][0]
    fdict[-1] = (fdir, (0,0))
    del fdict[ff]
    # 백트래킹 시작
    max_point = back_track(fdict, ff)

    print(max_point)

solution(input)