14391. 종이 조각 (Python)

 

14391번: 종이 조각

 

풀이

 백트래킹을 통해서 모든 경우의 수를 탐색하면 된다. 자세한건 코드의 주석을 참고하자

 

코드

# (x, y)에서 (x, ny) 또는 (nx, y)까지 사용된 곳이 있는지를 체크하기 위한 함수
def checkVisited(x, y, nx, ny):
    for i in range(x, nx + 1):
        if visited[i][y]: # 이미 사용된 곳이라면 False 반환
            return False

    for i in range(y, ny + 1):
        if visited[x][i]: # 이미 사용된 곳이라면 False 반환 
            return False

    return True


# visited 배열을 flag로 바꿔주기 위한 메서드 
def toggleVisited(x, y, nx, ny, flag):
    for i in range(x, nx + 1):
        visited[i][y] = flag

    for i in range(y, ny + 1):
        visited[x][i] = flag


# (x, y)에서 (x, ny) 또는 (nx, y)까지의 숫자를 구하기 위한 메서드 
def calcNum(x, y, nx, ny):
    ret = board[x][y]

    for i in range(x + 1, nx + 1):
        ret = ret * 10 + board[i][y]

    for i in range(y + 1, ny + 1):
        ret = ret * 10 + board[x][i]

    return ret


def dfs(idx, total):
    if idx == N * M: # 모든 곳이 사용되었으면 res 업데이트 후 종료
        global res
        res = max(res, total)
        return

    x, y = idx // M, idx % M # idx를 기준으로 (x, y) 좌표를 구한다

    if visited[x][y]: # 이미 사용된 곳이면 다음 인덱스로 함수 호출
        dfs(idx + 1, total)
        return

    for i in range(7):
        nx = x + dx[i]
        ny = y + dy[i]

        # 범위를 넘었거나 이미 사용된 좌표가 존재하면 continue 
        if nx >= N or ny >= M or not checkVisited(x, y, nx, ny):
            continue
        
        # 백트래킹 
        toggleVisited(x, y, nx, ny, True)
        dfs(idx + 1, total + calcNum(x, y, nx, ny))
        toggleVisited(x, y, nx, ny, False)


if __name__ == '__main__':
    N, M = map(int, input().split())
    dx = [0, 0, 0, 0, 1, 2, 3]
    dy = [0, 1, 2, 3, 0, 0, 0]
    visited = [[False for _ in range(M)] for _ in range(N)]
    board = [[0 for _ in range(M)] for _ in range(N)]
    res = 0

    for i in range(N):
        num = input()
        for j in range(M):
            board[i][j] = int(num[j])

    dfs(0, 0)
    print(res)