[BOJ] 19236번 - 청소년 상어(삼성 SW 기출)

동아리 활동이 끝나고 다시 알고리즘을 하면서 카카오 쪽 코딩테스트를 두개 봤다.

하나는 JS, 하나는 python으로 언어를 선택했지만,, 결과는 좋지 않았다. ㅠ.ㅠ

그래서 시간 날 때마다 알고리즘 문제를 집중해서 풀고 블로그를 쓰면서 기술들을 잘 정리 해야겠다고 생각했다.

 

내가 제일 약하다고 느끼는 부분 중 하나가 dfs부분이다. 사실 기본 그래프 문제에서 탐색하는 것은 어렵다고 느껴지진 않았는데

백트래킹 쪽 탐색 문제에서 이해가 잘 되지 않았던 부분들이 많았다.

삼성 역량 기출 문제중에서 구현, 백트래킹 문제가 상당히 많았고, 문제 풀 때마다 빡셌던것 같다. (나의 역량이 부족한 걸로!)

 

www.acmicpc.net/problem/19236

19236번: 청소년 상어

 

시간을 되게 많이 썼고, 디버깅 하는 데도 재귀로 돌리는 것이라 매우 힘들었다. 심지어 테케가 다 맞는 와중에도

4퍼센트에서 자꾸끊기는 바람에... 엄청 오래걸렸던 것 같다.

 

1. 물고기들의 순회 함수 (총 9가지 방향이 있으며 맞는 방향까지 45도씩 돌아가며 확인해야한다)

- 물고기들의 위치 바꾸기, 상어 피하기, 빈 공간은 그냥 이동 시키기  이 정도만 참고하면 될 것 같다

 

2. 상어가 먹이를 먹는 dfs( ) 함수

- 기존배열 복사 해놓기 재귀 돌고 나온 배열에 복사 해놨던 배열 deepcopy로 복사해주기

( 그냥 box = list 이런식으로 하게되어버리면 for문을 돌면서 원본 배열이 자꾸 바뀌게 된다. )

 

이렇게 보면 간단한 문제 같지만 2번에서 배열복사를 deepcopy로 하지 않는 바람에 배로 시간이 걸렸던것 같다.

아마 이런 분들 중 테케는 다 맞지만 틀리는 경우도 있으니 참고 하실분은 참고를...

from sys import stdin
from copy import deepcopy

box = [[] for i in range(4)]
fish = [[] for i in range(16)]

for i in range(4):
    a = list(map(int, stdin.readline().split()))
    for j in range(0, 8, 2):
        box[i].append([a[j]-1, a[j+1]-1])
        fish[a[j]-1] = [i, j//2]

# 상어 첫번째 식사
shark_d = box[0][0][1]
fish[box[0][0][0]] = []
answer = box[0][0][0]+1
box[0][0] = [-1, shark_d]
nr, nc = [-1, -1, 0, 1, 1, 1, 0, -1], [0, -1, -1, -1, 0, 1, 1, 1]


def fish_move():
    for i in range(16):  # 물고기 개수만큼 순회
        if fish[i] == []:
            continue
        # 회전 물고기
        f_r, f_c = fish[i]
        f_d = box[f_r][f_c][1]
        for j in range(9):
            direction = (f_d + j) % 8
            dr, dc = f_r + nr[direction], f_c + nc[direction]
            if 0 <= dr < 4 and 0 <= dc < 4 and not box[dr][dc][0] == -1:
                box[f_r][f_c][1] = direction
                if box[dr][dc][0] == -2:
                    fish[i] = [dr, dc]
                else:
                    fish[i], fish[box[dr][dc][0]] = [dr, dc], fish[i]
                box[f_r][f_c], box[dr][dc] = box[dr][dc], box[f_r][f_c]
                break


def shark_eat(s_r, s_c, s_d, ans, depth):
    global answer, box, fish
    fish_move()
    temp_b, temp_f = deepcopy(box), deepcopy(fish)
    for i in range(1, 4):
        dr, dc = s_r+nr[s_d]*i, s_c+nc[s_d]*i
        if 0 <= dr < 4 and 0 <= dc < 4 and box[dr][dc][0] >= 0:
            box[s_r][s_c][0] = -2  # 상어위치 빈 공간
            eat = box[dr][dc][0]  # 먹이
            temp1, temp2 = fish[box[dr][dc][0]], box[dr][dc]
            box[dr][dc] = [-1, box[dr][dc][1]]  # 다음 상어 대입
            fish[eat] = []
            shark_eat(dr, dc, box[dr][dc][1], ans+eat+1, depth+1)
            box, fish = deepcopy(temp_b), deepcopy(temp_f)

    if answer < ans:
        answer = ans
        return


shark_eat(0, 0, shark_d, answer, 0)
print(answer)