Search

[백준 14500] 테트로미노

[백준 14500] 테트로미노

Tip

도형의 회전과 대칭함수를 구현하여 모든 경우의 수를 따져가며 종이를 완전탐색할 순 있지만,,
DFS로 접근하는 것이 훨씬 간편!
DFS(깊이 우선 탐색)?
테트로미노는 정사각형을 4개를 이어 붙인 도형이므로, 시작 위치의 count값을 1로 했을 때, count가 4가 될 때까지 탐색을 수행한 경로로 표현 가능
단, ㅜ ㅗ ㅓ ㅏ 모양은 일반적인 DFS로 표현할 수 없으므로 반례 처리가 필요
종이의 적힌 수 중 최댓값을 구해 놓고, 이를 활용하면 효율적인 탐색 수행이 가능 (코드 참고)

풀이 소스 코드

import sys si = sys.stdin.readline n, m = map(int, si().split()) paper = [list(map(int, si().split())) for _ in range(n)] visited = [[False] * m for _ in range(n)] # 상하좌우 탐색에 사용할 방향 인덱스 배열 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] # 종이에서 가장 큰 값 max_val = max(map(max, paper)) # 결과값을 저장할 변수 result = 0 # DFS 함수 def dfs(x, y, cnt, total): global result # 남은 탐색 지점을 모두 최댓값으로 해도 현재까지의 result보다 작으면 해당 탐색은 조기종료 if result >= total + max_val * (4 - cnt): return # 4개의 정사각형을 모두 사용했다면 if cnt == 4: result = max(result, total) # result값 갱신 else: # 아직 4개의 정사각형을 다 사용못한 경우 for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == False: # ㅜ, ㅗ, ㅏ, ㅓ 모양을 만들기 위한 반례 처리 if cnt == 2: visited[nx][ny] = True # nx, ny 좌표는 방문 처리만 하고 dfs(x, y, cnt + 1, total + paper[nx][ny]) # x, y에서 다시 탐색 수행 visited[nx][ny] = False visited[nx][ny] = True dfs(nx, ny, cnt + 1, total + paper[nx][ny]) visited[nx][ny] = False # 종이 2차원 배열 모든 요소에서 DFS 수행 for i in range(n): for j in range(m): visited[i][j] = True dfs(i, j, 1, paper[i][j]) visited[i][j] = False print(result)
Python