문제 링크

문제 소개

해당 무넺는 어떠한 보드에 부메랑을 4가지 모양으로 둘 수 있을 때, 합이 최대가 되는 값을 구하는 문제이다.

문제 분석

해당 문제를 풀기 전에, 단순무식하게 브루트포스를 사용하지 않고 백트래킹을 활용해서 중간에 조건이 성립되지 않을 경우는 멈추고 답을 찾아간다면 문제를 풀 수 있을 것이다.

여기서 조건은 다른 부메랑과 겹치지 않는다는 조건일 것이다.

사실 DFS에 익숙하다면 쉽게 풀 수 있을 문제일것이다.

우선 우리는 3가지로 나눴다.

def dfs(y, x, value, visited):
    global maxVal
    if x == M:
        pass
    elif y == N:
        pass
    else:
    	pass

우선, 어떤 배치를 했을 때 다음 배치로 이어지는 조건이 없기 때문에 하나씩 옮겨가면서 상황을 봐야한다. 이렇게 진행할 때, 우린 2차 반복문을 사용할 수 있지만 나중에도 반복문을 써야되는 불상사(만약 이렇게 할거면, 먼저 시작점에서 2차 반복문을 돌리고 어떠한 부메랑 형태로 위치했을 때 그 다음 중심 위치도 2차 반복문을 써야함)가 발생하기 때문에 위와 같이 재귀함수 모습으로 구현한다면 쓸데없는 코드를 줄일수 있다.

이렇게 3가지로 나눈 이유는 아래와 같다.

1. 기본적으로 x좌표를 하나씩 더하며 진행
2. 만약 해당 x좌표의 값들을 다 지났다면, y좌표를 하나 더해 다음 줄로 이동
3. 만약 넘어갈 y좌표가 끝이라면 최대값을 비교하고 종료시킨다.

그럼으로 2번과 같이 x좌표가 끝났을 때를 x==M 조건문을 뒀고, 넘어갈 y좌표가 끝일 때는 y==N이라고 둘 것이다. 그리고 이 둘의 상황이 아니라면 정상적으로 x를 하나씩 더하며 진행할 것이다.

def dfs(y, x, value, visited):
    global maxVal
    if x == M:
        pass	// 2번
    elif y == N:
        pass	// 3번
    else:
    	pass	// 1번

참고로, DFS를 재귀함수로 풀때는 위와 같이 상황을 쪼개가며 본다면 문제를 풀기 좋다.

우선 2번과 같이 x가 끝났을 때는 다음 y좌표로 넘어가기 위해 아래와 같이 추가할 것이다.

dfs(y + 1, 0, value, visited)

그 다음, 3번과 같이 해당 영역을 다 봤을 때, 즉 넘어갈 다음 y좌표가 없을 때는 값을 비교해서 최대값을 아래와 같이 찾는다

maxVal = max(maxVal, value)
        return

여기서 헷갈릴만한 점은, 해당 코드가 실행된 이후에는 넘어갈 것이 없기 때문에 return으로 끝냈다.

다음으로 1번과 같이 x를 하나씩 옮겨가는 것은 아래의 코드와 같이구현했다.

dfs(y, x + 1, value, visited)

정리하면 로직은 아래와 같다.

def dfs(y, x, value, visited):
    global maxVal
    print(y,x)
    if x == M:
        dfs(y + 1, 0, value, visited)
    elif y == N:
        maxVal = max(maxVal, value)
        return
    else:
        dfs(y, x + 1, value, visited)

여기서 끝이 아니다. 우리는 이렇게 옮겨가면서 해당 위치에 부메랑을 어떻게 놓을건지 생각해야한다.

그럼으로 우리는 1번 부분에 코드를 추가해야할 것이다.

먼저, visited 리스트를 사용해서 방문 처리를 하고 방문하지 않았다면 해당 위치를 기점으로 4가지 부메랑 위치를 각각 계산하고 놓을 수 있는지 확인하고 방문처리를 한 다음, 계속 이어나간다.

이러한 내용을 코드로 풀어내면 아래와 같다.

if not visited[y][x]:
    for d1 in range(4):
        d2 = (d1 + 1) % 4
        y1, x1, y2, x2 = y + controlY[d1], x + controlX[d1], y + controlY[d2], x + controlX[d2],
        if -1 < y1 < N and -1 < y2 < N and -1 < x1 < M and -1 < x2 < M:
            if not visited[y1][x1] and not visited[y2][x2]:
                visited[y][x], visited[y1][x1], visited[y2][x2] = True, True, True
                dfs(y, x + 1, value + board[y][x] * 2 + board[y1][x1] + board[y2][x2], visited)
                visited[y][x], visited[y1][x1], visited[y2][x2] = False, False, False

전체 코드 및 요약

정리하자면, 우리는 어떤 위치에서 해당 위치가 만약 x좌표의 끝이라면 다음 y좌표로 이동해주고 y좌표의 끝이라면 최대값을 비교한다.

그것도 아나리면, 우리는 현재 위치에 부메랑을 놓을 경우랑 놓지 않고 지나갈 경우를 생각해야한다.

import sys


def dfs(y, x, value, visited):
    global maxVal
    if x == M:
        dfs(y + 1, 0, value, visited)
    elif y == N:
        maxVal = max(maxVal, value)
        return
    else:
        if not visited[y][x]:
            for d1 in range(4):
                d2 = (d1 + 1) % 4
                y1, x1, y2, x2 = y + controlY[d1], x + controlX[d1], y + controlY[d2], x + controlX[d2],
                if -1 < y1 < N and -1 < y2 < N and -1 < x1 < M and -1 < x2 < M:
                    if not visited[y1][x1] and not visited[y2][x2]:
                        visited[y][x], visited[y1][x1], visited[y2][x2] = True, True, True
                        dfs(y, x + 1, value + board[y][x] * 2 + board[y1][x1] + board[y2][x2], visited)
                        visited[y][x], visited[y1][x1], visited[y2][x2] = False, False, False

        dfs(y, x + 1, value, visited)


input = sys.stdin.readline
N, M = map(int, input().split())
maxVal = 0
board = [list(map(int, input().split())) for _ in range(N)]
controlY, controlX = [0, 1, 0, -1], [1, 0, -1, 0]

dfs(0, 0, 0, [[False for _ in range(M)] for _ in range(N)])
print(maxVal)