백준 2589 : 보물섬

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

2589번: 보물섬

https://github.com/HPYoo/swcodingtest/commit/62118e398922bb9aac5c97340c4c44f14f86ed08

sw coding 2589 update(Baekjoon) · HPYoo/swcodingtest@62118e3

1. 단순하게 생각하자.

처음엔 땅 덩어리 파악 후 조합 함수 활용하여 거리를 전부 확인해주려고 했는데, 이렇게 하면 시간초과 날게 분명해보였다. 그냥 땅 위치 정보만 따온다음에 하나씩 BFS 로 최대 거리 측정하는 것이 단순하면서도 빠르게 접근 가능할 것 같았음.(내 생각엔) 내 면도날은 여기까지인가? 그래도 암튼 통과했으니 다행. 다른 코드들 찾아보면서 가속화 시킬 수 있는 방법 찾아보자.

 -1) 보드 내용 받아온다음에 땅 정보 전부 파악

 -2) 하나씩 빼보면서 BFS 탐색 : 어차피 W로 되어있는 곳은 못가니까 큐에 많은 데이터가 들어가지는 않을 것

 -3) 계산한 BFS를 토대로 거리함수 계속 최신화

 

2. 전체코드

 1차 풀이 - 메모리 : 121952 KB, 시간 : 1056 ms (순수 파이썬 내장 함수 활용)

 2차 수정 - 메모리 : 129724 KB, 시간 : 976 ms (deque 사용) // 풀이시간 : 30 min

 ! 조심할 것 : 코드 짤 때 방문함수 처리 등 자잘한 실수, 인덱싱 실수 하지 않을 것!

from collections import deque
N, M = map(int, input().split())
board = [list(map(str, input())) for _ in range(N)]
land_info = deque()
for i in range(N):
    for j in range(M):
        if board[i][j] == 'L' :
            land_info.append([i, j])
# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# Find Continent
def solve():
    maxValue = 0
    while land_info :
        x, y = land_info.popleft()
        q = deque([[x, y, 0]])
        visited = [[False for _ in range(M)] for _ in range(N)]
        visited[x][y] = True
        while q :
            x, y, cnt = q.popleft()
            maxValue = max(maxValue, cnt)
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] :
                    if board[nx][ny] == "L" :
                        visited[nx][ny] = True
                        q.append([nx, ny, cnt + 1])
    print(maxValue)

solve()