[백준 - Python] 14500. 테트로미노 (완전 탐색)

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

14500번: 테트로미노

 

코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * M for _ in range(N)]
answer = 0

def dfs(x, y, step, total):
    global answer

    if step == 4:
        answer = max(answer, total)
        return

    for dx, dy in d:  # 튜플인 원소를 for 문 안에서 바로 분해 가능 !
        nx = x + dx
        ny = y + dy
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
            # 'ㅗ' 모양에 대한 탐색
            if step == 2:
                visited[nx][ny] = True
                # dfs의 1,2번 인자로 nx, ny가 아닌 x, y를 넣어줌으로써 2번쨰 블록까지 이어 붙였을 때, 새로운 블록을 이어붙일 다음 블록을 탐색하지 않고 다시 기존 블록 위치에서 탐색
                dfs(x, y, step + 1, total + board[nx][ny])
                visited[nx][ny] = False

            visited[nx][ny] = True
            dfs(nx, ny, step+1, total + board[nx][ny])
            visited[nx][ny] = False


for i in range(N):
    for j in range(M):
        visited[i][j] = True
        dfs(i, j, 1, board[i][j])
        visited[i][j] = False

print(answer)

 

기본적인 틀은 맞게 짰지만 정답까지 구현하지는 못한 문제였다

 

이 문제의 해결 포인트는 다섯 종류의 테트로미노 중에서

'ㅗ' 모양의 테트로미노는 나머지 모양들과는 다르게

일반적인 dfs 방식으로는 확인할 수 없는 모양이라는 것을 알고

해당 모양을 다르게 처리하는 것인 것 같다

 

우선, N, M에 종이 사이즈를 입력 받고

board 변수에 종이의 각 칸에 적힌 숫자들을 저장한다

 

방향 전환 리스트 d와 방문 여부 처리 리스트 visited를 선언하고

최종 답안을 출력할 answer 변수도 선언한다

(방향 전환 리스트를 dx, dy 각각으로 선언하는 방법 외로도

튜플로 x,y 좌표의 변화량을 넣고

for 문 안에서 튜플인 원소들을 바로 분해하는 코드도 가능하다)

 

이중 반복문으로 주어진 종이의 모든 칸을 탐색하며 방문 처리를 해주고 dfs를 실행해준다

 

dfs 인자로

칸의 좌표값인 x,y 값과 이어진 칸의 개수를 나타내는 step과

테트로미노가 놓여져 있는 칸들의 정수값들의 합을 넣어준다

 

dfs가 재귀적으로 돌면서 최댓값을 갱신해나갈 것이기 때문에

전역으로 answer 변수를 선언해주고

네 방향에 대해서 주어진 범위 안에 있고 방문하지 않은 칸인 경우에

dfs를 실행시켜준다

 

가능한 모든 방향에 대해서 최댓값이 있는지를 확인해줘야 하기 때문에

dfs 실행 전에 방문 처리를 해주고

dfs 실행 후에 방문 처리를 해제해주는 백트래킹 코드를 넣어준다

 

이때 아까 위에서 언급했듯이,

'ㅗ' 모양에 대한 처리를 해주어야 한다.

'ㅗ' 모양의 특징을 설명해보자면,

가운데 블록을 기준으로 네 방향 중 세 방향만 칸이 이어져 있다

 

따라서, 2번째 블록까지 붙인 경우인

step이 2인 경우에 다시 전 블록(가운데 블록)으로 돌아가서

다시 네 방향과 방문하지 않은 블록을 살펴본다

해당 경우에 대한 dfs를 실행할 때에도

백트래킹으로 모든 방향에 대해 확인을 해준다

 

테트로미노는 정사각형 4개를 이어붙인 폴리오미노이므로

종료 조건으로 step이 4가 되었을 때

현재 저장된 값과 비교를 통해 최댓값을 갱신해준다

 

위의 코드는 파이썬으로 통과는 되지만, 실행 시간이 매우 길다

 

실행시간을 단축할 수 있는 방법 중의 하나가

특정 조건을 만족하지 못하면 탐색을 끝까지 진행하지 않도록 조건을 걸어주는 것이다

 

#모든 좌표 중의 최댓값
max_val = max(map(max, board))

# 종료 조건 추가
if total + max_val*(4-step) <= answer:
	return

 

입력으로 주어진 board 이차원 배열의 정수값들 중,

최댓값을 max_val 변수에 저장하고 해당 변수를 활용해 조건식을 만들 수 있다.

 

dfs 함수 내에서 종료 조건으로,

현재까지 진행한 step 이후의 스텝이 모두 max_val 값을 가진다고 가정을 했을 때,

현재 저장되어 있는 answer 값보다 여전히 작은 경우에는 탐색을 계속 진행한다고 하여도

절대 최댓값이 되지 않는다는 점을 활용했다

(문제를 처음 접했을 때, 내가 이런 생각을 해 낼 수 있을까..?)

 

해당 조건문을 추가함으로써 시간을 엄청나게 단축시킬 수 있다!

 

 

위의 사진에서

첫 번째 줄은 조건문을 추가하지 않은 코드이고

두번째 줄은 조건문을 추가한 코드이다

 

실행 속도가 거의 40배 넘게 차이가 나는 것을 확인할 수 있었다 !!!

 

조건문 추가한 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
max_val = max(map(max, board))  # 모든 좌표 중 최댓값 **
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * M for _ in range(N)]
answer = 0

def dfs(x, y, step, total):
    global answer

    if total + max_val*(4-step) <= answer:  # 종료 조건 1 : 탐색을 계속 진행해도 최댓값이 안 되는 경우
        return
    if step == 4:
        answer = max(answer, total)
        return

    for dx, dy in d:  # 튜플인 원소를 for 문 안에서 바로 분해 가능 !
        nx = x + dx
        ny = y + dy
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
            # 'ㅗ' 모양에 대한 탐색
            if step == 2:
                visited[nx][ny] = True
                # dfs의 1,2번 인자로 nx, ny가 아닌 x, y를 넣어줌으로써 2번쨰 블록까지 이어 붙였을 때, 새로운 블록을 이어붙일 다음 블록을 탐색하지 않고 다시 기존 블록 위치에서 탐색
                dfs(x, y, step + 1, total + board[nx][ny])
                visited[nx][ny] = False

            visited[nx][ny] = True
            dfs(nx, ny, step+1, total + board[nx][ny])
            visited[nx][ny] = False


for i in range(N):
    for j in range(M):
        visited[i][j] = True
        dfs(i, j, 1, board[i][j])
        visited[i][j] = False

print(answer)

 

 

참고 자료

https://heytech.tistory.com/364