[백준 14500번] 테트로미노 - 파이썬

문제 링크:

 

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

14500번: 테트로미노

 

백준 14500번 테트로미노 문제는 삼성 SW 역량테스트 기출문제이다.

 

테트로미노

 

---

풀이 유형:

구현, 브루트 포스(완전 탐색) 알고리즘, DFS 

 

풀이 과정 1

<브루트 포스(완전 탐색)로만 이용>

1. 테트로미노 모양은 5가지가 있다. 이 모양에 해당하는 함수들을 모두 만들어 계산한다.

2. 모양에 따라 회전하는 함수와 대칭하는 함수 2개를 모두 만들어야 하기 때문에 코드가 매우 길어진다.

3. 필자는 DFS방식을 이용하지 않고 브루트 포스, 구현으로 문제를 풀었다. 코드가 약 280줄이 나왔기에 파이썬에는 시간 초과가 뜨고, PyPy3에서는 Pass 되었다.

4. 조금 더 간단하게 푸는 방법은 밑에 있는 DFS 설명을 보자.

 

참고) 간단한 코드상에서는 Python3가 메모리, 속도 측에서 우세, 복잡한 코드(반복)를 사용하는 경우에서는 PyPy3가 우세한다.

 

(문제 푸는데 몇 시간이 걸렸다... 하지만 풀어서 행복하다!!

앞으로도 연습 많이 해야겠다)

 

 

풀이 코드:

 

# 14500번 테트로미노

# 방향체크 함수 생성
# 회전, 대칭하는 함수 생성
# 제일 왼쪽에 있는 숫자를 기준으로 모든 숫자 반복문 실행하며 수들의 합 구하기

from sys import stdin

# 종이의 세로 크기와 가로 크기 입력받기
n, m = map(int, stdin.readline().rstrip().split())

# 종이에 있는 데이터 리스트 생성
data = []

# 숫자를 한 행씩 입력받기
for _ in range(n):
  data.append(list(map(int, stdin.readline().split())))

# 현재 가리키고 있는 방향
direction = 0

# 북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 오른쪽방향으로 90도 돌기
def turn_right():
  global direction
  direction += 1
  if direction == 4:
    direction = 0

# 테트로미노를 나타내는 함수 

# 1. 4x1 모양
def get_tetro_1(nx, ny):
  global direction
  cnt1 = 0
  # 테트로미노 모양 생성
  for _ in range(4):
      # 종이에 이탈하면 0으로 초기화
    if nx < 0 or ny < 0 or nx >= n or ny >= m:
      cnt1 = 0
      return cnt1
    cnt1 += data[nx][ny]
    nx += dx[direction]
    ny += dy[direction]
  
  return cnt1

  
# 2. 2x2 모양
def get_tetro_2(nx, ny):
  cnt2 = 0
  # 종이를 이탈하면 0을 반환
  if nx < 0 or ny < 0 or nx+1 >= n or ny+1 >= m:
    return cnt2
  cnt2 += data[nx][ny]
  cnt2 += data[nx][ny+1]
  cnt2 += data[nx+1][ny]
  cnt2 += data[nx+1][ny+1]
  return cnt2


# 3. L자모양
def get_tetro_3(nx, ny):
  global direction
  cnt3 = 0

  # 기존 모양대로 회전
  for _ in range(3):
    # 종이를 이탈하면 0으로 반환
    if nx < 0 or ny < 0 or nx >= n or ny >= m:
      cnt3 = 0
      return cnt3
    cnt3 += data[nx][ny]
    nx += dx[direction]
    ny += dy[direction]
  # 마지막 이동한 위치로 이동  
  nx -= dx[direction]
  ny -= dy[direction]
  # 이동 방향 설정
  if direction != 0:
    direction -= 1
  else:
    direction = 3
  # 이동할 좌표 설정
  nx += dx[direction]
  ny += dy[direction]
  # 종이를 이탈하면 0을 반환
  if nx < 0 or ny < 0 or nx >= n or ny >= m:
    cnt3 = 0
    return cnt3
  # 이동하기
  cnt3 += data[nx][ny]
  return cnt3


