[Python] BOJ(백준) 2589번 - 보물섬

1. 링크

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

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

골드5

3. 풀이

	from collections import deque
	import sys
	input = sys.stdin.readline
	n, m = map(int, input().split())
	s = list(list(map(str, list(str(input().strip())))) for _ in range(n))
	dx = [-1, 1, 0, 0]
	dy = [0, 0, -1, 1]
	def bfs(x, y):
	graph = [[0] * m for _ in range(n)]
	q = deque([(x, y)])
	graph[x][y] = 1
	temp = graph[x][y]
	while q:
	x, y = q.popleft()
	for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]
	if 0 <= nx <= n-1 and 0 <= ny <= m-1 and s[nx][ny] == 'L' and not graph[nx][ny]:
	graph[nx][ny] = graph[x][y] + 1
	if graph[nx][ny] > temp:
	temp = graph[nx][ny]
	q.append((nx, ny))
	return temp - 1
	result = 0
	for i in range(n):
	for j in range(m):
	# 여기부터
	if i > 0 and i+1 < n:
	if s[i-1][j] == "L" and s[i+1][j] == "L":
	continue
	if j > 0 and j+1 < m:
	if s[i][j-1] == "L" and s[i][j+1] == "L":
	continue
	# 여기까지의 조건이 없다면 Python 3은 통과할 수 없음
	if s[i][j] == 'L':
	result = max(result, bfs(i, j))
	print(result)

view raw BOJ2589.py hosted with ❤ by GitHub

n과 m이 각각 50까지밖에 안되는 것을 보고 브루트포스로 해도 되겠다는 생각이 들었다. 우선 아이디어는 각 위치별로 가장 먼 곳까지 가는 숫자를 찾아야 하기 때문에 L일 때마다 BFS를 실행하고 이중 배열을 초기화하여 최대값을 갱신해가는 것인데, 일반적인 BFS로만 풀면 PyPy3으로만 통과할 수 있다. 

코드에도 있듯이, 좌우 혹은 상하가 모두 L이라면 그 자리는 가장자리가 아니기 때문에 탐색을 넘김으로써 불필요한 배열 재선언 및 BFS의 실행을 방지할 수 있다.