[백준] 2589 보물섬 (Python)

22 Apr 2021

문제

백준 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())