[Python] BOJ 2589 - 보물섬

www.acmicpc.net/problem/2589

2589번: 보물섬

1. 보물 -> 육지 사이의 최장거리이므로 지도(m)을 입력받고 지도에 있는 모든 육지좌표를 land배열에 저장한다.

 

2. bfs함수: visited배열초기화, dist배열 0으로 초기화, (i, j) 시작지점에 대해 deque에 넣고 bfs를 돌린다.

   만약 상하좌우 칸에 방문하지 않았고, 그 칸이 육지라면 거리를 1증가시킨다. 최종적으로 거리의 최댓값을 return

   (27번째 줄 코드는 2차원 배열에서 최댓값을 구하는 코드이다. 좌표문제에서 편리하게 쓸 수 있으니 기억해두자!)

 

3. land에 있는 좌표들을 모두 돌면서 최장거리를 max_dist에 저장해주고 출력한다.

 

from collections import deque
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
m = [input() for _ in range(N)]
dx, dy = [0,0,-1,1], [1,-1,0,0]
land = []
for i in range(N):
	for j in range(M):
		if m[i][j] == 'L':
			land.append((i,j))

def bfs(i,j):
	visited = [[False] * M for _ in range(N)]
	visited[i][j] = True
	dist = [[0] * M for _ in range(N)]
	q = deque([(i,j)])
	while q:
		x, y = q.popleft()
		for k in range(4):
			nx, ny = x + dx[k], y + dy[k]
			if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and m[nx][ny] == 'L':
				q.append((nx,ny))
				dist[nx][ny] = dist[x][y] + 1
				visited[nx][ny] =  True
	return max(map(max, dist))
    
max_dist = 0
for i, j in land:
	max_dist = max(bfs(i,j), max_dist)
print(max_dist)

(solved.ac 티어: 골드 5)

 

# 요즘 삼성기출문제(구현, 시뮬레이션)를 풀고 있는데, 너무 어렵다.. 한시간 반 넘게 노트에 풀고 코드로 옮겨 실행했는데 틀리면 시뮬레이션 문제라 반례찾는것도 불가능하고, 손으로 직접 시뮬레이션 돌리면 너무 오래걸리고 푸는 시간도 길어 틀렸을 때 다시 손대기가 싫어진다ㅠㅠ

머리도 식힐 겸 다시 백준 문제로 돌아왔다.