[이것이 파이썬 코딩테스트다 - 구현] 청소년 상어

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

19236번: 청소년 상어

 

import copy
# 입력받을 배열 초기화
graph = [[None]*4 for _ in range(4)]
for i in range(4):
    data = list(map(int, input().split()))
    # 데이터 각각 집어넣기
    for j in range(4):
        # 중요: 여기서 -1 해주는 이유? dx, dy 값 8개만 쓸 것이라서
        graph[i][j] = [data[j*2],data[j*2+1]-1]
# print(graph)
# 방향 정의하는 배열
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

# 반시계 방향으로 이동하는 함수
def turn_left(direction):
    return (direction+1) % 8

# 물고기 인덱스 찾는 함수
def find_fish(array,index):
    for i in range(4):
        for j in range(4):
            # breakpoint()
            if array[i][j][0] == index:
                return (i,j)
    return None

# 물고기 움직임 -> 반시계 방향으로 이동하는 함수, 물고기 인덱스 찾는 함수
# 여기서는 array 받는 이유 -> dfs로 여러 array가 복사될 것이기 때문임...
def fish_movement(array,shark_x,shark_y):
    for idx in range(1,17):
        target = find_fish(array,idx)
        if target != None:
            # 물고기 swap 여부 결정
            x,y = target
            direction = array[x][y][1]
            for i in range(8):
                nx = x+dx[direction]
                ny = y+dy[direction]
                if nx>=0 and nx<4 and ny>=0 and ny<4:
                    if shark_x != nx or shark_y != ny:
                        # 이렇게 쉽게 바꿀 수 있는 방법이 !!
                        array[x][y][1] = direction # 이거 해주는 이유: direction이 처음과 달라지는 경우 생기기 때문임 !!
                        array[nx][ny], array[x][y] = array[x][y], array[nx][ny]
                        break

                # 방향 전환 갈기기
                direction = turn_left(direction)
                
# 상어가 먹을 수 있는 모든 위치 반환
def shark_possible(array,shark_x,shark_y):
    position =[]
    nx = shark_x
    ny = shark_y
    _, s_direction = array[nx][ny]
    for i in range(4):
        # 후보 x,y값 구함
        nx = nx + dx[s_direction]
        ny = ny + dy[s_direction]
        if nx>=0 and nx<4 and ny>=0 and ny<4:
            if array[nx][ny][0] != -1:
                position.append((nx,ny))

    return position
# 결과값
result = 0

# 상어 움직임 -> 물고기 움직임
def dfs(array,shark_x,shark_y,total):
    # result 글로벌 변수로 받아서 여기 안에서도 통신 가능하도록
    global result

    # array 복사
    array = copy.deepcopy(array)

    # 상어 먹기 시작
    # 쳐먹기 -> 해당 위치 인덱스 먹기
    total += array[shark_x][shark_y][0]
    array[shark_x][shark_y][0] = -1

    # 물고기 움직이기
    fish_movement(array,shark_x,shark_y)
    # 상어 후보 받기
    position = shark_possible(array,shark_x,shark_y)
    if len(position) == 0:
        result = max(total,result)
        return
    for next_x,next_y in position:
        dfs(array,next_x,next_y,total)

dfs(graph,0,0,0)

print(result)

 

 

1. 못 푼 이유

- '최대'를 그리디로 생각하고, 상어가 먹을 수 있는 먹이 중에 가장 좋은 녀석이면 된다고 생각함 -> 처음 설계할 때 이런 부분 주의할 것 !!!

- 문제를 어렵게 생각함 : 4*4행렬에서 인덱스 찾는 게 어렵지 않은데, 괜히 이거 저장해서 풀겠다고 하다가 코드 꼬임 (물고기 찾는 거 짜는 데만 30분 넘게 걸린 듯)

- 구현 문제는 당연하게도, 세부 모듈부터 짜는 것이 안된다 !! (답지 보고 베끼는 게 아니기 때문에...) 따라서 먼저 크게 돌아가는 구현코드부터 작성해서, input, output이 뭐가될지 큰 모듈들로부터 짜기 시작해서, 동작이 여러번 나올 것 같은 함수들을 짜는 방식으로 코드를 짜야 한다.

- 이 문제는 완전 탐색 알고리즘이므로 나동빈씨는 그래프 별로 중간중간 나올 수 있는 경우의 수를 저장할 수 있도록 dfs를 썼다. (근데 이렇게 중간 값을 저장하는 거면 DP라고 생각할 수도 있는 것인가??) 좋은 생각인 것 같은게, 재귀로 짜서 maximum  값을 저장할 수 있도록 하는 방식이며, 중간에 나올 수 있는 여러 고려 사항을 저장할 수 있기 때문이다 !!

 

2. 잘한 것.

- 오늘은 입력 받기 빠르게 넘겼다.. good! 

- 그리고 각 원소를 리스트로 저장하고, 또 상어랑 물고기들 움직이는 알고리즘도 잘 구현했음 !!!

- 다만 실행한 모든 output 저장하는 거 고려할 수 있도록 함수로 짜는 연습을 해야할 것 같고, 때문에 여기서 나온, copy 라이브러리의 deepcopy 메소드와, 함수 내로 변수 저장하는 global 변수 선언법을 배울 수 있었다.

- 또, 이런 문제는 굳이 인덱스를 저장하기 위한 요소를 따로 둘 필요가 없다 !! 4*4이기 때문이다 !! -> 이러한 판단들도 메모해두고, 시험 직전에 다시 한번 풀어봐야겠다 !! (전날 !!!)