[BOJ] 청소년 상어

청소년 상어

처음에 HashMap을 사용해서 Table형식으로 접근하려고 했는데, 머릿속에서 너무 매칭이 안 되서 헷갈리드라구요.
제가 사용하려 했던건 물고기의 번호 당 위치를 나타내는 딕셔너리 하나, 방향을 나타내는 딕셔너리 하나 그리고 방향 배열 하나 물고기 배열 하나 이렇게 4개를 활용하려고 했습니다.

근데 문제가 뭐냐면, BackTracking으로 dfs를 돌릴려고 하니, 재귀를 빠져나오고 난 뒤에 다시 돌려 놓을 방법을 생각을 못했습니다. 좀... 꼬였습니다. 그래서 다른 풀이를 좀 참고했습니다. 제가 참고한 풀이는 이곳을 실리콘벨리로 68번째 글에서 보았습니다.

우선 문제의 입력값이 그리 크지가 않기 때문에 완전 탐색으로 문제를 풀어야 합니다.

import copy

board = [[] for _ in range(4)]

# 방향 선정
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

# 데이터 받기
for i in range(4):
    data = list(map(int, input().split()))
    fish = []
    for j in range(4):
        # 물고기 번호, 방향
        fish.append([data[2*j], data[2*j+1]-1])
    board[i] = fish

# 답을 내는 것임
max_score = 0

# back_tracking 알고리즘
def dfs(sx, sy, score, board):
    global max_score
    score += board[sx][sy][0]
    max_score = max(max_score, score)
    board[sx][sy][0] = 0

    # 물고기 위치 찾기
    for f in range(1, 17):
        fx, fy = -1, -1
        for x in range(4):
            for y in range(4):
                if board[x][y][0] == f:
                    fx, fy = x, y
                    break
                # 물고기 찾으면 break 
        # 물고기 못찾았으면, 넘기셈
        if fx == -1 and fy == -1:
            continue
        # 물고기 방향 할당
        fd = board[fx][fy][1]

        # 물고기 모두 방향대로 돌리기
        for i in range(8):
            nd = (fd + i) % 8
            nx, ny = fx + dx[nd], fy + dy[nd]
            # 안전하지도 않고 처음과 같다면, continue
            if not (0 <= nx < 4 and 0 <= ny < 4) or (nx == sx and ny == sy):
                continue
            board[fx][fy][1] = nd
            # 물고기 자리 바꿔줌
            board[fx][fy], board[nx][ny] = board[nx][ny], board[fx][fy]
            break

    # 샤크 방향 할당
    sd = board[sx][sy][1]
    # 샤크 먹이 먹자~!
    for i in range(1, 5):
        nx, ny = sx + dx[sd]*i, sy + dy[sd]*i
        # 안전하고 물고기 있으면, 거기로 dfs 들어가면 됨.
        if (0 <= nx < 4 and 0 <= ny < 4) and board[nx][ny][0] > 0:
            dfs(nx, ny, score, copy.deepcopy(board))

dfs(0, 0, 0, board)
print(max_score)

끝!

참고로 이 문제 약간 다시 풀어보고 싶은 생각이 큰데 추후에 해당 문제로 포스팅 하겠습니다.