19236번 - 청소년 상어

문제

 

19236번: 청소년 상어 (acmicpc.net)

19236번: 청소년 상어

풀이 1

문제에서 상어가 물고기를 먹는 경우 중 번호의 합이 최대가 되는 경우를 구해야 하므로, 백트래킹으로 접근해야겠다는 판단이 가능하다. 또한 조건에서 물고기 번호는 유일하므로, 물고기의 정보는 리스트에 담아 인덱스로 식별할 수 있겠다.

 

백트래킹으로 접근하게 될 것이므로 재귀함수 형태로 문제에서 주어진 상황을 구현해야 한다. 구현하는 것은 두 가지로, 물고기를 이동시키는 것과 상어가 이동하는 것이다. 이 때 주의해야할 점은, 재귀함수 호출 시 물고기의 이동과 상어의 이동 두 행동 모두 보드를 조작한다는 것이다. 따라서 상어의 이동 뿐 아니라 물고기의 이동도 재귀함수 호출 후 원래대로 되돌려 줘야하는데, 차라리 재귀함수를 호출할 때 새로운 리스트에 복사본을 넣어 넘겨주는 편이 편하다.

 

어떤 부분이 풀이에 필요한 정보들을 조작할 것인지 염두하고 문제를 설계할 필요를 느낄 수 있는 문제였다. 또한 재귀함수의 각 상태에서 사용하는 정보의 불변성을 지켜줄 필요가 있으며, 전역변수를 두고 하기보다는 이쪽을 더 우선시 해야겠다는 생각이 들었다.

 

# N, NW, W, SW, S, SE, E, NE
dRow = [-1,-1,0,1,1,1,0,-1]
dCol = [0,-1,-1,-1,0,1,1,1]

survived = [True]*17
loc = [[0,0] for _ in range(17)]
dir = [0] * 17
board = [[0]*4 for _ in range(4)]
for row in range(4):
    li = list(map(int,input().split()))
    for col in range(4):
        idx = col * 2
        board[row][col] = li[idx]
        loc[li[idx]][0],loc[li[idx]][1] = row,col
        dir[li[idx]] = li[idx + 1] - 1


def update_result(result,_board,_dir,_loc,_survived):
    global answer
    answer = max(answer,result)
    # 물고기 이동
    for fish in range(1,17):
        if _survived[fish]:
            row,col = _loc[fish]
            for j in range(8):
                nDir = (_dir[fish] + j) % 8
                nRow, nCol = row + dRow[nDir], col + dCol[nDir]
                if 0 <= nRow < 4 and 0 <= nCol < 4 and _board[nRow][nCol] != 0:
                    _dir[fish] = nDir
                    v = _board[nRow][nCol]
                    if v > 0:
                        _loc[v][0], _loc[v][1] = row, col
                    _loc[fish][0], _loc[fish][1] = nRow, nCol
                    _board[row][col], _board[nRow][nCol] = v, fish
                    break
    # 상어 이동
    row,col = _loc[0]
    d = _dir[0]
    nRow,nCol = row,col
    while 0 <= nRow+dRow[d] < 4 and 0 <= nCol+dCol[d] < 4:
        nRow += dRow[d]
        nCol += dCol[d]
        v = _board[nRow][nCol]
        if v > 0:
            _dir[0] = _dir[v]
            _loc[0][0],_loc[0][1] = nRow,nCol
            _survived[v] = False
            _board[row][col],_board[nRow][nCol] = -1,0
            update_result(result+v,[[*elem] for elem in _board],[*_dir],[[*elem] for elem in _loc],[*_survived])
            _board[row][col],_board[nRow][nCol] = 0,v
            _survived[v] = True
            _loc[0][0],_loc[0][1] = row,col
            _dir[0] = d


answer = 0
# 상어 세팅
prey = board[0][0]
dir[0] = dir[prey]
survived[prey] = False
board[0][0] = 0
update_result(prey,board,dir,loc,survived)

print(answer)

풀이 2

