[백준/Python]2589: 보물섬

문제

https://www.acmicpc.net/problem/2589
백준 문제집 - 대학생 기본반

---

풀이

사실 보물이고 나발이고, 이 문제의 핵심은 "육지-육지 간의 거리중 가장 최댓값"을 구하는것이다.

보물섬 지도에서 L은 육지, W는 바다를 나타낸다.

1. 육지는 모두 붙어있는것이 아닌 몇개의 섬으로 이루어져있는 형태다.
2. 가장 먼 거리를 D라고 했을때, 어느 L이 시작점/끝점 인지 불분명하다.

따라서 L을 발견할때마다 bfs를 실행해줘야 한다.

 

전체 코드

# 문제집 - 대학생 기본반


# 문제: https://www.acmicpc.net/problem/2589
# 메모리: 34072KB / 시간: 4264ms
from sys import stdin
from collections import deque


input = stdin.readline

def bfs(x, y):
    global ret
    queue = deque([(x, y, 0)])
    visited = [[False] * n for _ in range(m)]
    visited[x][y] = True

    while queue:
        cx, cy, dis = queue.popleft()
        ret = max(ret, dis)

        for nx, ny in ((cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1)):
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue

            if not visited[nx][ny] and MAP[nx][ny] == "L":
                visited[nx][ny] = True
                queue.append((nx, ny, dis + 1))


m, n = map(int, input().split())
MAP = [input().rstrip() for _ in range(m)]

ret = 0

for i in range(m):
    for j in range(n):
        if MAP[i][j] == "L":
            bfs(i, j)

print(ret)

 

모든 L에 대해서 실행했기때문에 실행시간이 어마어마하다.

다른풀이를 찾아보니 내 실행시간의 1/10도 안되는 케이스가 많았다...;;
(그리고 나처럼 L을 발견할때마다 bfs를 실행했다가 시간초과가 뜨는 경우도 있었다.)

 

 

새로운 풀이의 방식은 이러하다.

만약, 해당 L의 상하 or 좌우에 L이 존재한다면?
현재의 L은 중간에 낀 모양새이므로 최단거리의 시작점이 될 수 없다. => pass!

 

아래는 공개된 풀이 중 하나다. 실행시간은 384ms!
(사실 더 빠른 풀이도 있었으나 가독성이 떨어져서 넘겼다.)

# 출처: https://www.acmicpc.net/source/83166630
from collections import deque
import sys
input = sys.stdin.readline


def bfs(r,c):

    dist = [[0] * m for _ in range(n)]
    dr = [-1,1,0,0]
    dc = [0,0,-1,1]

    visited[r][c] = True

    queue = deque()
    queue.append((r,c))

    while queue:

        r, c = queue.popleft()

        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if 0 <= nr < n and 0 <= nc < m and board[nr][nc] == 'L' and not visited[nr][nc]:
                dist[nr][nc] = dist[r][c] + 1
                visited[nr][nc] = True
                queue.append((nr,nc))


    return max(map(max,dist))


n, m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]

answer = 0
for i in range(n):
    for j in range(m):
        if board[i][j] == 'L':
            visited = [[False] * m for _ in range(n)]
            if 0 <= i - 1 and i + 1 < n:
                if board[i - 1][j] == 'L' and board[i + 1][j] == 'L':
                    continue
            if 0 < j - 1 and j + 1 < m:
                if board[i][j - 1] == 'L' and board[i][j - 1] == 'L':
                    continue
            answer = max(answer, bfs(i, j))

print(answer)

 

먼저 현재 육지의 상하좌우가 범위 내에 있는지 체크하고,
상하 또는 좌우에 L이 존재한다면 바로 다음 반복문으로 넘어간다.

            if 0 <= i - 1 and i + 1 < n:
                if board[i - 1][j] == 'L' and board[i + 1][j] == 'L':
                    continue
            if 0 < j - 1 and j + 1 < m:
                if board[i][j - 1] == 'L' and board[i][j - 1] == 'L':
                    continue

내 원래 코드로도 Python3 통과가 가능하지만, 👆위 풀이가 훨씬 더 효율적이다.
문제가 요구하는 답에 더 가깝기도 한 것 같다.

 

조금만 더 생각하면 떠올릴 수 있는 풀이다.
평소에 깊이 생각하는 습관을 길러야겠다...