청소년 상어 [삼성 기출]

1.접근 방법

- 항상 최적화와 효율적 접근이 중요하다는 사실을 기억하자

-> 최적화와 효율적 접근이 성패를 가른다 

 

- 자료구조는 적게 쓸 수록 좋다

-> 좌표는 따로 배열에 저장하지 않고, Map에서 가져다 쓰면 된다.

-> 그리고 가져다 쓸 때, 그 좌표를 반환시키면 된다. 

 

- 기본적으로 DFS로 접근하는 문제이다.

-> 그 점을 잘 기억하자

 

- beforeBoard를 copy해놓는다는 아이디어가 중요하다

-> copy해 놓아야 나중에 복원할 수 있다

-> 방문한 곳의 숫자는 -1로 처리한다 

 

- 위치를 단순히 교환하는 것은 파이썬 문법의 장점이다

-> moveFish에서 상어의 위치일 때는 이동이 불가능하다는 점을 고려해야 한다. 

 

- shark의 Move도 하나의 for문에서 처리할 수 있고, 거기서 arr을 만들어서 바로 배열을 리턴할 수 있다

-> 여기서 board[sx][sy][0] != -1을 고려하는 것이 중요하다 

 

- 상어가 이동할 칸이 없다

-> 즉, len(arr) == 0인 경우에, 이전에 beforeBoard를 다시 붙여줘야 한다는 점이 중요하다 

 

- 처음 방향 값을 넣을 때부터 -1을 한 값을 넣어줄 수 있다 

 

2. 처음 코드 

- 
3. 수정된 코드

import copy 

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

maxSum = 0

board = [] 

for i in range(4):
    row = list(map(int, input().split()))
    inputRow = [] 
    
    for j in range(4):
        inputRow.append([row[2*j], row[2*j+1]-1])
        
    board.append(inputRow)



    
        


def findFish(board, num):
    
    for i in range(4):
        for j in range(4):
            if board[i][j][0] == num:
                return (i, j)
                
        
    return None


    

    
    



def moveFish(board, sx, sy): 
    
    
    for num in range(1, 17):
        
        fish = findFish(board, num)
        
        if fish != None: 
                
            i, j = fish 
            dir = board[i][j][1] 
            
            for d in range(8):
                
                nx = i+dx[dir]
                ny = j+dy[dir]
                
                if 0<=nx and nx < 4 and 0<=ny and ny < 4 and (nx, ny) != (sx, sy):
                    
                    board[i][j][1] = dir
                    board[nx][ny], board[i][j] = board[i][j], board[nx][ny]
                    break
                
                dir = (dir+1)%8
                    
                    
        
      
def sharkMove(board, sx, sy):
    
    arr = [] 
    dir = board[sx][sy][1]
    
    for _ in range(4):
        
        sx = sx + dx[dir]
        sy = sy + dy[dir]
        
        if 0<=sx and sx<4 and 0<=sy and sy<4 and board[sx][sy][0] != -1:
            arr.append([sx, sy])
            
    
    return arr
        
    
   

def dfs(x, y, sum):
    
    global board
    global maxSum 
    
    beforeBoard = copy.deepcopy(board)
    
    sum += board[x][y][0]
    board[x][y][0] = -1 
    
    moveFish(board, x, y)
    
    arr = sharkMove(board, x, y)
    
    
    if len(arr) == 0:
        board = copy.deepcopy(beforeBoard)
        maxSum = max(maxSum, sum)
        return 
    
    for nx, ny in arr:
        dfs(nx, ny, sum)
        
    board = copy.deepcopy(beforeBoard)



dfs(0, 0, 0)



print(maxSum)