[Algorithm🧬] 백준 2589 : 보물섬

문제

BFS 로 방문하면서 거기까지 간 거리를 입력했는데...

W 0 1 W W W 0
2 1 2 W 3 2 1
3 W 3 W 4 W W
4 W 4 W 5 6 7
W 6 5 W 6 W W

이렇게 되고 있어서.... 7이 최댓값으로 잡힘...
양쪽으로 분기 타는게 아니라 하나에서 하나로 갈때 가장 큰 길이 필요... 그건 어케 하지...
-> 그냥 모든 시작 육지에 대해서 따져주면 되는거였다.

나는 dist + 1 을 넣는 것으로 풀었는데 다른사람들은 max 를 이용한듯.. 주석으로 max 이용풀이도 넣어둠!
그런데 이해 안가서

처음에 생각했던 방법대로 짠 코드

def BFS(i, j):
    q = deque()
    adj = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    ch = [[0] * w for _ in range(h)] # 이걸 여기로 안넣어서 계속 뭔가 다른 값이 나왔는데,

    q.append((i, j, 0))
    ch[i][j] = 1

    while q:
        x, y, dist = q.popleft()
        # print(x, y, ch[x][y])
        for dx, dy in adj:
            nx = dx + x
            ny = dy + y

            if not 0 <= nx < h:
                continue
            if not 0 <= ny < w:
                continue

            # 육지가 아니라면
            if pmap[nx][ny] == "W":
                continue

            if ch[nx][ny] != 0:
                continue

            ch[nx][ny] = 1
            # 방금 탐색한 것과 이전까지의 최댓값 중 더 큰걸 담아야됨.
            q.append((nx, ny, dist + 1))

    return dist # 처음에 1로 시작하니까.

readl = sys.stdin.readline
h, w = map(int, readl().split())
pmap = [[c for c in readl().strip()] for _ in range(h)]

max_dist = 0
# BFS 로 탐색해서 성분 찾고, 그 중 최단거리가 최대인 것을 찾으면 될듯...?
for i in range(h):
    for j in range(w):
        # 다른 BFS 처럼 하나의 지점에서 시작해서 그것과 이어진 지점을 한번 돌고 끝나는게 아니라,
        # 모든 육지에 대해서 BFS 를 수행하고 (그래프 하나에도 여러번 접근) 
        # 가장 먼 곳을 찾아서 그 곳의 거리 중 가장 큰 것을 찾는다.
        if pmap[i][j] == "L": # 여기서 ch 는 검사를 안하니까!!
            max_dist = max(max_dist, BFS(i, j))

print(max_dist)

max 를 이용하는 코드

import sys
from collections import deque


def BFS(i, j):
    q = deque()
    adj = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dist_arr = [[0] * w for _ in range(h)] # 이걸 여기로 안넣어서 계속 뭔가 다른 값이 나왔는데,

    q.append((i, j))
    dist_arr[i][j] = 1 # 사실은 0인데 방문 체크를 위해 1부터 시작
    max_dist = 0

    while q:
        x, y = q.popleft()
        # print(x, y, dist_arr[x][y])
        for dx, dy in adj:
            nx = dx + x
            ny = dy + y

            if not 0 <= nx < h:
                continue
            if not 0 <= ny < w:
                continue

            # 육지가 아니라면
            if pmap[nx][ny] == "W":
                continue

            if dist_arr[nx][ny] != 0:
                continue

            dist_arr[nx][ny] = dist_arr[x][y] + 1
            # 방금 탐색한 것과 이전까지의 최댓값 중 더 큰걸 담아야됨.
            max_dist = max(max_dist, dist_arr[nx][ny])
            q.append((nx, ny))

    return max_dist - 1 # 처음에 1로 시작하니까.


# 뒤는 같아서 생략.

일단 이건데... 시간 초과 남....
심지어 다른 사람들이 올려둔 풀이도 넣어보면 시간 초과 남
다른 글에 있는 PyPy3 으로 제출해봤더니 됐다...
pypy3 서버 설명