110. [삼성기출6] Python 백준 14500 번 테트로미노 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 14500 번 테트로미노 입니다.

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

14500번: 테트로미노

 

먼저 백준 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 코드였습니다.

감사합니다.