문제에서 보드는 물고기가 이동하면서 한번, 상어가 이동하면서 한번 총 두번 갱신된다. 상어가 이동하는 코드를 보면 여타 백트래킹 문제와 마찬가지로 상어가 일으킨 갱신을 다시 되돌리는데, 물고기가 이동한것에 대해서는 그렇지가 않다는 사실이 중요하다. 즉 전역변수로 선언된 보드를 직접 갱신한다면, 재귀호출된 함수에서 일어난 갱신이 함수가 종료되고 다시 원래 시점으로 돌아왔을 때 되돌려질 방법이 없게될 것이다. 이때문에 물고기의 이동에서 갱신되는 locs와 board는 재귀함수 호출 시 복사해서 param으로 넣어줘야한다. 정리하자면, 반복문에서 갱신되었던것을 재귀함수가 종료된 후에 다시 되돌리는것은 상관없지만, 반복문 바깥에서 갱신된 내용에 대해서도 반드시 고려를 해줘야한다. 사실 시간제한과 메모리만 허용된다면, 잘 안된다 싶으면 일단 참조하고 있는 보드나 그외 객체를 복사해서 param으로 넣어주는것도 방법이다.

위 풀이와 다르게 물고기의 위치를 바꿀 때 값이 아닌 참조 객체를 서로 바꿔주고 있는데, 그 뒤에 locs를 따로 건드리고 있지 않기 때문에 안전한 방법이다.

물고기가 인접 칸을 탐색할 때 dir = (dir-1+j)%8 + 1 로 작성해서 엄청나게 시간을 낭비했는데, 당연하게도 이렇게 하면 방향이 45도씩 틀어지는것이 아니라 45도 -> 90도 -> 135도 이런식으로 누적된다. 원판돌리기 문제에서도 x의 배수를 구할 때 x *= 2로 해서 누적되게 해버렸는데, 이런 사소한 실수를 조심할 필요가 있겠다.

# N/A,N,NW,W,SW,S,SE,E,NE
dRow = [0,-1,-1,0,1,1,1,0,-1]
dCol = [0,0,-1,-1,-1,0,1,1,1]

# -1:상어, 0:빈칸, 1~16:물고기
board = [[[] for col in range(4)] for row in range(4)]
dirs = [0]*17
for i in range(4):
    for j,v in enumerate(map(int,input().split())):
        board[i][j // 2].append(v)
locs = [[0, 0] for _ in range(17)]
for row in range(4):
    for col in range(4):
        f = board[row][col][0]
        locs[f][0], locs[f][1] = row, col
survived = [True]*17


def get_answer(_locs,_board,x,y,result):
    global answer
    # 물고기 이동
    for i in range(1,17):
        if not survived[i]:
            continue
        r,c = _locs[i]
        dir = _board[r][c][1]
        ndir = dir
        for j in range(8):
            ndir = (dir-1+j)%8+1
            nr,nc = r+dRow[ndir],c+dCol[ndir]
            if 0 <= nr < 4 and 0 <= nc < 4 and _board[nr][nc][0] >= 0:
                adj = _board[nr][nc][0]
                if adj > 0:
                    _locs[adj][0],_locs[adj][1] = r,c
                _locs[i][0],_locs[i][1] = nr,nc
                _board[r][c][1] = ndir
                _board[r][c], _board[nr][nc] = _board[nr][nc], _board[r][c]
                break
    # 상어 탐색
    d = _board[x][y][1]
    nx,ny = x,y
    while True:
        # 탐색
        nx += dRow[d]
        ny += dCol[d]
        if not (0 <= nx < 4 and 0 <= ny < 4):
            answer = max(answer, result)
            break
        target = _board[nx][ny][0]
        if target == 0:
            continue
        # 이동
        survived[target] = False
        _board[x][y][0] = 0
        _board[nx][ny][0] = -1
        get_answer([[*elem] for elem in _locs],[[[*elem] for elem in li] for li in _board],nx,ny,result+target)
        _board[nx][ny][0] = target
        _board[x][y][0] = -1
        survived[target] = True


answer = 0
# 상어 출현
target = board[0][0][0]
survived[target] = False
board[0][0][0] = -1
get_answer(locs,board,0,0,target)
print(answer)