[백준] 18430 무기공학 파이썬/Python

https://www.acmicpc.net/problem/18430

18430번: 무기 공학

백트레킹 문제 ! 

삽질 많이 했다 ㅜㅜ

dx, dy 는 4가지 부메랑의 모양을 만들어주기 위해서 좌표를 구하는 연산을 위해 만들었다. 
노란색 칸을 (x, y) 라고 했을 때 하얀색 칸의 좌표에 도달하기 위한 값을 저장했다. 

또한 array 를 탐색할 때 (0, 0) .. (n-1, m-1) 를 부메랑의 중심 좌표 (노란색으로 칠한 부분)로 두고 부메랑으로 만들 수 있는지 없는지 확인한다. 
부메랑으로 만들 수 있는 경우라면 visited[i][j] 에 True 를 저장하여 방문처리를 하고, 부메랑으로 만들 었을 때의 값을 더해서 dfs() 함수의 인자로 전달한 한다. 
부메랑으로 만들지 않는 경우도 있기 때문에, 다시 visited[i][j] 에 False 를 저장하여 백트래킹한다. 
그리고 부메랑으로 만들지 않는 경우를 호출하는데, 이 때 주의할 점은 for 문 바깥에서 호출해야 한다. 

if not visited[x][y]:
    for i in range(4):
        nx1 = x + dx[i][0]
        ny1 = y + dy[i][0]
        nx2 = x + dx[i][1]
        ny2 = y + dy[i][1]

        # 좌표들이 범위에 있는지 체크하기
        if 0 <= nx1 < n and 0 <= nx2 < n and 0 <= ny1 < m and 0 <= ny2 < m:
            if not visited[nx1][ny1] and not visited[nx2][ny2]:  # 방문하지 않았는지 확인하기
                visited[x][y] = True
                visited[nx1][ny1] = True
                visited[nx2][ny2] = True
                temp = array[x][y] * 2 + array[nx1][ny1] + array[nx2][ny2]
                dfs(x, y + 1, temp + total)  # 이번 칸들 3개를 무기로 선택하는 경우
                visited[x][y] = False
                visited[nx1][ny1] = False
                visited[nx2][ny2] = False
                #  dfs(x, y + 1, total)  # 선택하지 않는 경우 여기서 호출하면 안됨

for문 안에서 호출하게 하는 실수를 했었는데, 이런 경우에는 해당 위치에서 부메랑을 선택한 경우 , 다시 선택하지 않는 경우만을 확인하는 케이스로 넘어 가게 된다. 

재귀함수 탐색을 종료 하는 조건은 x와 y 의 값이 maximum 값인 n, m 으로 확인한다. 
dfs 탐색을 0,0로 시작하는데, 부메랑의 중심 좌표로써 0,0 ~ n-1, m-1 를 모두 탐색하는 것이 목표이므로, 
dfs 함수 안에서 x, y 좌표값을 하나씩 증가시켜서 모든 경우를 확인하게 한다. 

dfs(x, y + 1, temp + total)  # 이번 칸들 3개를 무기로 선택하는 경우

dfs 인자값으로 x, y 위치 좌표를 전달할 때 y를 1씩 증가시켰다. 

# x, y 더이상 탐색할 수 없을 때 확인하기
if y == m:
    x += 1
    y = 0
if x == n:
    answer = max(answer, total)
    return

y가 m 값에 도달하면 인덱스 초과가 나므로 다시 y=0으로 초기화 해 준다. 또한 x 값이 0 인경우 y에 대해 모두 확인을 했다는 의미이므로 x 값을 1 증가 시켜준다. 
ex) 예제 1에서 n = 3, m = 3 인경우
(0, 0) (0, 1) (0, 2) 이후 (0, 3) 일 때 if 문을 통하여 (1, 0) 으로 만들어 준다. 

그리고 (n-1, m-1) 좌표까지 모두 탐색하게 되어 (n, m-1)에 도달하게 되면 재귀 함수를 탈출한다. 해당 좌표에서 부터 가능한 부메랑 만드는 경우를 모두 확인했으므로, 최댓값을 answer 와 비교하여 갱신해 준다. 

[전체 코드]

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
result = 0
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

# 1 - 2 - 3 - 4 모양 순서대로 좌표값
dx = [(0, 1) ,(0, -1), (-1, 0), (0, 1)]
dy = [(-1, 0),(-1, 0), (0, 1), (1, 0)]

visited = [[False] * m for _ in range(n)]  # 방문 여부
answer = 0

def dfs(x, y, total):
    global answer
    # x, y 더이상 탐색할 수 없을 때 확인하기
    if y == m:
        x += 1
        y = 0
    if x == n:
        answer = max(answer, total)
        return
    if not visited[x][y]:
        for i in range(4):
            nx1 = x + dx[i][0]
            ny1 = y + dy[i][0]
            nx2 = x + dx[i][1]
            ny2 = y + dy[i][1]

            # 좌표들이 범위에 있는지 체크하기
            if 0 <= nx1 < n and 0 <= nx2 < n and 0 <= ny1 < m and 0 <= ny2 < m:
                if not visited[nx1][ny1] and not visited[nx2][ny2]:  # 방문하지 않았는지 확인하기
                    visited[x][y] = True
                    visited[nx1][ny1] = True
                    visited[nx2][ny2] = True
                    temp = array[x][y] * 2 + array[nx1][ny1] + array[nx2][ny2]
                    dfs(x, y + 1, temp + total)  # 이번 칸들 3개를 무기로 선택하는 경우
                    visited[x][y] = False
                    visited[nx1][ny1] = False
                    visited[nx2][ny2] = False
    dfs(x, y + 1, total)  # 선택하지 않는 경우


dfs(0, 0, 0)
print(answer)