백준_18430_무기공학(python)

※ 접근법

n의 범위가 크지 않았기 때문에 모든 경우의 수를 백트래킹을 활용하여 큰 수를 구해야겠다고 생각했다. 4가지 모양을 가지고 각 좌표에 대해서 해당 모양이 될 수 있는지 없는지를 범위와, 방문 여부로 판단했다. 

 

※ 풀이 

1. 0,0부터 visited,0을 가지고 dfs(solve함수)를 시작한다.

2. y좌표를 1씩 이동했고 y좌표가 배열의 범위를 벗어났다면 x += 1, y= 0을 해줬다.

3. 최댓값을 어느 시점에서 걸어서 백트래킹을 걸까(return을 할까) 했었는데 x가 배열의 범위를 벗어났을때는 이미 탐색을 다 한 것이니 x == n일때 해주면 됐다.

n,m = map(int,input().split())

data = [list(map(int,input().split())) for _ in range(n)]

max_num = 0

def high_left(r,c,visited):
    if c + 1 == m or r + 1 == n:
        return False
    if visited[r][c] == 1 or visited[r][c+1] == 1 or visited[r+1][c] == 1:
        return False
    visited[r][c] = 1
    visited[r][c+1] = 1
    visited[r+1][c] = 1
    return True

def high_right(r,c,visited):
    if c -1 < 0 or r + 1 == n:
        return False
    if visited[r][c] == 1 or visited[r+1][c] == 1 or visited[r][c-1] == 1:
        return False
    visited[r][c] = 1
    visited[r+1][c] = 1
    visited[r][c-1] = 1
    return True

def low_left(r,c,visited):
    if c + 1 == m or r -1 < 0:
        return False
    if visited[r][c] == 1 or visited[r-1][c] == 1 or visited[r][c+1] == 1:
        return False
    visited[r][c] = 1
    visited[r-1][c] = 1
    visited[r][c+1] = 1
    return True

def low_right(r,c,visited):
    if c - 1 < 0 or r - 1 < 0:
        return False
    if visited[r][c] == 1 or visited[r-1][c] == 1 or visited[r][c-1] == 1:
        return False
    visited[r][c] = 1
    visited[r-1][c] = 1
    visited[r][c-1] = 1
    return True

def solve(x,y,visited,count):
    global max_num
    if y == m:
        y = 0
        x += 1
    if x == n:
        max_num = max(count,max_num)
        return
    if high_left(x,y,visited):
        solve(x,y+1,visited,count+ 2*data[x][y] + data[x][y+1] + data[x+1][y])
        visited[x][y] = 0
        visited[x][y+1] = 0
        visited[x+1][y] = 0

    if high_right(x,y,visited):
        solve(x,y+1,visited,count+2*data[x][y]+ data[x][y-1] + data[x+1][y])
        visited[x][y] = 0
        visited[x][y-1] = 0
        visited[x+1][y] = 0

    if low_right(x,y,visited):
        solve(x,y+1,visited,count+2*data[x][y] + data[x-1][y] + data[x][y-1])
        visited[x][y] = 0
        visited[x-1][y] = 0
        visited[x][y-1] = 0
    
    if low_left(x,y,visited):
        solve(x,y+1,visited,count+2*data[x][y] + data[x-1][y] + data[x][y+1])
        visited[x][y] = 0
        visited[x-1][y] = 0
        visited[x][y+1] = 0
    solve(x,y+1,visited,count)

visited = [[0] * m for _ in range(n)]
solve(0,0,visited,0)
print(max_num)

※ 회고

첫 번째 착각

처음에는 이중 포문을 돌면서 배열 좌표 하나하나 dfs를 돌라했었다. 이럴 경우 이전 좌표에 대해서는 고려를 못 해준다.

두 번째 착각

dfs함수에서 좌표 이동을 할 때 재귀로 인해 자연스럽게 좌표 이동이 됐어야 했는데 임의로 좌표 이동을 하려고 했었다.