백준/ Gold 5 문제 , 백준 파이썬 2589, 보물섬 [BFS]

백준/ Gold 5 문제 , 백준 파이썬 2589, 보물섬  [BFS]

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
최대 거리로 떨어져있는 것들 중에서의 최단 거리를 구하는 문제.
뭐 결국 bfs 를 돌려봐서 최대 거리를 구하는 것과 동일하다.

 

문제 출처

 

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

2589번: 보물섬

 

 

풀이

 

 

1. 기본 세팅

 

1. 상하좌우 움직일 수 있게 vertical, parallel 선언

 

2. N,M 입력받기

 

3. N 행만큼의 입력 받아 MAP 이라는 리스트에 담기

 

 

 

 

2. BFS 호출을 최대한 줄이기 위한 작업

 

굳이 L이 있는 모든 칸에서 BFS 함수를 호출 할 필요가 있을까?

 

최대 거리는 L들로 둘러싸여있는 L 이 아닌 범위의 끝쪽에 형성 되어있을 것이다.

 

그렇다면 그 정답이 될 L 은 맞붙어있는 L들의 최대 숫자가 최대 2개일 것이다.

 

왜냐면 주변 L이 3개이상 부터는 최대거리를 가진 L 이 아니기 때문이다.

 

예를 들어보면, 

 

 

위와 같은 입력이 주어진다고 하자.

 

 

그렇다면, 이 빨간 구역들은 확인할 필요가 없다. 

 

끝값들이 아니기 때문에 이 구역에서는 최대거리를 가진 L 이나올수 없다.

 

이렇게만 제외해줘도 bfs 호출이 반정도로 확 주는 것을 확인할 수 있다.

 

 

 

3. BFS 호출

 

시작자리와 탐색한 자리들은 재탐색을 막기위해 다른 문자로 바꿔준다.

 

나는 'N'으로 바꿨지만 L 말고 다른 아무 문자로 하면 된다.

 

이후 dq에는 방문할 자리 인덱스와 거리를 1씩 증가시켜 dq에 넣어주면된다.

 

이때 거리는 따로 tmp 변수에 넣어준 뒤 while 문 종료후 이 tmp 값만 return 시킨다.

 

 

 

 

 

아까 위에서 걸러주었던 L들만 bfs 를 호출시키고 리턴받은 값들중에서 가장 큰값을 골라주면 끝이다.

 

 

 

정답

 

 

from collections import deque
from copy import deepcopy

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]

N,M=map(int,input().split())
MAP=[]
for i in range(N):
    MAP.append(list(input()))
MAX=0
LAND=[]
for i in range(N):
    for j in range(M):
        if MAP[i][j]=='L':
            cnt=0
            for k in range(4):
                mx=i+vertical[k]
                my=j+parallel[k]
                if 0<=mx<N and 0<=my<M:
                    if MAP[mx][my]=='L':
                        cnt+=1
            if cnt<=2:
                LAND.append([i,j])

def bfs(x,y):
    COPY=deepcopy(MAP)
    COPY[x][y]='N'
    dq=deque()
    dq.append([x,y,0])
    tmp=0
    while dq:
        X,Y,cnt=dq.popleft()
        for i in range(4):
            mx=X+vertical[i]
            my=Y+parallel[i]
            if 0<=mx<N and 0<=my<M:
                if COPY[mx][my]=='L':
                    COPY[mx][my]='N'
                    dq.append([mx,my,cnt+1])
                    tmp=cnt+1      
    return tmp

for i in LAND:
    x,y=i[0],i[1]
    result=bfs(x,y)
    if MAX<result:
        MAX=result

print(MAX)