[백준/파이썬] 2589 보물섬

#문제링크

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

2589번: 보물섬

#나의풀이

import sys
from collections import deque

delta = [[-1, 0], [0, 1], [1, 0], [0, -1]]
board = []
R = 0
C = 0
answer = 0

def BFS(i, j):
    global answer
    check = [[2147000000] * C for _ in range(R)]
    check[i][j] = 0
    queue = deque()
    queue.append((i, j))

    while(queue):
        tmp = queue.popleft()
        for i in range(4):
            dx = tmp[0] + delta[i][0]
            dy = tmp[1] + delta[i][1]
            if 0 <= dx < R and 0 <= dy < C and check[dx][dy] == 2147000000 and board[dx][dy] == 'L':
                check[dx][dy] = check[tmp[0]][tmp[1]] + 1
                queue.append((dx, dy))

    max_value = 0
    for values in check:
        for value in values:
            if value != 2147000000:
                max_value = max(max_value, value)

    answer = max(answer, max_value)
if __name__=="__main__":
    R, C = map(int, sys.stdin.readline().split())

    for _ in range(R):
        S = sys.stdin.readline().strip()
        tmp = []
        for i in range(C):
            tmp.append(S[i])
        board.append(tmp)

    for i in range(R):
        for j in range(C):
            if board[i][j] == 'L':
                BFS(i, j)

    print(answer)

#해설

기존 BFS에서 특이한 조건 이 붙었던 문제였다.

같은 육지에 있는 지점끼리 가장 큰 최단거리를 찾는 문제였는데 특정한 조건은 보이지 않았고 전부 탐색을 해봐야겠다 라는 생각이 들었다.

 

입력 부분은 제외하고 배열을 돌면서 육지를 찾고 BFS로 좌표를 던져준다.

BFS에서 부분은 가장 멀리간 최단 길이를 구해야 하기 때문에 엄청큰 값으로 초기화를 시켜주었고 4방탐색으로 count를 check 배열에 넣어 주었다. 이후 가장긴 최단거리를 찾고 결과 값과 비교후 더 길면 바꿔주었다.

 

기존에 하던 방식으로 방문과 dp를 같이 썼는데 좀 아쉬운거 같다 방문따로 DP를 전역으로 하고 만약 현재값이 DP보다 작으면 바로 끝내면 시간적으로 많이 줄일수 있을꺼 같다는 생각이 들었다.