# 3-1. L자대칭 모양
def sym_tetro_3(sym_nx, sym_ny):
  global direction
  sym_cnt3 = 0

  # 대칭모양 회전
  for _ in range(3):
    # 종이를 이탈하면 0을 반환
    if sym_nx < 0 or sym_ny < 0 or sym_nx >= n or sym_ny >= m:
      sym_cnt3 = 0
      return sym_cnt3     
    sym_cnt3 += data[sym_nx][sym_ny]
    sym_nx += dx[direction]
    sym_ny += dy[direction]
  # 마지막 이동한 위치로 이동  
  sym_nx -= dx[direction]
  sym_ny -= dy[direction]   
  # 이동 방향 설정
  if direction != 3:
    direction += 1
  else:
    direction = 0
  # 이동할 좌표 설정
  sym_nx += dx[direction]
  sym_ny += dy[direction]
  # 이동시 종이를 이탈하면 0을 반환
  if sym_nx < 0 or sym_ny < 0 or sym_nx >= n or sym_ny >= m:
    sym_cnt3 = 0
    return sym_cnt3
  # 이동하기
  sym_cnt3 += data[sym_nx][sym_ny]
  return sym_cnt3


# 4. 지그재그 모양
def get_tetro_4(nx, ny):
  global direction
  cnt4 = 0
  # 현재 위치 값 저장 
  cnt4 += data[nx][ny]
  # 이동할 좌표 설정
  nx += dx[direction]
  ny += dy[direction]
  # 종이를 이탈하면 0을 반환
  if nx < 0 or ny < 0 or nx >= n or ny >= m:
    cnt4 = 0
    return cnt4
  # 이동하기
  cnt4 += data[nx][ny]
  # 방향 바꾸기
  if direction != 0:
    direction -= 1
  else:
    direction = 3
  # 이동할 좌표 설정
  nx += dx[direction]
  ny += dy[direction]
  # 종이를 이탈하면 0을 반환
  if nx < 0 or ny < 0 or nx >= n or ny >= m:
    cnt4 = 0
    return cnt4
  # 이동하기
  cnt4 += data[nx][ny]
  # 방향 바꾸기
  if direction != 3:
    direction += 1
  else:
    direction = 0
  # 이동할 좌표 설정
  nx += dx[direction]
  ny += dy[direction]
  # 종이를 이탈하면 0을 반환
  if nx < 0 or ny < 0 or nx >= n or ny >= m:
    cnt4 = 0
    return cnt4
  cnt4 += data[nx][ny]
  return cnt4

# 4-1 지그재그 대칭 모양
def sym_tetro_4(nx, ny):
  global direction
  sym_cnt4 = 0
  # 현재 위치 값 저장 
  sym_cnt4 += data[nx][ny]
  # 이동할 좌표 설정
  nx += dx[direction]
  ny += dy[direction]
  # 종이를 이탈하면 0을 반환
  if nx < 0 or ny < 0 or nx >= n or ny >= m:
    sym_cnt4 = 0
    return sym_cnt4
  # 이동하기
  sym_cnt4 += data[nx][ny]
  # 방향 바꾸기
  if direction != 3:
    direction += 1
  else:
    direction = 0
  # 이동할 좌표 설정
  nx += dx[direction]
  ny += dy[direction]
  # 종이를 이탈하면 0을 반환
  if nx < 0 or ny < 0 or nx >= n or ny >= m:
    sym_cnt4 = 0
    return sym_cnt4
  # 이동하기
  sym_cnt4 += data[nx][ny]
  # 방향 바꾸기
  if direction != 0:
    direction -= 1
  else:
    direction = 3
  # 이동할 좌표 설정
  nx += dx[direction]
  ny += dy[direction]
  # 종이를 이탈하면 0을 반환
  if nx < 0 or ny < 0 or nx >= n or ny >= m:
    sym_cnt4 = 0
    return sym_cnt4
  sym_cnt4 += data[nx][ny]
  return sym_cnt4


# 5. ㅜ, ㅗ, ㅓ, ㅏ 모양
def get_tetro_5(nx,ny):
  global direction
  cnt5 = 0
  # 이동하기
  for _ in range(3):
    # 종이를 이탈하면 0을 반환
    if nx < 0 or ny < 0 or nx >= n or ny >= m:
      cnt5 = 0
      return cnt5
    cnt5 += data[nx][ny]
    nx += dx[direction]
    ny += dy[direction]
  # 가운데 위치로 이동
  for _ in range(2):
    nx -= dx[direction]
    ny -= dy[direction]
  # 방향 바꾸기
  if direction != 3:  
    direction += 1
  else:
    direction = 0
  nx += dx[direction]
  ny += dy[direction]
  # 종이를 이탈하면 0을 반환
  if nx < 0 or ny < 0 or nx >= n or ny >= m:
    cnt5 = 0
    return cnt5
  cnt5 += data[nx][ny]
  return cnt5

