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

---

소스코드 (틀린풀이)

from collections import deque

N,M = map(int,input().split())

tetro = []

for i in range(N):

  tetro.append(list(map(int,input().split())))

dx = [-1,1,0,0]

dy = [0,0,-1,1]

def bfs(x,y):

  queue = deque()

  queue.append((x,y))       #시작 지점 queue에 삽입

  SUM = tetro[x][y]

  Max_place = ()

  visited = [(x,y)]

  for _ in range (3):       #테트로미노는 자기포함 4번 움직임

    poly = queue.popleft()

    Max = 0

    nlist = []

    for i in range(4):      #상하좌우 탐색해서 최대값 찾기

      nx = poly[0] + dx[i]

      ny = poly[1] + dy[i]

      if (nx < 0) or (nx>=N)or (ny<0)or (ny>=M) or ((nx,ny) in visited):

        continue

      if tetro[nx][ny] >= Max:

        Max = tetro[nx][ny]   #최대 값

        Max_place = (nx,ny)   #최대 값의 좌표

    visited.append(Max_place)

    SUM += Max

    queue.append(Max_place)

  

  Sum_o = tetro[x][y]

  for i in range(4):      #ㅗ,ㅓ,ㅏ,ㅜ

    nx = x + dx[i]

    ny = y + dy[i]

    if (nx < 0) or (nx>=N)or (ny<0)or (ny>=M):

      continue

    nlist.append(tetro[nx][ny])

  if len(nlist) == 3:

    Sum_o += sum(nlist)

  if len(nlist) == 4:

    nlist.remove(min(nlist))

    Sum_o += sum(nlist)

  return max(SUM,Sum_o)

ans = 0

for i in range (N):

  for j in range (M):

    if bfs(i,j) >= ans :

      ans = bfs(i,j)

print(ans)

알고리즘

1. ㅗ,ㅓ,ㅏ,ㅜ는  한붓그리기가 안되는 애들이므로 따로 구현을 해줘야 했다.

2. 틀린이유

테스트케이스 80%까지 갔다가 틀린 코드이다. 다른 사람들의 코드를 보고 왜 틀렸는지 알게 되었는데

미로찾기 알고리즘 처럼 시작점을 기준으로 상하좌우 중 가장 큰애들을 따라가며 더하는 알고리즘을 짯는데

그러면 안되고 빈 list를 선언해서 방문한 애들의 좌표값을 true로 바꾸고 모양이 완성되면 true인 애들의 합의 최대를 return하는 알고리즘을 짜야했다.   

 

---

소스코드 (맞는풀이)

import sys

input = sys.stdin.readline

# 상, 하, 좌, 우

move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# INPUT

N, M = map(int, input().split())

board = [list(map(int,input().split())) for _ in range(N)]

visited = [[False] * M for _ in range(N)]

# 최대값 변수

maxValue = 0

# ㅗ, ㅜ, ㅓ, ㅏ 제외한 모양들 최대값 계산

def dfs(i, j, dsum, cnt):

    global maxValue

    # 모양 완성되었을 때 최대값 계산

    if cnt == 4:

        maxValue = max(maxValue, dsum)

        return

    # 상, 하, 좌, 우로 이동

    for n in range(4):

        ni = i+move[n][0]

        nj = j+move[n][1]

        if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj]:

            # 방문 표시 및 제거

            visited[ni][nj] = True

            dfs(ni, nj, dsum + board[ni][nj], cnt+1)

            visited[ni][nj] = False

# ㅗ, ㅜ, ㅓ, ㅏ 모양의 최대값 계산

def exce(i, j):

    global maxValue

    for n in range(4):

        # 초기값은 시작지점의 값으로 지정

        tmp = board[i][j]

        for k in range(3):

            # move 배열의 요소를 3개씩 사용할 수 있도록 인덱스 계산

            # 012, 123, 230, 301

            t = (n+k)%4

            ni = i+move[t][0]

            nj = j+move[t][1]

            if not (0 <= ni < N and 0 <= nj < M):

                tmp = 0

                break

            tmp += board[ni][nj]

        # 최대값 계산

        maxValue = max(maxValue, tmp)

for i in range(N):

    for j in range(M):

        # 시작점 visited 표시

        visited[i][j] = True

        dfs(i, j, board[i][j], 1)

        visited[i][j] = False

        exce(i, j)

print(maxValue)