백준 문제 중 2225번, 그래프탐색, ‘테트로미노(DFS)’
백준 문제 중 14500번
https://www.acmicpc.net/problem/14500
문제
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
입력
첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
풀이
핵심 아이디어
이전에 브루트 포스로 풀어봤던 14500문제를 테트로미노를 DFS로 풀어보았다. 이 문제에 DFS를 적용해야겠다는 아이디어를 떠올리는게 쉽지가 않지만, 한번 풀이를 보면 아주 명확하게 DFS로 풀 수 있는 문제라는걸 알 수 있다.
-
시작노드를 기준으로 위 아래 좌 우 네방향 어디로든 갈 수 있다면, 4번의 이동을 진행하고 나면 방문한 노드들의 모양이 모두 ‘ㅗ’ 모양을 제외한 테트로미노들의 모양이 됨을 생각할 수 있다.
-
‘ㅗ’ 모양은 DFS를 진행하다가 2번째 노드를 방문한 뒤 3번째 노드를 방문할 때 재귀적으로 호출될 DFS에서 탐색의 시작점을 3번째 노드가아닌 2번째의 노드로 설정한다면 1,2,3 중 2번을 기준으로 위 아래 탐색을 하게 될것이고, 4개 노드의 모양이 ‘ㅗ’를 회전하는 형태가 될 것이다.
이렇게 모든 경우의 테트로미노를 DFS로 탐색하며 블록이 놓인 수들의 최대합을 조사하게끔 코드를 구성하면 된다.
요약
간략하게 코드의 흐름을 살펴보자면 이렇다.
- 이미 방문한 노드에 방문표시를 하기 위한 리스트 visited를 선언한다.
- 재귀적으로 dfs를 구현할 함수 dfs(row, col, depth, sum) 함수를 선언한다. row, col 은 행과 열을 depth는 재귀의 깊이, 즉 이번 차례에 방문 중인 노드의 순번 sum은 이전까지의 블록에 표기된 수들의 합을 나타낸다.
- 아직 방문하지 않았고 row, col이 인덱스의 범위를 벗어나지 않는경우에 한해서 재귀적으로 네 방향을 DFS로 탐색을 한다.
- 단. depth가 2일때는 ‘ㅗ’ 모양 탐색을 위해 세번째점 까지의 블록합을 가지고, 시작점을 두번째 노드로하는 DFS를 한다.
- depth가 4가된다면 이전까지의 모든 블록합 sum들 중 최대값을 ans에 저장하고 리턴하여 재귀를 탈출한다.
- 주어진 칸들중 최대값을 max_of_all이라고 할때 지금 저장된 ans가 sum + max_of_all*(4-depth) (즉 지금까지의 블록합뒤에 최대로 큰 값들만 올경우)보다 크다면 ans가 항상 최대이므로 바로 리턴하여 조기에 재귀를 탈출한다.
생각하기 어려운 부분은 6번정도이고 1 ~ 5번 정도만 구현해도 pypy로 아슬아슬하게 시간초과에 걸리지 않는다.
위의 내용들을 코드로 작성하면 다음과 같다.
n,m = map(int, input().split())
board = []
for _ in range(n):
board.append(list(map(int,input().split())))
visited = [[False for _ in range(m)] for _ in range(n)]
# 상하좌우 이동에 쓰일 변수
drow, dcol = [1, -1, 0, 0],[0, 0, 1, -1]
# 주어진 정수중 최대값
max_of_all = max(max(*board))
ans = 0
def dfs(row, col, depth, sum):
global ans
# 조기종료 조건으로 최적화
if sum + max_of_all*(4-depth)<ans:
return
if depth == 4:
ans = max(ans, sum)
return
for i in range(4):
nrow, ncol = row + drow[i], col + dcol[i]
# 상하좌우 중 인덱스를 벗어나지 않고, 방문하지 않은경우만 dfs진행
if 0<=nrow<n and 0<=ncol<m and not visited[nrow][ncol]:
# 'ㅗ'모양 탐색을 위한 처리
if depth == 2:
visited[nrow][ncol] = True
dfs(row, col, depth+1, sum + board[nrow][ncol])
visited[nrow][ncol] = False
visited[nrow][ncol] = True
dfs(nrow, ncol, depth + 1, sum + board[nrow][ncol])
visited[nrow][ncol] = False
for row in range(n):
for col in range(m):
visited[row][col] = True
dfs(row, col, 1, board[row][col])
visited[row][col] = False
print(ans)
19
Leave a comment