[백준]14500 테트로미노 - 골드 4
[오늘의 문제]
https://www.acmicpc.net/problem/14500
[오늘의 학습 키워드]
- DFS
- 구현
- 브루트포스 알고리즘
1. 문제설명

보드의 크기 N, M이 주어질 때 해당 보드에 테트로미노 블록 1개만 놓아서 최대의 크기를 가지는 경우를 구하는 문제 입니다.
테트로미노는 위 그림처럼 5개의 모양이 존재합니다.
각 모양을 적절히 회전하거나, 뒤집어서 최대의 크기를 가지는 경우 1가지를 구해 그 크기를 출력하는 문제 입니다.
[제한사항]
- 시간 제한 2초
- 메모리 제한 512MB
- 4 ≤ N, M ≤ 500
- 둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
2. 접근방식

테트로미노 블록에는 1가지 특징이 있습니다.
바로 ㅗ 모양을 제외한 나머지 블록은 한붓그리기가 가능하다는 것입니다.
ㅡ, ㅁ, ㄴ, ㄹ 같은 모양들은 한 붓으로 그릴 수 있습니다.
그 말은 DFS 탐색을 통해서 한번에 탐색이 가능하다는 의미이죠
모든 테트로미노 블록의 길이는 4입니다. 길이가 4만 넘지않는다면 어떠한 방식으로 4줄을 그어도 테트로미노 블록이 된다는 소리입니다.
예시 그림을 살펴보죠 한 붓으로 그린 4의 길이인 블록을 그려 보겠습니다.

어떻게 그어도 길이가 4가 되기만 한다면 테트로미노 블록 중 한가지가 나오게 되죠
즉, 이 블록을 찾는 방법은 DFS 탐색을 통해서 파악이 가능합니다.
그러나 ㅗ 모양 블록은 예외가 존재하죠
이 블록을 만들기 위해서는 3줄까지 갔다가 돌아와서 새로운 방향으로 탐색을 해야 합니다.
그러나 좀더 쉽게 생각해보죠

ㅗ 모양은 무조건 4가지 모양밖에 나오지 않습니다. ㄹ, ㄴ 모양의 경우에는 회전과 뒤집기를 통해서 더 많은 모양이 나올 수 있는데
ㅗ 모양은 무조건 저 4가지 모양밖에 나오지 않죠 이를 한군데로 합치면 왼쪽처럼 십자가 모양이 됩니다.
간단한 원리 입니다. 중심을 기준으로 4방향으로 뻣어나간 모양에서 1군데만 삭제시켜 주면 오른쪽의 ㅗ 모양 테트로미노 모양중 1개가 되는 것입니다.
이 모양도 최대값을 구해야 하니 십자가 모양이 되었을 때는 제일 낮은 값을 가지는 위치 1개를 삭제시켜주고, 그게 아닌 3가지 모양만 구해지면 기존에 구한 테트로미노 값과 비교해서 더 큰 값으로 바꿔주면 되겠죠
코드로 설명해 보겠습니다.
3. 코드
import sys
input = sys.stdin.readline
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 테트로미노 블록 찾기
def DFS(x, y, width, count):
global answer
# 종료 조건
if count == 4:
answer = max(answer, width)
return
# 4방향 중 한 방향으로 뻣어나가면서 모든 경우의 수 찾아주기
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 백 트래킹으로 모든 경우의 수 탐색
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
visited[nx][ny] = True
DFS(nx, ny, width + paper[nx][ny], count + 1) # 테트로미노 길이 계속 더해주면서 DFS 탐색
visited[nx][ny] = False
# ㅗ 모양 탐색
def find(x, y):
global answer
tetromino = paper[x][y] # 현재 위치의 값
width = []
# 현재 위치를 기준으로 4방향으로 뻣어주기
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < M:
width.append(paper[nx][ny])
# 모든 방향이 다 들어간다면 가장 작은 값 삭제
if len(width) == 4:
width.sort(reverse=True)
width.pop()
tetromino += sum(width)
answer = max(answer, tetromino)
# 3방향만 들어간다면 그 값 반환
elif len(width) == 3:
tetromino += sum(width)
answer = max(answer, tetromino)
# 최소 3개의 값이 들어가야 하는데 안되는 경우 테트로미노 X
return
# 입력
N, M = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
answer = 0
# 전체 위치에 대해 테트로미노 블록을 찾아야 하니 2중 for 문
for i in range(N):
for j in range(M):
visited[i][j] = True # 백트래킹을 이용해 모든 경우의 수를 구해야 한다.
DFS(i, j, paper[i][j], 1) # DFS로 한 붓 그리기 가능한 테트로미노 블록 찾기
find(i, j) # ㅗ 모양 찾기
visited[i][j] = False # 따라서 기존 위치에 방문 처리를 초기화
print(answer)
[코드설명]
# 입력
N, M = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
answer = 0
# 전체 위치에 대해 테트로미노 블록을 찾아야 하니 2중 for 문
for i in range(N):
for j in range(M):
visited[i][j] = True # 백트래킹을 이용해 모든 경우의 수를 구해야 한다.
DFS(i, j, paper[i][j], 1) # DFS로 한 붓 그리기 가능한 테트로미노 블록 찾기
find(i, j) # ㅗ 모양 찾기
visited[i][j] = False # 따라서 기존 위치에 방문 처리를 초기화
print(answer)
우선 입력처리를 해주고 DFS 탐색을 실시해줍니다.
테트로미노 블록 모양중 최대값이 되는 모든 경우의 수중 1개를 찾아야 하니 백트래킹을 활용해 주어야 겠죠
이를 위해 visited 배열에 초기값을 방문 처리후 다시 False로 바꿔 방문 처리를 초기화 해줍니다.
ㅗ모양을 제외한 테트로미노 블록은 DFS를 통해서 탐색을 실시하고 ㅗ 모양을 찾기위해 find 함수를 따로 탐색해줍니다.
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 테트로미노 블록 찾기
def DFS(x, y, width, count):
global answer
# 종료 조건
if count == 4:
answer = max(answer, width)
return
# 4방향 중 한 방향으로 뻣어나가면서 모든 경우의 수 찾아주기
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 백 트래킹으로 모든 경우의 수 탐색
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
visited[nx][ny] = True
DFS(nx, ny, width + paper[nx][ny], count + 1) # 테트로미노 길이 계속 더해주면서 DFS 탐색
visited[nx][ny] = False
테트로미노 블록을 찾는 DFS 코드 입니다.
기준 위치를 기준으로 4방향 탐색을 실시합니다.
테트로미노 블록은 현재 위치를 기준으로 적절한 회전, 뒤집기 등을 통해 가장 큰 값을 찾아주어야 합니다.
이 경우 동일하게 백트래킹을 활용해 모든 경우의 수를 찾아 주어야 합니다.
DFS 탐색을 실시할 때 길이가 4까지만 가능한 테트로미노 블록을 찾아주면 ㅗ 모양을 제외한 모든 경우의 수를 찾아줄 수 있죠

