[백준_2589] 보물섬 python

바보같이 처음에 리커전을 통해,

두 좌표의 조합을 모두 구해 해결하려는 판단을 해 버렸고,

어림도없이 시간초과에 걸려버렸다.

# 입력 속도 개선
import sys
input = sys.stdin.readline

# n, m 입력
n, m = map(int, input().split())

# island 설계
island = [
    [0] * m
    for _ in range(n)
]

# island 입력
for i in range(n):
    s = input()
    for j in range(m):
        # 땅이면
        if s[j] == 'L':
            # 1로 처리
            island[i][j] = 1

# 함수들
# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

# can_go(x, y)
def can_go(x, y):
    # 범위 내에 있고, 육지이며, 방문한 적이 없으면 가능
    return in_range(x, y) and island[x][y] and not visited[x][y]

# bfs()
def bfs():
    while q:
        x, y = q.popleft()
        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            # 갈 수 있으면,
            if can_go(nx, ny):
                # 큐에 넣어주고,
                q.append((nx, ny))
                # 방문 처리 해 주고,
                visited[nx][ny] = 1
                # step 배열 관리
                step[nx][ny] = step[x][y] + 1

# simulate(x, y)
def simulate(x, y):
    
    # 전역 변수 선언
    global visited, step

    # visited 선언 및 초기화
    visited = [
        [0] * m
        for _ in range(n)
    ]

    # step 선언 및 초기화
    step = [
        [0] * m
        for _ in range(n)
    ]

    # bfs
    q.append((x, y))
    visited[x][y] = 1
    bfs()

    # 현재 최댓값
    curr_max = 0

    # step 돌면서
    for i in range(n):
        for j in range(m):
            # 발견한 값이 현재 최댓값보다 크다면
            if step[i][j] > curr_max:
                # 최댓값 교체
                curr_max = step[i][j]
    
    # 최댓 값 반환
    return curr_max

# 설계
# 거리의 최댓 값 설정
max_dist = 0

# 큐 사용준비
from collections import deque
q = deque()

# 섬을 돌면서
for i in range(n):
    for j in range(m):
        # 땅을 발견하면,
        if island[i][j]:
            # 시뮬레이션 돌려서 더 큰 값을 넣기
            max_dist = max(max_dist, simulate(i, j))

# 출력
print(max_dist)