[백준/19236] 청소년 상어

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

19236번: 청소년 상어

---

 전형적인 구현 문제입니다만, 조건이 상당히 많아서 실수없이 구현하기가 어려운 문제입니다. 평소에 구현 유형 문제를 많이 풀어보지 않으면 머리에 과부하가 걸리는 문제인 듯 합니다.. 소스코드는 다음과 같습니다.

 

from copy import deepcopy


dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
max_cnt = 0

array = [[None] * 4 for _ in range(4)]

for i in range(4):
    row = list(map(int, input().split()))
    for j in range(4):
        array[i][j] = [row[2 * j], row[2 * j + 1] - 1]

def find(array, idx):
    for i in range(4):
        for j in range(4):
            if array[i][j][0] == idx:
                return (i, j)
    return None

def fish_moving(shark, array):
    sx, sy = shark
    for i in range(1, 17):
        pos = find(array, i)
        if pos:
            x, y = pos
            if (x, y) == (sx, sy):
                continue
            direction = array[x][y][1]
            for _ in range(8):
                nx, ny = x + dx[direction], y + dy[direction]
                if 0 <= nx < 4 and 0 <= ny < 4:
                    if (nx, ny) != (sx, sy):
                        array[x][y][1] = direction
                        array[x][y], array[nx][ny] = array[nx][ny], array[x][y]
                        break

                direction = (direction + 1) % 8

def possible_position(array, shark):
    possible = []
    sx, sy = shark
    direction = array[sx][sy][1]
    
    for _ in range(4):
        sx += dx[direction]
        sy += dy[direction]
        if 0 <= sx < 4 and 0 <= sy < 4:
            if array[sx][sy][0] != -1:
                possible.append((sx, sy))
                
    return possible

def dfs(shark, array, cnt):
    global max_cnt
    
    x, y = shark
    array = deepcopy(array)

    cnt += array[x][y][0]
    array[x][y][0] = -1

    fish_moving(shark, array)
    possible = possible_position(array, shark)

    if not possible:
        max_cnt = max(cnt, max_cnt)
        return

    for a, b in possible:
        dfs((a, b), array, cnt)

dfs((0, 0), array, 0)
print(max_cnt)

 

 우선 전체 플로우를 dfs 함수를 통해 확인하고 각각의 함수의 기능을 확인해보는 편이 좋을 듯 합니다. 우선 입력은 (물고기 번호, 방향)의 튜플 형태로 이중 리스트에 저장합니다.

for i in range(4):
    row = list(map(int, input().split()))
    for j in range(4):
        array[i][j] = [row[2 * j], row[2 * j + 1] - 1]

 

 관건은 물고기의 움직임을 구현한 뒤, 매번 상어가 받을 수 있는 보상의 모든 경우의 수를 탐색하는 것입니다. 따라서 여기선 깊이 우선 탐색 방법을 사용했습니다. 너비 우선 탐색을 사용할 경우 '이동 가능한 경우의 수가 없다면 종료한다'는 기능을 구현하기가 까다로워지기 때문에 깊이 우선 탐색 방법을 택했습니다.

def dfs(shark, array, cnt):
    global max_cnt
    
    x, y = shark
    array = deepcopy(array)

    cnt += array[x][y][0]
    array[x][y][0] = -1

    fish_moving(shark, array)
    possible = possible_position(array, shark)

    if not possible:
        max_cnt = max(cnt, max_cnt)
        return

    for a, b in possible:
        dfs((a, b), array, cnt)

 

 입력으로는 상어의 위치, 맵 정보, 그리고 지금까지 상어가 먹은 물고기의 총합을 줍니다. 중요한 것은 탐색 과정에서 array가 계속해서 변할 것인데, 같은 시기에 분기해 나온 경우의 수에 대해서는 같은 맵을 입력으로 주어야 합니다. 그러나 array를 깊은 복사해놓지 않으면 전역 array 변수가 계속해서 업데이트되기 때문에 제대로 된 정답을 도출할 수 없습니다.

 이후에 현재 상어가 있는 위치에 대해서 물고기를 먹고, 해당 물고기를 총합에 더해주는 기능을 수행합니다. 다음엔 물고기가 움직이게 하고, 업데이트된 맵에 대해서 상어가 움직일 수 있는 모든 경우의 수를 구한 뒤, 경우의 수가 없다면 최대값을 업데이트하고 종료, 경우의 수가 있다면 재귀적으로 다음 경우의 수를 탐색합니다. 

 

 그럼 물고기가 움직이게 하는 함수부터 보겠습니다.

def fish_moving(shark, array):
    sx, sy = shark
    for i in range(1, 17):
        pos = find(array, i)
        if pos:
            x, y = pos
            if (x, y) == (sx, sy):
                continue
            direction = array[x][y][1]
            for _ in range(8):
                nx, ny = x + dx[direction], y + dy[direction]
                if 0 <= nx < 4 and 0 <= ny < 4:
                    if (nx, ny) != (sx, sy):
                        array[x][y][1] = direction
                        array[x][y], array[nx][ny] = array[nx][ny], array[x][y]
                        break

                direction = (direction + 1) % 8

 1번 물고기부터 16번 물고기까지 차례로 위치가 업데이트되므로 순서대로 처리하되, 상어가 있는 위치는 업데이트되서는 안됩니다. 물고기의 위치를 구하는 함수는 단순 이중반복문이므로 생략하겠습니다. 물고기의 위치를 구한 뒤, 8가지 방향에 대해서 순차적으로 고려하고, 만약 이동가능한 경우가 있다면 위치를 변경합니다.

 

 다음은 상어의 이동 가능한 경우의 수를 구하는 함수입니다.

def possible_position(array, shark):
    possible = []
    sx, sy = shark
    direction = array[sx][sy][1]
    
    for _ in range(4):
        sx += dx[direction]
        sy += dy[direction]
        if 0 <= sx < 4 and 0 <= sy < 4:
            if array[sx][sy][0] != -1:
                possible.append((sx, sy))
                
    return possible

 

단순히 상어의 방향을 구한 뒤, 맵을 넘어가지 않고 물고기가 있는 경우에 대해서 모두 리스트에 넣어 반환해줍니다. 

 이후 초기 상어의 위치 0, 0과 총합 0을 dfs함수의 인자로 주면, 전역 변수 max_cnt가 업데이트되어 결과를 도출할 수 있습니다.

---

 변수 이름을 막 지정하는 안 좋은 버릇이 있었습니다. 예를 들어 i, j라던가 x, y라던가.. i, j같은 경우는 컨텍스트 내에서만 쓰이기 때문에 영향이 없을지 몰라도 x, y를 남발하는 것은 생각보다 위험한 일인것 같았습니다. 함수 내 컨텍스트와 전역 컨텍스트에서 무분별하게 사용되어 나중에 오류가 발생하면 디버깅하기가 상당히 골치아팠습니다..

 웬만하면 변수명을 유니크하게 주는 습관을 들여야겠다고 느낀 문제였습니다..