👉문제 링크

느낀점

• 오랜만에 삼성입사 시험 기출 알고리즘을 풀었다.
• 시간도 3시간이 넘게 걸렸고, 풀이도 지저분하다.
• 시뮬레이션류로.. 어려운 문제가 아니었는데..
• 뭔가 씁쓸하다.

정답 코드 및 해설

direction = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]


def solution(_answer, _shark_dir, _shark_xy, _world, _tracker, count):
    global answer
    if count != 16 and answer != 136:
        dx, dy = direction[_shark_dir]
        shark_x_next_temp = _shark_xy[0] + dx
        shark_y_next_temp = _shark_xy[1] + dy
        if 0 <= shark_x_next_temp < 4 and 0 <= shark_y_next_temp < 4:
            for jump in range(3):
                shark_x_next_jump = shark_x_next_temp + dx * jump
                shark_y_next_jump = shark_y_next_temp + dy * jump
                if 0 <= shark_x_next_jump < 4 and 0 <= shark_y_next_jump < 4 and _world[shark_y_next_jump][
                    shark_x_next_jump]:
                    world_next = [[[] for __ in range(4)] for _ in range(4)]
                    for yy in range(4):
                        for xx in range(4):
                            world_next[yy][xx] = _world[yy][xx][:] if _world[yy][xx] else []
                    tracker_next = {}
                    for key, value in _tracker.items():
                        tracker_next[key] = value[:]
                    # 잡아먹힌 물고기 정보
                    eaten_fish, eaten_fish_dir = world_next[shark_y_next_jump][shark_x_next_jump]
                    eaten_fish_xy = [shark_x_next_jump, shark_y_next_jump]
                    world_next[shark_y_next_jump][shark_x_next_jump] = 0
                    del tracker_next[eaten_fish]
                    # 물고기 이동
                    for fish_num, fish_xy in tracker_next.items():
                        fish_x, fish_y = fish_xy
                        fish_dir = world_next[fish_y][fish_x][1]
                        for dir_jump in range(8):
                            fish_next_dir = (fish_dir + dir_jump) % 8
                            ddx, ddy = direction[fish_next_dir]
                            fish_next_x, fish_next_y = fish_x + ddx, fish_y + ddy
                            if 0 <= fish_next_x < 4 and 0 <= fish_next_y < 4:
                                if world_next[fish_next_y][fish_next_x]:
                                    # 물고기가 있다면 이동 후 자리교체
                                    new_fish_num, new_direction = world_next[fish_next_y][fish_next_x]
                                    new_fish_xy = tracker_next[new_fish_num]

                                    world_next[fish_next_y][fish_next_x] = [fish_num, fish_next_dir]
                                    world_next[fish_y][fish_x] = [new_fish_num, new_direction]

                                    tracker_next[fish_num] = new_fish_xy[:]
                                    tracker_next[new_fish_num] = fish_xy[:]
                                    break
                                elif world_next[fish_next_y][fish_next_x] != 0:
                                    # 빈 자리라면 이동 후 자리 교체
                                    world_next[fish_y][fish_x] = []
                                    world_next[fish_next_y][fish_next_x] = [fish_num, fish_next_dir]
                                    tracker_next[fish_num] = [fish_next_x, fish_next_y]
                                    break
                                else:
                                    # 상어라면 방향 전환
                                    pass
                            else:
                                # 막다른 곳이라면 방향 전환
                                pass
                        else:
                            print("물고기가 이동을 못함")
                            raise Exception("물고기가 이동을 못함")
                    # 다음 재귀 호출
                    world_next[shark_y_next_jump][shark_x_next_jump] = []
                    solution(_answer + eaten_fish, eaten_fish_dir, eaten_fish_xy, world_next, tracker_next,
                             count + 1)
            else:
                if answer < _answer:
                    answer = _answer

        else:
            # 상어가 이동 못해서 종료
            if answer < _answer:
                answer = _answer
    else:
        if answer < _answer:
            answer = _answer


# 초기 세팅
answer = 0
world = [[[] for __ in range(4)] for _ in range(4)]
tracker = {i: [-1, -1] for i in range(1, 17)}
for y in range(4):
    inputs = list(map(int, input().split()))
    for x in range(4):
        world[y][x] = [inputs[x * 2], inputs[x * 2 + 1] - 1]
        tracker[inputs[x * 2]] = [x, y]

# 첫번째 포식
answer, shark_dir = world[0][0]
shark_xy = [0, 0]
del tracker[answer]
world[0][0] = 0

# 물고기 이동
for fish_num, fish_xy in tracker.items():
    fish_x, fish_y = fish_xy
    fish_dir = world[fish_y][fish_x][1]

    for dir_jump in range(8):
        fish_next_dir = (fish_dir + dir_jump) % 8
        ddx, ddy = direction[fish_next_dir]
        fish_next_x, fish_next_y = fish_x + ddx, fish_y + ddy
        if 0 <= fish_next_x < 4 and 0 <= fish_next_y < 4:
            if world[fish_next_y][fish_next_x]:
                # 물고기가 있다면 이동 후 자리교체
                new_fish_num, new_direction = world[fish_next_y][fish_next_x]

                new_fish_xy = tracker[new_fish_num]

                world[fish_next_y][fish_next_x] = [fish_num, fish_next_dir]
                world[fish_y][fish_x] = [new_fish_num, new_direction]

                tracker[fish_num] = new_fish_xy[:]
                tracker[new_fish_num] = fish_xy[:]
                break

            elif world[fish_next_y][fish_next_x] != 0:
                # 빈 자리라면 이동 후 자리 교체
                world[fish_y][fish_x] = []
                world[fish_next_y][fish_next_x] = [fish_num, fish_next_dir]
                tracker[fish_num] = [fish_next_x, fish_next_y]
                break
            else:
                # 상어라면 방향 전환
                pass
        else:
            # 막다른 곳이라면 방향 전환
            pass
    else:
        print("물고기가 이동을 못함")
        raise Exception("물고기가 이동을 못함")
solution(answer, shark_dir, shark_xy, world, tracker, 0)
print(answer)