# 결과를 출력할 변수 생성
sum = -1e9


# 방향 북쪽으로 설정
direction = 0

# 하나의 숫자를 기준으로 테트로미노인지 확인
for i in range(n):
  for j in range(m):
    # 방향별로 돌리면서 수의 합 구하기
    for k in range(4):
      direction = k
      case1 = get_tetro_1(i, j)
      direction = k
      case2 = get_tetro_2(i, j)
      direction = k
      case3 = get_tetro_3(i, j)
      direction = k
      case3_1 = sym_tetro_3(i, j)
      direction = k
      case4 = get_tetro_4(i, j)
      direction = k
      case4_1 = sym_tetro_4(i, j)
      direction = k
      case5 = get_tetro_5(i, j)
      direction = k
      # 계산결과 중 가장 큰 테트로미노 값으로 반환
      sum = max(sum, case1, case2, case3, case3_1, case4, case4_1, case5)
      # 방향 바꾸기
      turn_right()

# 정답 출력
print(sum)

 

풀이 과정 2

<DFS, 브루트 포스(완전 탐색) 이용>

1. 테트로미노 중 'ㅗ' 모양을 가진 분홍색 테트로미노를 제외한 나머지 모양들은 DFS를 통해 구할 수 있다.

테트로미노

이는 예시로 빨간 점에서 DFS를 수행한다면 나머지 4개 모양들은 방향과 상관없이 만들 수 있다.

 

●

 

2. 'ㅗ' 모양은  idx = 1일 때(2개의 블록을 선택했을 때) 새로운 블록에서 다음 블록을 탐색하는 것이 아닌 기존 블록에서 탐색한다면 'ㅗ' 모양을 만들 수 있다.

3. 종이(2차원 배열)에서 최댓값을 찾아 max(map(max, arr)) 선택할 수 있는 남은 블록의 개수만큼 곱하고, 이를 현재 누적 합 total에 더해서 ans와 비교해준다.

 

풀이 코드:

 

import sys 
input = sys.stdin.readline

# dfs 정의
def dfs(r, c, idx, total):
  # 결과값 변수
  global ans
  # 현재의 dfs에서 남은 블록이 모두 최댓값에 해당하더라도 현재 ans를 넘기지 못한다면 조기종료
  if ans >= total + max_val * (3 - idx):
    return
  # 4개의 블록을 모두 사용했으면
  if idx == 3:
    # 현재 dfs한 값과 이전까지의 최댓값(ans)을 비교해 더 큰 값을 ans로 반환하고 종료
    ans = max(ans, total)
    return
  # 4개의 블록을 아직 다 사용하지 않았다면
  else:
    # 방향 설정
    for i in range(4):
      nr = r + dr[i]
      nc = c + dc[i]
      # 이동할려는 위치가 종이(배열)안에 있고 방문한 적이 없다면
      if 0 <= nr < N and 0 <= nc < M and visit[nr][nc] == 0:
        # 만약 2개의 볼록을 선택했다면
        if idx == 1:
          # 방문도장 찍기
          visit[nr][nc] = 1
          # 방문도장 찍은 위치에서 dfs 재귀적 호출
          dfs(r, c, idx + 1, total + arr[nr][nc])
          # 목적지를 풀어주기
          visit[nr][nc] = 0
       	# 방문도장 찍기
        visit[nr][nc] = 1
        # 방문도장 찍은 위치에서 dfs 재귀적 호출
        dfs(nr, nc, idx + 1, total + arr[nr][nc])
        # 목적지 풀어주기
        visit[nr][nc] = 0

# 입력받기
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visit = [([0] * M) for _ in range(N)]

# 좌표 이동거리 행, 열 입력받기
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
ans = 0
# 종이 중에 가장 큰 값
max_val = max(map(max, arr))

# 종이에 있는 숫자를 하나씩 입력받아
for r in range(N):
  for c in range(M):
    # 방문도장 찍기
    visit[r][c] = 1
    # dfs 호출하여 ans 최댓값 구하기
    dfs(r, c, 0, arr[r][c])
    # 목적지 해제
    visit[r][c] = 0

# 정답 출력
print(ans)

 

 

14500번 테트로미노