[Python] BOJ(백준) 17086번 - 아기 상어 2

1. 링크

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

2. 난이도(solved.ac 참고)

실버2

3. 풀이1(메모리 초과)

	import sys
	from collections import deque
	input = sys.stdin.readline
	n, m = tuple(map(int, input().split()))
	shark_list = [list(map(int, input().split())) for _ in range(n)]
	ans = 0
	def bfs(x, y):
	q = deque([(x, y, 0)])
	dx = [-1, -1, -1, 0, 1, 0, 1, 1]
	dy = [-1, 0, 1, 1, 1, -1, 0, -1]
	while q:
	x, y, distance = q.popleft()
	for i in range(8):
	nx = x + dx[i]
	ny = y + dy[i]
	if 0 <= nx < n and 0 <= ny < m:
	if shark_list[nx][ny] == 0:
	q.append((nx, ny, distance+1))
	else:
	return distance+1
	for i in range(n):
	for j in range(m):
	if shark_list[i][j] == 0:
	ans = max(ans, bfs(i, j))
	print(ans)

view raw BOJ17086.py hosted with ❤ by GitHub

왜 메모리초과가 떴는지 이해가 안 간다.. 시간 초과도 아니고 메모리 초과라니. ans값을 심지어 배열로 두지도 않았고 상수로 두어 최댓값을 계속 업데이트하는 식으로 진행했는데? 메모리 초과가 뜬 원인을 아는 분이 있다면 댓글로 남겨주시면 좋겠다.

하.. 그래프탐색 문제를 오랜만에 푸니까 정신이 나갔나보다. visited 배열을 당연히 선언해줬어야 했는데 실수했다.

4. 풀이2(AC)

	import sys
	from collections import deque
	input = sys.stdin.readline
	n, m = tuple(map(int, input().split()))
	shark_list = [list(map(int, input().split())) for _ in range(n)]
	ans = 0
	def bfs(x, y):
	visited = [[False for _ in range(m)] for _ in range(n)]
	q = deque([(x, y, 0)])
	visited[x][y] = True
	dx = [-1, -1, -1, 0, 1, 0, 1, 1]
	dy = [-1, 0, 1, 1, 1, -1, 0, -1]
	while q:
	x, y, distance = q.popleft()
	for i in range(8):
	nx = x + dx[i]
	ny = y + dy[i]
	if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
	if shark_list[nx][ny] == 0:
	q.append((nx, ny, distance+1))
	visited[nx][ny] = True
	else:
	return distance+1
	for i in range(n):
	for j in range(m):
	if shark_list[i][j] == 0:
	ans = max(ans, bfs(i, j))
	print(ans)

view raw BOJ17086AC.py hosted with ❤ by GitHub

풀이1에서 visited를 추가했다.

5. 풀이3(AC)

	import sys
	from collections import deque
	input = sys.stdin.readline
	n, m = tuple(map(int, input().split()))
	shark_list = [list(map(int, input().split())) for _ in range(n)]
	q = deque()
	for i in range(n):
	for j in range(m):
	if shark_list[i][j] == 1:
	q.append([i, j])
	ans = 0
	dx = [-1, -1, -1, 0, 1, 0, 1, 1]
	dy = [-1, 0, 1, 1, 1, -1, 0, -1]
	while q:
	x, y = q.popleft()
	for i in range(8):
	nx = x + dx[i]
	ny = y + dy[i]
	if 0 <= nx < n and 0 <= ny < m:
	if shark_list[nx][ny] == 0:
	q.append([nx, ny])
	shark_list[nx][ny] = shark_list[x][y] + 1
	ans = max(ans, shark_list[x][y] + 1)
	print(ans-1)

view raw BOJ17086AC.py hosted with ❤ by GitHub

위 풀이와는 다르게 1일 때 큐에 넣고 BFS를 함수 형태로 빼지 않고 바로 시작했다.

 

뭐 결국 거리의 최댓값을 구하는 것이니 어렵지 않았다만 시간 초과도 아니고 메모리 초과가 뜬 건 이해가 잘 안 된다🤷‍♂️