백준 2146번 다리만들기

백준 2146번 다리만들기

문제 바로가기

문제 해결

💣 bfs를 이용한 최소 거리 완전 탐색방법

이 문제는 각 구역에서 다른 구역으로 가는 최단 거리를 구하는 것입니다.
해결하기 위해서는 각 구역끼리 서로 구분할 수 있어야합니다.

import sys
from collections import deque

def splitGround():
  numbering = 2
  for i in range(N):
    for j in range(N):
      if board[i][j] != 1:
        continue 
      deq = deque()
      deq.append([i, j])
      board[i][j] = numbering
      while deq:
        r, c = deq.popleft()
        for v in range(4):
          newRow = r + dy[v]
          newColumn = c + dx[v]

          if newRow < 0 or newRow >= N or newColumn < 0 or newColumn >= N:
            continue

          if board[newRow][newColumn] == 1:
            board[newRow][newColumn] = numbering
            deq.append([newRow, newColumn])
      
      numbering += 1
  return numbering

def calculateMinDistance(countGround):  
  minDistance = 100001
  distDictionary = {count : [[0 for i in range(N)] for v in range(N)] for count in range(2, countGround)}
  for i in range(N):
    for j in range(N):
      if board[i][j] == 0:
        continue 
      
      deq = deque()
      deq.append([i, j])
      number = board[i][j]
      distBoard = distDictionary[number]
      while deq:
        r, c = deq.popleft()
        dist = distBoard[r][c]
        for v in range(4):
          newRow = r + dy[v]
          newColumn = c + dx[v]

          if newRow < 0 or newRow >= N or newColumn < 0 or newColumn >= N:
            continue

          if board[newRow][newColumn] == 0:
            if distBoard[newRow][newColumn] == 0:
              distBoard[newRow][newColumn] = dist + 1
              deq.append([newRow, newColumn])

            if distBoard[newRow][newColumn] > dist + 1:
              distBoard[newRow][newColumn] = dist + 1
              deq.append([newRow, newColumn])
          else:          
            if board[newRow][newColumn] != number:
              minDistance = min(minDistance, dist)
              break

  return minDistance

N = int(sys.stdin.readline())
board = []

for i in range(N): 
  board.append(list(map(int, sys.stdin.readline().split())))

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

countGround = splitGround()

print(calculateMinDistance(countGround))

1. Board 배열을 만들고 각 구역별로 넘버링을 다르게 붙였습니다.
2. 완전 탐색을 통해서 각 출발지로부터 다른 구역까지의 거리를 모두 구해본 후 최솟값을 return 하도록 합니다.
3. 이때 이미 방문했던 바다(0)지역에 표시를 하지 않는다면 반복적인 계산이 일어날 수 있습니다.
4. 따라서 거리를 나타내는 새로운 배열 distBoard를 만든 후 각 구역별로 해서 다른 구역까지의 거리들을 저장하면서 반복적인 계산이 일어나지 않도록 합니다.

처음에는 다음과 같은 흐름으로 문제를 풀었습니다. 그런데 각 구역별로 distance의 값들을 다르게 저장하고 있어야 하므로 distdictionary를 지정하고 구역별로 distBoard 배열을 구별해서 저장하는 방식을 사용했습니다.

결과는..?

메모리초과

채점을 하고 나서는 당연하게 느껴지는 것이 100X100 크기의 배열을 여러개 구별해서 사용하다보면 메모리 초과가 나는 것이 당연합니다.. ㅎㅎ

⭕️ 재귀함수를 이용한 풀이

import sys
from collections import deque

def splitGround():
  numbering = 2
  for i in range(N):
    for j in range(N):
      if visited[i][j] != 1:
        continue 
      deq = deque()
      deq.append([i, j])
      visited[i][j] = numbering
      while deq:
        r, c = deq.popleft()
        for v in range(4):
          newRow = r + dy[v]
          newColumn = c + dx[v]

          if newRow < 0 or newRow >= N or newColumn < 0 or newColumn >= N:
            continue

          if visited[newRow][newColumn] == 1:
            visited[newRow][newColumn] = numbering
            deq.append([newRow, newColumn])
      
      numbering += 1

def calculateMinDistance(depth):
  dist = 100001
  for r in range(N):
    for c in range(N):
      if board[r][c] != depth:
        continue 
      numbering = visited[r][c]
      for v in range(4):
        newRow = r + dy[v]
        newColumn = c + dx[v]

        if newRow < 0 or newRow >= N or newColumn < 0 or newColumn >= N:
          continue

        if board[newRow][newColumn] == 0:
          board[newRow][newColumn] = depth + 1
          visited[newRow][newColumn] = numbering
        if board[newRow][newColumn] == depth and visited[newRow][newColumn] != numbering:
          dist = min(dist, (depth-1) * 2)
          
        if board[newRow][newColumn] == depth-1 and visited[newRow][newColumn] != numbering:
          dist = min(dist, board[newRow][newColumn] + depth -2)
  if dist != 1001:
    return dist
  return calculateMinDistance(depth + 1)
N = int(sys.stdin.readline())
board = []
visited = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N): 
  board.append(list(map(int, sys.stdin.readline().split())))

for i in range(N):
  for j in range(N):
    if board[i][j] == 1:
      visited[i][j] = 1 

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

splitGround()
print(calculateMinDistance(1))

메모리 초과를 해결하기 위해서 방법을 수정했습니다.
bfs를 이용하기 보다는 재귀함수를 이용해서 각 영역에서 재귀함수 반복마다 영역을 넓혀가는 방법을 취했습니다.

1. board, vistited 배열을 두가지 이용해서 board 배열에서는 distance를 표현하기 위해서 각 구역을 구분하지 않고 1칸씩 영역을 넓혀갑니다.
2. 영역을 넓히던 도중 다른 구역의 영역을 만날경우 두 지역을 연결하는 다리의 크기를 구할 수 있게됩니다.
3. 이때 서로 다른 구역이라는 것을 인지해야하기 때문에 vistited 배열을 이용해서는 영역을 넓힐때마다 자신의 영역이라는 것을 넘버링을 통해서 표시했습니다.

도움이 되었던 반례

5
1 0 0 0 0
1 0 0 0 1
1 1 1 0 1
0 0 0 0 0
0 0 0 1 0

정답: 1

5
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 0 0 1

정답: 2