보물섬
입력:
세로 가로
보물섬 지도
출력:
최단 거리로 이동하는 시간
입력 예시)
5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW
우선 육지로 이동할 수 있는 경로를 찾는 방법
1. 모든 원소 가보기
2. 섬이면 상하좌우 이동
3. bfs로 결정되는 시간을 ans=[]에 저장한다.
-
예시의 경우 좌측의 그래프는 깊이 6칸, 7칸이다. 각 그래프에서 최단거리로 이동하는 방법은 뭘까?
-
특이한 점은 왼쪽 그래프 첫 번째 노드에서 깊이는 6인데, 정답 노드에서 측정되는 깊이는 8이다. 최단거리를 무시하고, 최장거리만 생각해보면, 가장 긴 거리의 노드는 깊이값이 최대가 되는 노드 위치가 된다.
-
그럼 bfs로 탐색되는 탐색에서 깊이의 최댓값을 갱신하면서 모든 원소를 탐색하면 깊이의 최댓값을 구할 수 있다.
-
노드마다 bfs의 깊이정보를 저장해둔다.
W66WWWW7
6...
8WLWLLL
W8L
그래서 이걸로 어떻게 구합니까
아니 어처피 bfs로 탐색하면 최단거리가 나온다. 육지로 갈 수 있는 모든 노드에서 최단거리가 최대인 지점에 보물이 심어질 수 밖에 없다. 그 말은 곧 뭐다. 그래프에서 최대 깊이를 구하면 된다. 걍 이게 끝이었음. 애초에 "최단거리를 최장시간으로 간다" == "bfs(최단거리)로 깊이가 젤 멀리 있는 지점으로 간다"인 것. 그러면 모든 노드를 탐색하면서 깊이가 커질 때마다 최대 깊이를 업데이트해주고 마지막에 최대 깊이출력해주면 된다. -
최단거리 라는 단어에 꽂혀서 좀 헤멨다.
bfs에서 가장 큰 깊이를 리턴하게 하는 방법
-> 큐에 삽입할 때 깊이값을 1 늘려준 상태로 추가 삽입한다.
-> popleft 할 때마다 max_depth를 갱신한다.
-> 처음에 i j 0 이 들어감 -> popleft 하고 상하좌우 움직임 -> 움직이 수 있으면 해당 ni, nj, 1로 저장 -> 다시 popleft 이때 max_depth = max(max_depth, depth)로 깊이가 유지되면서 순회하도록 저장한다.
(+) visited를 사용하지 않고 풀었지만 처음에 틀렸다. L이라고 바로 넘어갈 수 있는게 아니므로 visited 방문 여부도 동시에 확인하도록 하자.
시간초과가 떴다.
-> 모든 L에 대해서 bfs를 돌리면 시간초과 난다.
-> L을 선택적으로 bfs에 돌려야 한다.
-> 그럼 무슨 조건을 추가하냐
=> 내 양 옆, 위 아래가 땅인 경우, 그 땅에서 출발할 때 반드시 더 긴 시간이 걸리므로 해당 땅은 탐색하지 않는다.
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(N)]
ans = 0
def bfs(i, j):
q = deque([])
q.append([i, j, 0]) # 찾은 섬부터 시작
visited = [[False]*M for _ in range(N)]
max_depth = 0
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
while q:
ci, cj, depth = q.popleft()
visited[ci][cj] = True
max_depth = max(max_depth, depth)
for dir in range(4):
ni, nj = ci+dx[dir], cj+dy[dir]
# 이동이 되면
if 0 <= ni < N and 0 <= nj < M and graph[ni][nj] == 'L' and not visited[ni][nj]:
q.append([ni, nj, depth+1])
visited[ni][nj] = True
return max_depth
for i in range(N):
for j in range(M):
if graph[i][j] == 'L':
if 0 <= i-1 and i+1 < N:
if graph[i-1][j] == 'L' and graph[i+1][j] == 'L':
continue
if 0 < j-1 and j+1 < M:
if graph[i][j-1] == 'L' and graph[i][j-1] == 'L':
continue
ans = max(ans, bfs(i, j))
print(ans)
코드를 입력하세요
단순 bfs인데 검사 조건과 깊이 탐색에서 헤멨다. 문제 이해도 오래 걸리고. 조금 까다로웠다.
