https://www.acmicpc.net/problem/14500
DFS, BFS로 4칸 탐색한다고 생각하고 접근했다가 실패했다.
다음 모양은 방문했던 곳으로 돌아와야 한다.
대각선 방향도 가능하도록 하되, 접하는 방문한 영역이 존재해야한다는 부분에 착안해서 DFS, BFS의 틀을 유지하면서 코드를 추가했다. 이때, python으로는 시간초과가 나서 pypy로 제출했다.
+) 어떨때 global 필요한지 조사 필요
=> 팁 아티클에 작성완료
def is_valid(x,y):
if 0<=x<N and 0<=y<M and not visited[x][y]:
return True
return False
def dfs(x,y,cnt,cum_sum):
global max_sum # 값의 변경이 필요하므로
if cnt == 4:
max_sum = max(max_sum, cum_sum)
return
for dx, dy in direction:
new_x,new_y = x+dx, y+dy
if is_valid(new_x, new_y):
visited[new_x][new_y]=True
dfs(new_x, new_y, cnt+1, cum_sum+paper[new_x][new_y])
direction = [(0,1),(1,0),(0,-1),(-1,0)]
N, M = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(N)]
max_sum = -float('inf')
for i in range(N):
for j in range(M):
visited = [[False]*M for _ in range(N)] # 방문여부 초기화
visited[i][j] = True
dfs(i,j,1,paper[i][j])
print(max_sum)
import sys
input=sys.stdin.readline
def is_valid(x,y):
if 0<=x<N and 0<=y<M and not visited[x][y]:
return True
return False
def is_valid_diag(x,y): # 이동할 곳 x,y기준 붙어있는 곳 하나 있어야 됨
if 0<=x<N and 0<=y<M and not visited[x][y]:
for dx, dy in direction:
if 0<=x+dx<N and 0<=y+dy<M and visited[x+dx][y+dy]:
return True
return False
def dfs(x,y,cnt,cum_sum):
global max_sum # 값의 변경이 필요하므로
if cnt == 4:
max_sum = max(max_sum, cum_sum)
return
for dx, dy in direction: # 수평, 수직 이동
new_x,new_y = x+dx, y+dy
if is_valid(new_x, new_y):
visited[new_x][new_y]=True # 다른 DFS의 visited에도 영향을 미친다
dfs(new_x, new_y, cnt+1, cum_sum+paper[new_x][new_y])
visited[new_x][new_y]=False # 다시 False로 둬야 다른 DFS에 영향 안미친다
for dx, dy in diagonal: # 대각선 이동
new_x, new_y = x+dx, y+dy
if is_valid_diag(new_x,new_y):
visited[new_x][new_y]=True
dfs(new_x, new_y, cnt+1, cum_sum+paper[new_x][new_y])
visited[new_x][new_y]=False
direction = [(0,1),(1,0),(0,-1),(-1,0)] # 수직, 수평 방향
diagonal = [(1,1),(-1,-1),(1,-1),(-1,1)] # 대각선 방향
N, M = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(N)]
max_sum = -float('inf')
visited = [[False]*M for _ in range(N)] # 방문여부 초기화 1번만
for i in range(N):
for j in range(M):
visited[i][j] = True
dfs(i,j,1,paper[i][j])
visited[i][j] = False # 매번 초기화하는대신 여기서 다시 원복
print(max_sum)