📖문제

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

😭알린이의 실수😭

위에 있는 사진을 보면 시간초과가 발생하였다.
왜 시간초과가 발생했을까 ?? ( 답은 잘 나옴에도 불구하고 )
밑에 코드를 봐보자

# 시간 초과가 발생한 코드!!!!!
from collections import deque
import sys
import itertools

# 보물섬 지도 입력 받는 부분
sero,garo=map(int,input().split())

arr=[[]*garo for _ in range(sero)]

L_position=[]
for i in range(sero):
    str1=input()
    for k in range(len(str1)):
        arr[i].append(str1[k])
        if str1[k]=="L": # 육지 위치 저장
            L_position.append([i,k])

# 시작하는 위치와 목적지 위치의 모든 경우의 수를 조합으로 구함
nCr=list(itertools.combinations(L_position,2))

# 상하좌우 탐색 배열
dx=[-1,1,0,0]
dy=[0,0,1,-1]
ans=-1

# 조합으로 구한 모든 경우의 수에 대한 최단거리 구하기 
for i in range(len(nCr)):
    visited=[[0]*garo for _ in range(sero)]
    distance=[[-1]*garo for _ in range(sero)]
    start=nCr[i][0] #시작 위치
    end=nCr[i][1] # 목적지
    queue=deque()
    queue.append(start)
    visited[start[0]][start[1]] = 1
    distance[start[0]][start[1]] = 0
    
    #BFS 탐색 시작
    while queue:
        lst=queue.popleft()
        for i in range(4): # 상하좌우 탐색
            x=lst[0]+dx[i]
            y=lst[1]+dy[i]
            if 0<=x<sero and 0<=y<garo:
                if visited[x][y]==0 and arr[x][y]=="L":
                    visited[x][y]=1
                    distance[x][y]=distance[lst[0]][lst[1]]+1
                    queue.append([x,y])
                    
    if distance[end[0]][end[1]]!=-1:
   # 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳의 최단거리 
   # 결국 모든 경우의 수의 최단거리 중 가장 큰 값을 찾으면 된다.
        ans=max(ans,distance[end[0]][end[1]]) 


print(ans)

실수한 이유

1. 문제 해석과 풀이방법을 너무 1차원적으로 생각하였다.
-> 보물이 묻혀있는 두 곳을 모르네?
-> 그 두 곳을 고르기 위해 모든 경우의 수가 필요하네?
-> 조합을 써서 모든 경우의 수를 구하자
-> 모든 경우의 수를 BFS 탐색해서 최단거리들을 구하고 그 중에서 가장 큰 값을 구하자! -> 시간초과!!

2. 시간복잡도를 정확하게 계산하지 않고 그대로 구현으로 들어갔다.

이 부분에서

시간 복잡도

( 2500C2 )[조합 구할때 시간복잡도] x (50x50 )[ BFS 탐색시 시간복잡도 ]
=> 3,123,750 * 2500 => 7,809,375,000
=> 약 78억 =>약 78초쯤 걸린다.
78초이면 당연히 시간초과가 발생할 수 밖에 없다!!!

😎풀이 (해결책)😎

그럼 어떻게 풀어야 할까??

어차피 시작점에서는 "L"이 있는 모든 곳에 다 방문을 해야한다.
그리고 BFS 탐색시 "L"에 있는 모든 곳에는
시작점으로부터의 최단거리가 기록이 된다.

즉 , 우리는 조합을 사용하지 않더라도
어차피 시작점이 바뀔때마다"L"이 있는 모든 곳에
시작점으로부터의 최단거리가 기록이 되기 때문에
그때의 최단거리 최댓값을 구하면 된다.
그리고 그 최단거리 최댓값들 중에서 최댓값을 구하면
결국 가장 긴 시간이 걸리는 보물이 묻힌 육지 2곳에서의 최단거리를 알수 있다.

# 정답 코드
from collections import deque

# 상하좌우 탐색을 위한 배열
dx=[-1,1,0,0]
dy=[0,0,1,-1]

#BFS 탐색
def bfs(i,j):
    queue=deque()
    visited=[[0]*garo for _ in range(sero)]
    distance=[[0]*garo for _ in range(sero)]
    queue.append([i,j])
    visited[i][j]=1
    cnt=0 # 시작점으로부터 가장 먼 목적지의 최단거리를 구하기 위한 변수
    while queue:
        lst=queue.popleft()
        for k in range(4): # 상하좌우 탐색
            x=lst[0]+dx[k]
            y=lst[1]+dy[k]
            if 0<=x<sero and 0<=y<garo and visited[x][y]==0 and arr[x][y]=="L":
                visited[x][y]=1
                #"L"이 있는 곳마다 시작점으로부터의 최단거리를 기록한다.
                distance[x][y]=distance[lst[0]][lst[1]]+1
                queue.append([x,y])
                # 시작점으로부터 가장 먼 목적지의 최단거리 구하기
                cnt=max(cnt,distance[x][y])
    return cnt

# 보물섬 지도 입력
sero,garo=map(int,input().split())
arr=[[]*garo for _ in range(sero)]
for i in range(sero):
    str1=input()
    for k in range(len(str1)):
        arr[i].append(str1[k])

ans=0 # 최댓값 최단거리들 중에서의 최댓값 -> 가장 먼 두 곳 사이의 최단거리

# 전체 순환으로 시작점 업데이트 하면서 최댓값 최단거리들 중 최댓값 구하기
for i in range(sero):
    for j in range(garo):
        if arr[i][j]=="L":
            ans=max(ans,bfs(i,j)) # 최댓값 최단거리들 중 최댓값 업데이트

print(ans)

👩‍🎓 총평 👩‍🎓

아직 🟨골드 티어 문제 앞에서 나는
문제에 함정이 있는 것이 아닐까?
골드 문제라서 어렵지 않을까? 라는 두려움을 갖고 나아간다.

이번 문제는 단순하게
최댓값 최단거리들 중 최댓값을 찾는 문제인데
위의 이유로 너무 복잡하게 생각한 것이 컸다.

이번 문제를 통해 배운점

1. 항상 문제를 꼼꼼하게 읽고 문제의 본질을 파악하자
2. 시간복잡도를 꼼꼼하게 계산하여 알고리즘을 설계하자
3. 단계별로 잘 알고리즘을 차근차근 설계하자 -> 🟨골드 문제에 겁먹지 말자