문제

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

코드

n,m=map(int,input().split())

graph=[list(map(int,input().split())) for _ in range(n)]
visited=[[False]*m for _ in range(n)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
ans=0

def dfs(x,y,d,total):
    global ans

    if d ==4:
        ans=max(ans,total)
        return

    elif d<4:
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
                if d == 2:
                    visited[nx][ny]=True
                    dfs(x,y,d+1,total+graph[nx][ny])
                    visited[nx][ny]=False

                visited[nx][ny]=True
                dfs(nx,ny,d+1,total+graph[nx][ny])
                visited[nx][ny]=False

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

print(ans)

• 브루트 포스 dfs문제이다.

• 위와 같은 모양의 4칸으로 탐색하여 최대값을 구하는 문제이다.

• 모양대로 탐색하기위해 재귀를 통해 방문을 초기화할 수 있는 dfs가 bfs보다 적합하여 dfs로 구현했다.

• 하나씩 graph를 탐색하면서 dfs로 각 모양의 회전의 경우까지 탐색하여 최대값을 구한다.

• 가장어려운부분은 ㅗ 모양이였다. 해당 부분을 해결하기위해

if d == 2:
                    visited[nx][ny]=True
                    dfs(x,y,d+1,total+graph[nx][ny])
                    visited[nx][ny]=False

이부분을 사용하여 해결했다.

이 와같은 방식으로 현재 위치에서 다음으로 방문할 부분 (nx,ny)를 방문한것처럼한 후 x,y이전에 나머지 주위의 2칸을 탐색하는 방법이다.

참고

https://velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-14500-%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8