이 모양 안에 ㅗ를 제외한 모든 테트로미노 블록 모양이 들어가죠
이 모야은 DFS 탐색시 길이가 4까지 탐색한 경우 탐색가능한 모든 범위와 동일하구요
따라서 이렇게 DFS 탐색을 통해서 모든 경우의 수를 찾아주고 길이가 4까지인 모든 블록을 찾으면 그 중 가장 큰 값은 answer에 입력해 주게 됩니다.
이제는 ㅗ 모양에 대해서 찾아주어야 하죠
# ㅗ 모양 탐색
def find(x, y):
global answer
tetromino = paper[x][y] # 현재 위치의 값
width = []
# 현재 위치를 기준으로 4방향으로 뻣어주기
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < M:
width.append(paper[nx][ny])
# 모든 방향이 다 들어간다면 가장 작은 값 삭제
if len(width) == 4:
width.sort(reverse=True)
width.pop()
tetromino += sum(width)
answer = max(answer, tetromino)
# 3방향만 들어간다면 그 값 반환
elif len(width) == 3:
tetromino += sum(width)
answer = max(answer, tetromino)
# 최소 3개의 값이 들어가야 하는데 안되는 경우 테트로미노 X
return
이 모양은 탐색이 쉽습니다.
현재 위치를 기준으로 4방향 탐색과 동일하기 때문이죠
이때 현재 위치를 기준으로 4방향이 모두 들어간다면 그 중 가장 작은 값은 가지는 1칸을 삭제해주면 현재 위치를 기준으로 가장 큰 값을 가지는 ㅗ모양의 테트로미노를 찾을 수 있죠
그때의 값을 answer에 저장된 값과 비교해 바꿔줍니다.
만약 3가지 값만 들어간다면 한쪽벽에 붙은 경우가 되겠죠 이때의 길이를 answer에 비교해 바꿔주게 됩니다.
그러다 길이가 3미만 이라면 이는 테트로미노가 아니기 때문에 반환 후 종료합니다.
4. 결과

[회고]
처음에는 브루트포스로 접근했습니다.
모든 경우의 수를 하드코딩으로 모양을 구해 해당 경우를 모두 탐색하여 가장 큰 값만 구하려 했었죠
실제로 예제는 모두 통과가 되었습니다.
그러나 이런 방식으로 문제를 해결하니 1가지 문제점이 존재했는데 그게 ㄴ 모양과 ㄹ 모양의 뒤집은 모양을 찾을 수가 없다는 것 이었습니다.
제가 구한 방식은

이런식으로 현재 위치를 기준으로 각 테트로미노 블록을 회전한 위치만 구해주었었기 때문입니다.
이렇게 해서 모든 경우의 수를 구해 dx dy에 리스트로 구분해 작성해주었었죠
그러다 반례를 찾아서 틀리게 되었고
다른 방식을 찾아보자 생각했습니다.
질문게시판을 보다보니 다른 사람들은 DFS로 해결하는 사람들이 있다고 하더라구요 이 문제를 어떻게 DFS 로 풀지? 라고 생각하며 문제를 다시 보았는데 DFS 키워드를 듣고 테트로미노 블록을 보니 충분히 DFS가 가능해 보였습니다.
DFS로 길이가 4까지만 보드를 탐색한다면 충분히 모든 모양의 테트로미노 블록을 구할 수 있었기 때문이죠
이를 위해서 방문배열을 초기화하며 모든 경우를 구하기 위해 백트래킹을 활용하였고 구할 수 없는 단 1가지의 경우이 ㅗ 모양만 예외로 브루트포스를 이용해 돌리려고 했는데
이번에는 dx dy의 접근을 잘못하여 또 틀렸었습니다.
따라서 ㅗ모양도 DFS 처럼 다른 방식이 없을까 생각하다가 전체 4방향중 1방향만 삭제하면 ㅗ모양이 되네? 라고 생각이 떠올라서 그대로 코드로 구현하였고 통과할 수 있었습니다.
이번 문제는 하드코딩으로도 충분히 문제 해결이 가능하였는데 모든 경우의 수를 구해서 dx dy로 작성한 후 적절히 크기를 구하고 크기를 초기화 하며 문제를 풀 수도 있었지만 신선한 아이디어가 있다면 더 쉽게 해결이 가능한 문제였죠
이번 문제를 통해서 좀더 다양한 방식으로 문제를 바라볼 수 있게 된 것 같습니다.
다음 시간에도 비슷한 문제를 해결하며 학습을 이어 나가겠습니다.