글 읽기 - 아기상어 시간초과 질문입니다.

tjdgns9246 4년 전 0

안녕하세요, 삼성 SW역량 기출문제 풀다가 시간초과로 문제해결을 못해서 질문드립니다.

질문게시판에 나와있는 반례들은 모두 다 테스트 해봤는데요, 반례들은 다 정답으로 뜨지만 제 소스로 채점하니 2%에서 시간초과가 납니다..

제가 접근한 방식은

1. 맵 전체를 BFS로 순회하면서 상어가 먹을 수 있는 물고기의 위치를 우선순위 큐에 저장 (Priority는 거리, 행, 열 순입니다.)

2. BFS가 끝난 후, 우선순위 큐에서 물고기 위치를 얻음 (우선순위 큐가 비어있다면 먹을 수 있는 물고기가 없다는 뜻이므로 종료합니다.)

3. 물고기를 잡아먹고, 상어크기의 갯수만큼 물고기를 먹으면 상어의 크기를 1 증가

4. 1~3 반복

위와 같이 코딩을 했고, 테스트 케이스 및 질문 게시판에 있는 반례들을 다 테스트해봤는데 잘 됐습니다.

그런데 막상 제출을 하니 2%에서 시간초과가 나네요.

어떤 부분에서 잘못됐는지 알 수 있을까요?

감사합니다.

import sys
from queue import Queue, PriorityQueue

n = int(sys.stdin.readline())
board = [[0 for c in range(n)] for r in range(n)]
for i in range(n):
	board[i] = list(map(int, sys.stdin.readline().split()))


def solution(n):
	answer = 0
	directions = ((-1, 0), (0, 1), (1, 0), (0, -1))
	
	# find current shark position
	for i in range(n):
		for j in range(n):
			if board[i][j] == 9:
				shark = (i, j)
	
	eat_count = 0
	shark_size = 2
	while True:
		q = Queue()
		q.put((shark, 0))
		visited = set()
		visited.add(shark)
		eatable = PriorityQueue()
		
		# BFS
		while q.qsize() > 0:
			cur, dist = q.get()
			
			for (dr, dc) in directions:
				next_r = cur[0] + dr
				next_c = cur[1] + dc
				if 0 <= next_r < n and 0 <= next_c < n:
					# if the shark can visit the position
					if (next_r, next_c) not in visited and board[next_r][next_c] <= shark_size:
						q.put(((next_r, next_c), dist + 1))
						visited.add((next_r, next_c))
						# if there is a fish at the position
						if 0 < board[next_r][next_c] < shark_size:
							# add candidate to the priority queue by distance, row and column
							eatable.put((dist + 1, next_r, next_c))
		
		if eatable.qsize() > 0:
			# get the best fish from the priority queue
			dist, fish_r, fish_c = eatable.get()
			# move shark and eat fish
			board[shark[0]][shark[1]] = 0
			shark = (fish_r, fish_c)
			board[shark[0]][shark[1]] = 9
			eat_count += 1
			# shark eat fishes
			if eat_count == shark_size:
				shark_size += 1
				eat_count = 0
			# add distance
			answer += dist
		else:
			break
	return answer


print(solution(n))

redbin0471 4년 전 0

if (next_r, next_c) not in visited and board[next_r][next_c] <= shark_size:

이부분이 오래걸리는거 아닌가요 ???

tjdgns9246 4년 전 0

문제 해결한 링크 첨부하겠습니다.

https://empty-cloud.tistory.com/25

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