2589번 - 보물섬

W는 바다, L은 대륙입니다.
대륙의 끝과 끝에 (둘 사이의 거리가 제밀 먼 곳에) 각각 보물이 묻혀있는데 이 둘 사이의 거리 중 제일 긴 거리를 구하면 됩니다.

---

세팅

from collections import deque
import sys
import copy
input = sys.stdin.readline

제가 쓸 방식은 인덱스 하나하나 다 BFS를 돌리고 deep copy 메소드를 사용할꺼기 때문에 시간이 많이 부족합니다. python에서 시간복잡도를 해결하기 위한 대표적인 방법 두 가지가 있죠? sysinput이랑 pypy3로 컴파일 하겠습니다.

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

BFS 항상 사용할 때처럼 상하좌우 설정을 해줍니다.

N,M = map(int,input().split())
map = []
que = deque()
for _ in range(N):
    map.append(list(input()))
map_copy = copy.deepcopy(map)
ans = []

보물지도의 입력을 받아줍시다. map이라는 변수 안에 받아주고 BFS를 하나하나 다 돌리기 위해서 map을 복제한 map_copy라는 변수도 하나 만들어주겠습니다.

for i in range(N):
    for j in range(M):
        ans.append(bfs(i,j))
        map = copy.deepcopy(map_copy)

아까 말씀드린대로 각 인덱스마다 bfs를 돌리고 map_copy로 복제한걸 다시 map 안에 넣어서 초기화 하는 과정을 반복하겠습니다.

---

BFS

def bfs(x,y):
    max = 0
    boolean = False
    que.append([x,y])

보물 사이의 거리수를 담을 max 함수를 초기화하고 boolean은 반례 처리를 위해서 설정해주겠습니다.

    if map[x][y] == 'L':
        map[x][y] = 1

자기자신이 땅이라면 1로 설정해주겠습니다.

    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue 
            if map[nx][ny] == 'L' and map[x][y] != 'W':
                boolean = True
                map[nx][ny] = map[x][y] + 1
                if max < map[nx][ny]:
                    max = map[nx][ny]
                que.append([nx,ny])

상하좌우 탐색을 돌아서 다음 것이 땅이라면 자기자신 + 1을 기입해 거기까지 가는 데의 거리를 인덱스에 대입해주겠습니다.
만약 자기자신+1이 여태 나온 가는데까지의 거리 중 가장 크다면 그게 곧 보물과 보물 까지의 거리이기 때문에 max에 넣고

    if boolean == True:
        return max
    else:
        return 1

이렇게 추가시켜주겠습니다.

---

print(max(ans)-1)

마지막으로 BFS로 돌린 보물과 보물 사이의 거리 후보들 중 현재 위치를 제외한 가장 큰 값을 출력하면 됩니다.

---

반례

아까 boolean 값을 설정해서 반례 처리를 해준다고 언급했었죠? 제가 햇갈렸던 두 가지 반례를 소개합니다.

1 2
WL

먼저 이런씩으로 작성이 되어있다면 탐색을 아예 안돌기 때문에 max의 초기값 0에서 -1이 빠져버린 -1값이 도출되게 됩니다.
해당 값을 0으로 도출하기 위해서 탐색을 아예 안돌았다면 1로 return 하여 0이 출력되게 유도합시다.

7 7
WLLLLLW
LWLWLWW
LLLWLWW
LWWWLWW
LLLLLWW
LWWWWWW
WWWWWWW

처음에 생각했던 코드는 어떤 씩이었냐면

for i in range(M):
    ans.append(bfs(N-1,i))

위와같이 어? 맨 아래만 탐색을 돌아도 보물끼리의 최단거리값이 도출되는거 아닌가? 했는데
위 반례를 보면 무작정 아래만 본다고 해서 최단거리값이 나오지는 않습니다.

한 가지 더 의문이 든 것은 제가 코딩테스트 준비를 위해 PS를 푸는게 주된 목적인데 기업에서 pypy3를 컴파일러로 제공해주지는 않을 것 같고 제 실력에서 python3로 사실상 시간초과 때문에 풀기 힘든 문제가 있다면 이걸 pypy3로만 마냥 해결해도 괜찮을까? 했는데

PyPy3로 제출하면 통과됩니다.

라는 게시글을 보고 안심할 수 있었습니다. pypy3로 통과될 만한 문제를 python3로 못풀었다고 기업에서 거를 정도의 시간복잡도를 가진 문제를 낼 가능성은 거의 없다고 봐야할 것 같습니다.

---

---