문제

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

보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육 두곳에 나뉘어 묻혀있다 << 이 부분에서 엥 뭐라는..? 싶었는데 육지 구역에서 가장 멀리 떨어져 있는 두 점을 얘기하는 거였다!

(0,0) 부터 (r-1,c-1) 까지 각각 시작 지점을 기준으로 최대한 움직일 수 있는 구역에서 움직이며 해당 구역에 있는 모든 육지노드에 대해 최단거리를 구하고 최단거리들 안에서도 최대값을 구한다.

계속해서 최단거리의 최대값을 갱신하며 위의 과정을 반복한다 😀

내 코드

import sys
from collections import deque

row,col=map(int,input().split())

graph=[]
for _ in range(row):
    graph.append(list(sys.stdin.readline().strip()))


dx=[1,-1,0,0]
dy=[0,0,1,-1]

def sol(r,c,visited):
    if graph[r][c]=='W':
        return
    visited[r][c]=1
    q=deque([[r,c]])
    while q:
        r,c=q.popleft()
        tmp=[]
        for x,y in zip(dx,dy):
            if -1<r+x<row and -1<c+y<col:
                tmp.append([r+x,c+y])
        for a,b in tmp:
            if graph[a][b]=='L' and visited[a][b]==False:
                q.append([a,b])
                visited[a][b]=visited[r][c]+1



max_num=0
for i in range(row):
    for j in range(col):
        visited=[[False]*(col) for _ in range(row)]
        sol(i,j,visited)
        num=max(map(max,visited))
        if num>max_num:
            max_num=num

print(max_num-1)

원래 시작하는 좌표에서는 distance가 0이다.(시작한 곳에선 아무 움직임이 없었으니까 0) 근데 컴퓨터는 내부적으로 0이라는 값을 False라고 인식하고 0이 아닌 다른 수는 True로 인식한다.

이 점을 이용해서 더 효율적으로 문제를 풀기위해 시작하는 좌표의 distance를 0이 아닌 1로해서 방문처리와 거리측정을 visited배열 하나로 원큐에 관리가능하도록 했다~!

이렇게 하면 방문처리할 visited, 거리 값을 저장할 distance 이런식으로 리스트를 따로 관리할 필요가 없어진다.

distance의 값이 1이상이라는 건 이미 그 노드에 방문했다는 거다. 0이 아닌 수는 컴퓨터에서 내부적으로 True로 인식되는 점을 이용해서 visited 배열 하나로 distance값과 방문여부를 관리할 수 있도록 했다.

그리고 이 부분은 마지막에 값을 구할 때 -1 해주면 알맞은 값이 된다!

할 일이 태산인데 코테 푸는게 제일 재밋다 ㅎ0ㅎ ;;;;