글 읽기 - 14500번 시간초과 관련 질문

wonderkyum21 2년 전 0

안녕하세요~ 빠큐 모양을 제외한 모든 모양을 dfs로 접근하고, 빠큐만 일일이 돌면서 수행하는 코드를 작성해서 제출햇는데

시간초과가 떴습니다 (사실 trace 부분에 append하는 것과 pop 때문에 쓸데없는 시간이 소요된다고 생각이 들긴 합니다..)

근데 제가 생각한 부분 이외에도 혹시 시간을 더 단축시킬 수 있는 부분이 있을까요??

고수님들의 조언 구합니다!

+ 그리고 미천한 제 머리로는 trace를 파악하지 않고 4칸짜리 블럭이 될때마다 최대값을 어떻게 체크해야할 지 모르겠는데 이 부분 관련해서도 조언해주시면 감사하겠습니다~~

# 14500
import copy
import sys
sys.setrecursionlimit(100000)

# ㅗ 모양을 제외한 모든 모양 검색 가능!!
def dfs(i, j):	
	global answer
	if i < 0 or i >= n or \
		j < 0 or j >= m or \
		temp_graph[i][j] == -1 or len(trace) == 4:
			return

	# print(temp_graph[i][j])
	# print(temp_graph)
	# print(trace)

	trace.append(temp_graph[i][j])
	temp_graph[i][j] = -1

	if len(trace) == 4:
		answer = max(answer, sum(trace))
		
	# 동서남북
	dfs(i - 1, j)
	dfs(i, j - 1)
	dfs(i + 1, j)
	dfs(i, j + 1)

	temp_graph[i][j] = trace[-1]
	trace.pop()
	

n, m = map(int, input().split())
trace = []
graph = []
answer = 0
for _ in range(n):
	graph.append(list(map(int, input().split())))

# print(graph)
for r in range(n):
	for c in range(m):
		temp_graph = copy.deepcopy(graph)
		dfs(r, c)

# ㅗ 모양 brute force => ㅗ, ㅏ, ㅜ, ㅓ		
for r in range(n):
	for c in range(m):
		try:
			answer = max(answer, graph[i][j - 1] + graph[i][j] + graph[i][j + 1] + graph[i - 1][j]) # ㅗ
		except:
			pass
		
		try:
			# print(graph[r - 1][c], graph[r][c], graph[r + 1][c], graph[r][c - 1])
			answer = max(answer, graph[r - 1][c] + graph[r][c] + graph[r + 1][c] + graph[r][c - 1]) # ㅓ
		except:
			pass

		try:
			answer = max(answer, graph[r][c - 1] + graph[r][c] + graph[r][c + 1] + graph[r + 1][c]) # ㅜ
		except:
			pass

		try:
			answer = max(answer, graph[r - 1][c] + graph[r][c] + graph[r + 1][c] + graph[r][c + 1]) # ㅏ	
		except:
			pass
	
print(answer)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

14500번 시간초과 관련 질문

wonderkyum21 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말