110. [삼성기출6] Python 백준 14500 번 테트로미노 자세한 설명
안녕하세요 코딩하는 덕구입니다.
백준 14500 번 테트로미노 입니다.
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
먼저 백준 14500 번 테트로미노 파이썬 정답 코드입니다. 설명은 아래에 있습니다.
N, M = map(int, input().split())
paper = []
dir_x = [-1, 1, 0, 0] #세로축 상, 하, 좌, 우
dir_y = [0, 0, -1, 1] #가로축
visited = [[False for _ in range(M)]for _ in range(N)]
for _ in range(N):
paper.append(list(map(int, input().split())))
max_val = max(map(max, paper))
def DFS(x, y, cnt, total):
global ans
if ans >= total + max_val*(3 - cnt):
return
if cnt == 3:
ans = max(ans, total)
return
for i in range(4):
nx = x + dir_x[i]
ny = y + dir_y[i]
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
if cnt == 1:
visited[nx][ny] = True
DFS(x, y, cnt + 1, total + paper[nx][ny])
visited[nx][ny] = False
visited[nx][ny] = True
DFS(nx, ny, cnt + 1, total + paper[nx][ny])
visited[nx][ny] = False
ans = 0
for i in range(N):
for j in range(M):
visited[i][j] = True
DFS(i, j, 0, paper[i][j])
visited[i][j] = False
print(ans)
문제 요약

NxM 크기의 종이가 있고, 종이는 1x1 사이즈의 칸으로 나누어져 있으며, 각 칸마다 서로 다른 숫자가 있습니다.
도형 중 하나를 적절히 놓아서 도형이 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성합니다.
문제 접근
도형들을 구현하는게 핵심입니다.
한 붓그리기, 즉 모든 점들을 한번씩만 이동하여 그릴 수 있는 도형은 dfs 로 구현이 가능합니다.
그럼 분홍색 도형을 제외한 모든 도형은 dfs 로 구현하고,
분홍색 도형은 dfs가 0, 1, 2, 3 순으로 탐색할때
2번 iteration째에 1번의 좌표에서 dfs를 진행하면 구현할 수 있습니다.
이런식으로요!
if cnt == 1:
visited[nx][ny] = True
DFS(x, y, cnt + 1, total + paper[nx][ny])
visited[nx][ny] = False
visited[nx][ny] = True
DFS(nx, ny, cnt + 1, total + paper[nx][ny])
visited[nx][ny] = False
Python 코드 구현
종이의 세로 N, 가로 M , 종이 paper, 탐색을 위한 dir_x, dir_y, visited를 구현해 줍니다.
N, M = map(int, input().split())
paper = []
dir_x = [-1, 1, 0, 0] #세로축 상, 하, 좌, 우
dir_y = [0, 0, -1, 1] #가로축
visited = [[False for _ in range(M)]for _ in range(N)]
종이의 정보를 받아 종이의 각 좌표에 저장하고,
프로그램의 동작속도 효율을 의해 가장 큰 값을 찾아 저장합니다.
for _ in range(N):
paper.append(list(map(int, input().split())))
max_val = max(map(max, paper))
좌표를 입력받아
해당 좌표에 모든 도형을 가능한 모든 방향으로 놓아서 도형안의 값을 더하고,
그 중 가장 큰 값을 출력하는 함수인 dfs 를 구현해봅시다.
def DFS(x, y, cnt, total):
가장 도형안의 숫자 합 중 가장 큰 숫자를 저장한 변수인 ans를 전역변수로 설정하고
불 필요한 동작을 줄이기 위해
남은 탐색 동안 가능한 큰 수가 들어와도 현재의 최대값을 넘을 수 없으면
해당 탐색은 종료합니다.
global ans
if ans >= total + max_val*(3 - cnt):
return
한 도형을 모두 탐색했다면 해당 도형안의 모든 숫자들의 합과 지금까지 가장 큰 숫자를 비교해서 더 큰 숫자를
지금까지 가장 큰 숫자를 저장하는 변수인 ans 에 저장합니다.
if cnt == 3:
ans = max(ans, total)
return
4가지 방향으로 dfs 를 동작시키는데
탐색할 다음 좌표가 그래프 안에 있을때, 아직 노드를 방문하지 않았을 때 dfs를 동작시키고,
for i in range(4):
nx = x + dir_x[i]
ny = y + dir_y[i]
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
cnt가 1이면 (도형의 4개 정사각형 중 3번째 탐색이라면) 2가지로 dfs를 동작시킵니다.
1.
O O O 이 위치에서 (굵은 원) 다음 dfs를 진행할 때 이전 좌표(nx, ny가 아닌 x, y)에서 진행하게 되면 방문한 곳은 방문하지 않으므로
1
O O O 1번이나 2번으로 이동하게 되고, ㅗ, ㅜ, ㅏ, ㅓ 모양을 구현할 수 있습니다.
2
if cnt == 1:
visited[nx][ny] = True
DFS(x, y, cnt + 1, total + paper[nx][ny])
visited[nx][ny] = False
2. dfs를 그냥 동작시키면 한붓그리기로 그릴 수 있는 모든 도형이 나오므로,
2가지의 dfs동작으로 모든 폴리오미노를 구현 가능합니다.
visited[nx][ny] = True
DFS(nx, ny, cnt + 1, total + paper[nx][ny])
visited[nx][ny] = False
함수 구현이 끝났습니다.
이제 모든 좌표에 대해 모든 도형을 대보면서
도형안의 숫자들의 합이 가장 큰 경우를 찾고
ans = 0
for i in range(N):
for j in range(M):
visited[i][j] = True
DFS(i, j, 0, paper[i][j])
visited[i][j] = False
출력하면 됩니다.
print(ans)
파이썬 백준 14500 번 테트로미노 최종 코드입니다.
N, M = map(int, input().split())
paper = []
dir_x = [-1, 1, 0, 0] #세로축 상, 하, 좌, 우
dir_y = [0, 0, -1, 1] #가로축
visited = [[False for _ in range(M)]for _ in range(N)]
for _ in range(N):
paper.append(list(map(int, input().split())))
max_val = max(map(max, paper))
def DFS(x, y, cnt, total):
global ans
if ans >= total + max_val*(3 - cnt):
return
if cnt == 3:
ans = max(ans, total)
return
for i in range(4):
nx = x + dir_x[i]
ny = y + dir_y[i]
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
if cnt == 1:
visited[nx][ny] = True
DFS(x, y, cnt + 1, total + paper[nx][ny])
visited[nx][ny] = False
visited[nx][ny] = True
DFS(nx, ny, cnt + 1, total + paper[nx][ny])
visited[nx][ny] = False
ans = 0
for i in range(N):
for j in range(M):
visited[i][j] = True
DFS(i, j, 0, paper[i][j])
visited[i][j] = False
print(ans)
백준 14500 번 테트로미노 자세한 설명 및 Python 코드였습니다.
감사합니다.