문제
백준 2589 보물섬 문제를 풀었습니다.
풀이
나의 사고 흐름
- 보물의 위치 : 최단 거리 이동할 때 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있음. 최단거리 이동에 가장 긴 시간이 걸리는 육지 두 지점을 찾아야 한다. 그럼 최단거리를 이루는 루트의 시작점을 어떻게 찾는가?
- 한 번의 탐색으로 해결 가능한가? (가령, 한 루트만 탐색하더라도 가장 먼 두 지점을 찾을 수 있는가?) : 최단거리만 잡고 돌 것이기 때문에 해결 불가능하다고 생각했습니다. 0, 1, 2, 3, … 처럼 시작점에서 각 노드에의 최단거리만을 갖고 있을 것이기 때문에, (적어도 내가 아는 한에서는) 계산이 불가능.
- 그럼 모든 노드를 탐색해도 되겠는가?
- BFS의 시간 복잡도 : O(N). 지도의 모든 곳이 육지로 꽉 차있다는 가정 하에 모든 노드가 모든 노드를 탐색해야 하는 상황.
- 지도의 최대 크기 : 50*50. 모든 노드에 대해 BFS를 하므로 O(N^2)이고, 50 50 밖에 안되므로 전부 다 탐색하라고 낸 문제라고 결론내림.
- 중간 분기점을 설정해서 특정 이상으로 가면 탈출하게 할 수 있는가? 딱히 불가능하다고 생각함. 최단거리의 최대값을 찾는 것이라서, 맨 끝의 끝까지 살펴보아야만 했음. 그래서 분기 탈출 설정 X
코드 - 디버깅용
from collections import deque
import copy
Dir = [[-1,0],[1,0],[0,-1],[0,1]]
rows, cols, MAP = 0,0,0
def isValid(dr, dc) :
return (0 <= dr < rows) and (0 <= dc < cols)
def BFS(MAP, visited, R, C) :
cnt = 0
q = deque([(R,C,cnt)])
visited[R][C] = True
while q :
nextR, nextC, cnt = q.popleft()
for D in Dir :
dr = nextR + D[0]
dc = nextC + D[1]
if isValid(dr, dc) and MAP[dr][dc] != 'W' and not visited[dr][dc] :
visited[dr][dc] = True
MAP[dr][dc] = cnt+1
q.append((dr, dc, cnt+1))
return cnt
def printMap(MAP) :
for maps in MAP :
for m in maps :
print(m, end='')
print()
def _2589() :
maxCnt = 0
global rows, cols, MAP
rows, cols = map(int, input().split())
MAP = [[]*cols for _ in range(rows)]
for row in range(rows) :
MAP[row] = list(input())
for row in range(rows) :
for col in range(cols) :
if MAP[row][col] != 'W' :
# print("start:", row, col)
visited = [[False]*cols for _ in range(rows)]
tmpMAP = copy.deepcopy(MAP)
tmpMAP[row][col] = 0
cnt = BFS(tmpMAP, visited, row,col)
# printMap(tmpMAP)
maxCnt = max(maxCnt, cnt)
# print(MAP)
return maxCnt
print(_2589())
첫 시도에서 52% 틀렸습니다가 나왔고, 어디가 문제인지 눈에 보이지 않아서 시작점을 0으로 두고 가는 모든 루트를 cnt로 갱신하는 방식으로 코드를 바꾸고 printMAP()을 추가하여 디버깅함.
- 그 결과 시작점에 visited 처리가 되지 않아 특정 경우에서, 한 바퀴 돌고 시작점을 한 번 더 방문하고는 함. -> visited 처리 해주고 통과
코드 (최소화)
from collections import deque
Dir = [[-1,0],[1,0],[0,-1],[0,1]]
rows, cols, MAP = 0,0,0
def isValid(dr, dc) :
return (0 <= dr < rows) and (0 <= dc < cols)
def BFS(visited, R, C) :
cnt = 0
q = deque([(R,C,cnt)])
visited[R][C] = True
while q :
nextR, nextC, cnt = q.popleft()
for D in Dir :
dr = nextR + D[0]
dc = nextC + D[1]
if isValid(dr, dc) and MAP[dr][dc] == 'L' and not visited[dr][dc] :
visited[dr][dc] = True
q.append((dr, dc, cnt+1))
return cnt
def _2589() :
maxCnt = 0
global rows, cols, MAP
rows, cols = map(int, input().split())
MAP = [[]*cols for _ in range(rows)]
for row in range(rows) :
MAP[row] = list(input())
for row in range(rows) :
for col in range(cols) :
if MAP[row][col] == 'L' :
visited = [[False]*cols for _ in range(rows)]
cnt = BFS(visited, row,col)
maxCnt = max(maxCnt, cnt)
return maxCnt
print(_2589())