[백준/BOJ] - 14500번 python 풀이 - dfs

---

다음 이미지 형태의 도형에 부합하는 값들의 합 - 최댓값을 도출하는 문제이다.

순간 이 문제를 봤을 때 dfs를 활용하면 될 거 같다는 생각이 들었다.

 

하지만 코드를 완전히 작성하고 난 후, 테스트 케이스를 돌려보니 기댓값과 다른 값이 출력되었다.

 

문제를 생각해보니,'ㅜ' 모양의 도형은 단순 dfs로는 해결이 안되는 것. 

나머지 도형의 유형은 모두 dfs로 해결 되지만, 유일하게 'ㅜ' 모양만 체크가 불가하다.

 

이를 해결하기 위해 새로운 함수를 만들어 'ㅜ' 모양만 예외처리 해주었다.

 

반복문을 활용한다고 가정했을 때, 총 나올 수 있는 형태는 4가지. ㅗ, ㅏ , ㅜ ㅓ 이다.

기준점 하나를 잡았으면, 해당 기준점 당 4가지의 경우의 수가 나올 수 있다는 점.

또한, 각 도형의 모형 별로 반복문 3번을 돌려 기준점 옆에 있는 곳에 도달하여 해당하는 배열 속 값을 더해주어야 한다.

 

즉, 바깥 반복문 4번, 내부 반복문 3번이 필요하다.

 

두 반복문의 변수를 더해 4로 나눠 3 미만의 나머지가 남게 하고

dx, dy = (-1,1,0,0), (0,0,-1,1)

동서남북의 지표인 dx,dy를 뽑는 idx로써 활용.

 

나머지 경우는 간단한 dfs를 활용하면 해결 가능하므로 생략.

---

import sys
input = sys.stdin.readline
m, n = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(m)]
dx, dy = (-1,1,0,0), (0,0,-1,1)
ok = [[False] * n for _ in range(m)]
maxi = 0

def dfs(a,b,val,step):        
    if step == 4:
        global maxi
        maxi = max(maxi,val)
        return
        
    for i in range(4):
        rx = a + dx[i]
        ry = b + dy[i]
        if 0<=rx<m and 0<=ry<n:
            if ok[rx][ry] == False:
                ok[rx][ry] = True #방문처리
                dfs(rx,ry,val+arr[rx][ry],step+1)
                ok[rx][ry] = False #원상 복구
def exec(a,b):
    global maxi
    for i in range(4): #4가지 조합(ㅗ 모양)
        tmp = arr[a][b]
        for j in range(3): #뽑아야 하는 것 3가지
            t = (i+j)%4
            rx = a + dx[t]
            ry = b + dy[t]
            if not (0<=rx<m and 0<=ry<n):
                tmp = 0                
                break
            tmp+=arr[rx][ry]        
        maxi = max(maxi,tmp)

for i in range(m):
    for j in range(n):
        ok[i][j] = True #방문처리
        dfs(i,j,arr[i][j],1)    
        ok[i][j] = False  
        exec(i,j)  
print(maxi)

---

---