[BOJ] 14500 : 테트로미노 [브루트포스](Python)

문제 링크

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

14500번: 테트로미노

소스 코드

import sys
input = sys.stdin.readline

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

graph = [list(map(int,input().rstrip().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)] # 방문 리스트 초기화
maximum = max(map(max,graph)) # 그래프 중 최댓값 저장

dx = [1,-1,0,0] # 방향 벡터
dy = [0,0,1,-1]

# 행,열,합,길이
def dfs(x,y,temp,leng):
    global answer
    if answer >= temp + maximum * (4-leng):
        return # 최대값으로 나머지를 이어붙여도 현재까지의 최댓값을 넘지 못하는 경우

    if leng == 4: # 네 개의 블록이 이어진 경우
        answer = max(answer,temp) # 최댓값 갱신
        return

    if x < 0 or x >= n or y < 0 or y >= m: # 그래프 범위 바깥인 경우
        return
    
    for i in range(3): # 세 개 블록 이어붙이기
        nx = x + dx[i]
        ny = y + dy[i]

        # 범위 내에 포함되며 방문한 적 없는 블록인 경우
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            # 'ㅗ,ㅜ,ㅏ,ㅓ' 블록
            if leng == 2:
                visited[nx][ny] = True                
                dfs(x,y,temp+graph[nx][ny],leng+1)
                visited[nx][ny] = False

            # 그 외의 블록
            visited[nx][ny] = True
            dfs(nx,ny,temp+graph[nx][ny],leng+1)
            visited[nx][ny] = False
    return

answer = 0
for i in range(n):
    for j in range(m):
        temp = graph[i][j] # 시작 블록으로 초기화
        leng = 1 # 길이 1

        visited[i][j] = True # 방문 처리
        dfs(i,j,temp,leng)
        visited[i][j] = False # 미방문 처리로 복구

print(answer)

 

해설

• DFS를 이용한 완전탐색(브루트 포스)이면서 백트랙킹이다.
• 'ㅜ' 모양의 블럭은 따로 탐색해야 한다.

 여백이 많아서 길어보이지만 사실 일반적인 백트랙킹 유형과 풀이 자체는 유사하다.

answer = 0
for i in range(n):
    for j in range(m):
        temp = graph[i][j] # 시작 블록으로 초기화
        leng = 1 # 길이 1

        visited[i][j] = True # 방문 처리
        dfs(i,j,temp,leng)
        visited[i][j] = False # 미방문 처리로 복구

print(answer)

여기를 보면 그래프의 모든 좌표에 dfs를 수행하는 것을 알 수 있다.

이때 시작하는 블록 graph[i][j] 의 값을 temp에 저장하고, 이 블록에서 시작하므로 연결된 블록의 길이 1을 매개변수로 전달한다.

또한 백트랙킹 유형이므로 dfs 전후에 방문처리를 조작해야 한다.

 

백트랙킹

우리는 다섯 가지의 블록을 확인해야 한다. 심지어 이를 회전하거나 대칭하는 것도 가능하다.

주목할 점은 네 칸으로 이어진 블록이라는 것이다.

어떤 시작점을 기준으로 세 칸을 더 움직인 경로를 잇게 되면 이는 문제에서 제시한 블록들이 된다.

 

예를 들어 오른쪽으로만 세 칸을 이동하면 'ㅡ' 모양이 될 것이고, 오른쪽으로 한 칸 + 아래로 한 칸 + 왼쪽으로 한 칸을 움직이면 'ㅁ' 모양이 될 것이다.

 

따라서 시작점을 기준으로 세 칸을 더 움직일 수 있는 모든 경우의 수를 탐색하고 이때의 최댓값을 갱신해야 한다.

 

'ㅜ' 블록은 따로 구하기

위에서 구한 블록들과 다르게 'ㅜ' 모양의 블록은 따로 구해야 한다. 이미 처리한 블록으로 다시 돌아와야 하기 때문이다.

예를 들어 시작점을 기준으로 오른쪽으로 한 칸 가면 ㅁㅁ 와 같은 모양이 될 것이다(ㅁ이 블록 한 칸).

여기서 오른쪽으로 한 칸 더 가면 ㅁㅁㅁ이 될 것이다. 그러면 'ㅜ' 모양을 만들기 위해서는 두 번째 블록으로 돌아와 아래로 내려가야 한다. 뒤집힌 'ㅗ' 모양도 마찬가지다.

 

ㅁㅁㅁ      ㅁ

   ㅁ      ㅁㅁㅁ

 

따라서 지금까지 이은 블록의 개수가 2개인 경우 따로 dfs를 수행해야 한다.

이때 dfs에 전달하는 인자는 이동한 블록의 좌표가 아닌 출발했던 블록의 좌표가 되어야 한다.

 

이를 코드로 구현한 것은 다음과 같다.

 # 범위 내에 포함되며 방문한 적 없는 블록인 경우
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            # 'ㅗ,ㅜ,ㅏ,ㅓ' 블록
            if leng == 2:
                visited[nx][ny] = True                
                dfs(x,y,temp+graph[nx][ny],leng+1)
                visited[nx][ny] = False

            # 그 외의 블록
            visited[nx][ny] = True
            dfs(nx,ny,temp+graph[nx][ny],leng+1)
            visited[nx][ny] = False

이때 역시 dfs 전후로 방문처리를 했다가 풀어줌으로써 한 점에서 이동할 수 있는 모든 경우의 수를 살펴볼 수 있도록 해야 한다.

 

효율적인 처리를 위한 팁(불필요한 연산 제거)

사실 여기까지가 일반적인 완전탐색에 대한 dfs 풀이인데 이렇게만 제출하면 시간 초과 판정을 받게 된다.

진짜로 모든 경우에 대해서 도형을 만들어보고 그 결과를 비교할 필요가 없기 때문이다.

maximum = max(map(max,graph)) # 그래프 중 최댓값 저장

def dfs(x,y,temp,leng):
    global answer
    if answer >= temp + maximum * (4-leng):
        return # 최대값으로 나머지를 이어붙여도 현재까지의 최댓값을 넘지 못하는 경우

maximum이라는 변수에는 그래프 내에 존재하는 최대의 값이 저장되어 있다.

그리고 dfs의 첫 종료 조건은 answer가 temp(현재 블록까지의 누적합)에 이 최댓값들을 더한 것 이상인 경우다.

 

이게 무슨 뜻이냐면, 예를 들어 첫 줄과 두 번째 줄의 정보가 [5,5,5,5], [3,1,1,1] 이런 식으로 주어졌다고 생각해보자.

이때 maximum은 그래프에서 가장 큰 값 5를 갖게 된다.

그리고 첫째 줄에서 얻을 수 있는 최댓값은 가로로 5,5,5,5를 더한 20이 된다. 'ㅡ' 모양이다.

 

둘째 줄을 검사하는 경우를 생각해보자.

만약 그래프가 위와 같다면 'ㅡ' 모양만 검사하겠지만 실제로는 더 많은 경우를 검사해야 한다.

하지만 temp = graph[1][0] = 3 으로 시작한 이 블록 덩어리는, 뒤에 세 개 연속 최댓값 5를 붙여줘도 현재의 최대를 넘지 못한다.

 

즉, 현재의 최대 = 20, 현재 블록 = 3, 남은 블록 3개 x 5(최댓값으로 가정) = 3 + 15

따라서 20 > 18 이므로 애초에 검사를 수행할 필요가 없는 것이다.

조금 더 직관적으로 생각해보면 최댓값이 저장된 상태에서는 시작점만 확인해도 굳이 검사를 수행할 필요가 없는 것이다.

 

이를 추가하면 굳이 하지 않아도 될 수많은 연산 과정들이 생략되어 빠른 속도로 처리가 된다.