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

solved.ac 난이도 :  GOLD5

백준   14500번- 파이썬 풀이

 

<문제>

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

14500번: 테트로미노

<풀이>-구현,브루트포스,DFS

위와 같은 도형 다섯가지가 있을때 보라색을 제외하곤 전부 DFS를 통해 구현할 수 있다.

DFS를 통해 회전 또는 대칭을 이룰수있는 각각의 모양을 전부 만들 수 있다.

 

-DFS 알고리즘-

 

우선 매개변수로 현재 그래프의 위치, 합, dfs횟수를 설정한다.(dfs(i,j,sum,cnt) 이때 dfs의 cnt가 4가 되는순간 재귀호출을 중단하고 합을 계산한다.

 

시작점의 위치(i,j)에서 상하좌우로 이동가능한 지역을 살펴본다. 이때 중복을 피하기 위해 visitied배열을 사용한다.

만약 상하좌우에 이동가능한 지역이 있고 visitied배열에도 미방문으로 되어있다면 그 위치에서 dfs함수를 호출한다.

 

이때, 중요한것은 dfs의 sum 매개변수의 이동한위치의 값을 더해주고 cnt+1을 해주는 것이다.

 

그리고 dfs호출이 끝나면 방문했던 지역은 다음 도형을 위해 다시 미방문으로 바꿔준다.

answer= 0
def dfs(i,j,sum,cnt):
    global answer
    
    if cnt == 4:
        answer = max(answer,sum)
        return
    
    for a in range(4):
        ni = i+dx[a]
        nj = j+dy[a]
        if 0<=ni<n and 0<=nj<m and not visitied[ni][nj]:
            visitied[ni][nj] = True
            dfs(ni,nj,sum+graph[ni][nj],cnt+1)
            visitied[ni][nj] = False

-'ㅗ'모양의 도형-

테트로미노중에서 'ㅗ','ㅜ','ㅓ','ㅏ' 이렇게 생긴 도형을 찾을 수 있다. 이와 같은 도형은 일자로 이을수가 없어 dfs를 활용하지는 못한다. 

 

도형중에서 튀어나온부분의 바로 밑부분을 기준으로 두고 앞, 좌, 우 방향의 원소의 합을 구해야한다.

 

튀어나온부분이 어디냐에 따라 앞,좌,우로 향하는 방향이 달라질수 있다.

 

예를 들면 'ㅗ','ㅜ'도형을 살펴보자

 

위 설명대로 하기 위해선 'ㅗ' 도형은 상,좌,우방향으로 움직여 합을 구해야한다.

반면 'ㅜ'도형은 앞,좌,우 의 합을 구하기 위해 하,좌,우방향으로 움직여야 한다.

 

따라서 dx,dy배열을 반복문을 통해 돌릴때 각 기준점의 위치에서 움직여야 하는 방향에 해당하는 인덱스로 돌도록 해야한다.

dx,dy = [-1,1,0,0],[0,0,-1,1](상하좌우)일때 'ㅗ'도형이라면 상,좌,우 방향이 필요하므로 dx,dy배열의 0,2,3인덱스만 반영되도록 반복문을 작성해야한다는 것이다.

#상하좌우
dx,dy = [-1,1,0,0],[0,0,-1,1]

def middle(i,j):
    global answer
    for a in range(4): #a는 기준점의 위치
        result = graph[i][j]
        for k in range(3):
            t = (a+k)%4  #기준점이 a일때 움직여야하는 인덱스
            ni = i+dx[t]
            nj = j+dy[t]
            if not(0<=ni<n and 0<=nj<m):
                result = 0
                break
            result+=graph[ni][nj]
        answer = max(answer,result)

728x90

<코드>-파이썬

import sys

n,m = map(int,sys.stdin.readline().split())
#상하좌우
dx,dy = [-1,1,0,0],[0,0,-1,1]
graph = []
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))
visitied = [[False]*m for _ in range(n)]
answer = 0
def dfs(i,j,sum,cnt):
    global answer
    if cnt == 4:
        answer = max(answer,sum)
        return
    
    for a in range(4):
        ni = i+dx[a]
        nj = j+dy[a]
        if 0<=ni<n and 0<=nj<m and not visitied[ni][nj]:
            visitied[ni][nj] = True
            dfs(ni,nj,sum+graph[ni][nj],cnt+1)
            visitied[ni][nj] = False
            
def middle(i,j):
    global answer
    for a in range(4):
        result = graph[i][j]
        for k in range(3):
            t = (a+k)%4
            ni = i+dx[t]
            nj = j+dy[t]
            if not(0<=ni<n and 0<=nj<m):
                result = 0
                break
            result+=graph[ni][nj]
        answer = max(answer,result)

for i in range(n):
    for j in range(m):
        visitied[i][j] = True
        dfs(i,j,graph[i][j],1)
        visitied[i][j] = False

        middle(i,j)

print(answer)

-마치며-

이 문제는 최근에 풀었던 문제들 중 가장 어려웠던 문제 같다. 이 문제를 보면서 혼자 생각할때 DFS를 사용해야한다는 생각이 하나도 들지 않았기 때문이다. 이렇게 감도 못잡았던 문제는 정말 오랜만이었던거 같다. 그동안 공부를 하면서 다양한 유형을 풀지 못했다는 생각도 들었다.