[Python][백준] 2589. 보물섬 / 브루트포스,BFS (G5)

링크🔗

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

---

🗒️파이썬 코드 풀이

from collections import deque 
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N,M = map(int,input().split())
graph = [list(input().strip()) for _ in range(N)]
visited = [[-1] * M for _ in range(N)]
ans = -1
di,dj = [0,1,0,-1],[1,0,-1,0]


def bfs(i,j):
    global ans
    visited = [[-1] * M for _ in range(N)]
    visited[i][j] = 0

    q = deque([[i,j]])
    while q:
        v = q.popleft()
        for k in range(4):
            ni,nj = v[0]+di[k], v[1]+dj[k]
            if 0<=ni<N and 0<=nj<M:
                if graph[ni][nj] == "L" and  visited[ni][nj] == -1:
                    visited[ni][nj] = visited[v[0]][v[1]] + 1
                    q.append([ni,nj])
                    ans = max(visited[ni][nj],ans)


for n in range(N):
    for m in range(M):
        if graph[n][m] == "L":
            if 0<=n-1<N and 0<=n+1<N:
                if graph[n-1][m] == "L" and graph[n+1][m] == "L":
                    continue
            if 0<=m-1<M and 0<=m+1<M:
                if graph[n][m-1] == "L" and graph[n][m+1] == "L":                            
                    continue
            bfs(n,m)
print(ans)

 

1. 최단거리를 구해야 하는 문제이므로 BFS가 적합하다. 

(DFS로 시도해보려다 실패 했음 ...)

 

2. 먼저 graph를 입력받아 채워 넣고, visited 2차원 리스트를 -1의 값으로 만들어준다.

 

3. BFS 함수를 실행 할 때마다,

가장 먼저 전달 받은 매개변수 i,j 위치의 visited 인덱스를 0으로 한다.

 

4. BFS의 가장 기본이 되는 Queue 자료구조를 만들어주고, while 문 작성한다.

 

5. popleft() 함수로 확인 할 인덱스를 v 에 넣어주고, 위/아래/양/옆의 조건들을 확인한다.

- ni와 nj가 범위 내에 있는지를 확인
- ni,nj 인덱스 위치에서 graph 값은 L인고,  방문를 하지 않았는지를 확인 

 

6. ni,nj가 조건에 맞는다면 Queue에 넣어준다 .

 

7. BFS를 한번 실행 할 때.  그 특정 i,j에서 최단 거리는 visited의 값이 최대 일 때이다. 

ex) (i,j) = (0,3) 일 때 BFS 예시 

W	L	L	W
L	L	L	W
L	W	L	W
L	W	L	W
W	L	L	W

(graph 리스트)

-1	4	5	-1
2	3	4	-1
1	-1	5	-1
0	-1	6	-1
-1	8	7	-1

(visited 리스트)

visited에서 최대값 8이 최단 거리가 된다,

 

 

8. N,M의 크기가 최대 50이여서, 어느정도 가지치기를 해줘야한다. 

그래서 넣은 조건이 BFS 실행 전 조건이다. 

해당 조건은 양 옆에 L이 있거나 위/아래 L이 있는 경우를 제외시킨다.

(이렇게 안하면 시간 초과가 발생한다.)

 

 

➕ 주의 사항

🚨맨 처음  visited = [[0] * M for _ in range(N)] 으로 해두고, 
BFS 실행 때 매개변수 i,j 위치의 visited 인덱스를 초기화 안했다. 

 

L	L
L	W

맨 처음 내가 했던 방식대로 하면, 이 상황에서 문제가 생긴다.

 

0	1
1	0

원래 최단거리 답이 1이 나와야 하는데,

(0,1) 또는 (1,0)이 q에 잡힐 때, (0,0)을 방문 안했다고 취급하여,

최단거리가 2가 나오게 되는 것이다.

 

그렇기 때문에 최단거리를 구할 때는,

visited 초기값과 BFS 실행 때 전달 받은 i,j 위치의 인덱스를 다르게 해야한다. 

 

 

📌  문제 코멘트

최근에 BFS와 DFS를 많이 풀어서 자신감이 차오른 상태였다.

 

나는 개인적으로 DFS가 편해서 DFS로 풀었는데,

도저히 내가 원하는 최단거리를 구할 수 없었다. 

그래서 최단거리 문제는 BFS로만 풀어야 되는것을 알았다.

 

그리고 다시 혼자 문제플 풀어보는데, 자꾸 시간 초과가 뜨는 것이다.

그래서 여러 블로그 찾아보면서 내 풀이랑 비교했는데, 큰 차이가 없었다.

심지어 대부분의 블로그 코드들 또한 시간초과가 발생했다. 

(문제 제한 시간이 바뀐건가...)

 

결국 어떤 블로그를 통해서

BFS 실행 전 양옆 / 위아래 필터링을 추가함으로써 정답처리가 되었다. 

 

개인적으로 굳이 이렇게까지 해야하나 생각이 든다...

N,M의 범위를 20정도만 해도 될 것 같은데...?? 

이번 문제에 멘탈이 와자작 나서 그냥 이런 생각을 해봤다.

---

📚문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

예제 입력 1 복사

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

예제 출력 1 복사

8