Coding 공부

def dfs(x,y,value,cnt):
    global N,M,max_value
    if cnt == 4:
        if max_value < value:
            max_value = value
        return 
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx <N and 0<= ny <M:
                if visted[nx][ny] == 0:
                    visted[nx][ny] = 1
                    dfs(nx,ny,value+arr[nx][ny],cnt+1)
                    visted[nx][ny] = 0


def check(x,y):
    global N,M,max_value
    another_matrix = [[[0,-1],[0,0],[0,1],[1,0]],
    [[0,-1],[0,0],[0,1],[-1,0]],
    [[-1,0],[1,0],[0,0],[0,1]],
    [[-1,0],[1,0],[0,0],[0,-1]]]
    for tus in another_matrix:
        flag = True
        temp = 0
        for cx,cy in tus:
            nx = x + cx
            ny = y + cy
            if 0<= nx <N and 0<= ny<M:
                temp += arr[nx][ny]
            else:
                flag = False
                break
        if flag:
            if max_value < temp:
                max_value = temp
N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,input().split())) for _ in range(N)]
visted = [[0]*M for _ in range(N)]
max_value = 0
for x in range(N):
    for y in range(M):
        visted[x][y] = 1
        dfs(x,y,arr[x][y],1)
        visted[x][y] = 0
        check(x,y)


print(max_value)

BFS가 아니라 DFS를 이용해서 해야한다. DFS를 이용해서 하면, ㅗ 모양을 제외하고는 전부 추적이 가능하다.

그 부분만 따로 검증하면 된다. 길이가 3일때 검증하면 된다.

import sys
def dfs(x,y,result,total):
    global N,M,max_value
    if visited[x][y]:
        return
    if len(total) == 4:
        if max_value < result:
            max_value = result
        return
    visited[x][y] = 1
    for i in range(3):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < N and 0 <= ny <M:
            if not visited[nx][ny]:
                dfs(nx,ny,result+arr[nx][ny],total+[(nx,ny)])
    if len(total) == 3:
        center_x,center_y = total[1]
        for i in range(4):
            nx = center_x + dx[i]
            ny = center_y + dy[i]
            if 0<= nx < N and 0 <=ny<M:
                if not visited[nx][ny]:
                    dfs(nx,ny,result+arr[nx][ny],total+[(nx,ny)])
    visited[x][y] = 0
    return



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

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


arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
max_value = 0
for x in range(N):
    for y in range(M):
        dfs(x,y,arr[x][y],[(x,y)])
print(max_value)

이게 좀 더 깔끔한 코드이다.

def dfs(N):
    stack = [1]
    visted = [0]*(N+1)
    cnt = 0
    visted[1] = 1
    while stack:
        num = stack.pop()
        cnt += 1
        for ind in graph[num]:
            if not visted[ind]:
                visted[ind] = 1
                stack.append(ind)
    return cnt - 1

N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)


print(dfs(N))

기본적인 DFS였다. 방향성이 없기 때문에, graph라는 리스트에 양방향으로 전부 저장시켜주고, 방문을 표시해준뒤, 1번 컴퓨터에 연결된 모든 노드들을 찾아주면 된다.