[Python] 백준 2146번 - 다리 만들기 (bfs, dfs 풀이)

문제: https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

문제를 보고 각 육지의 테두리에 있는 좌표들만 모아서 좌표들끼리 최단거리를 비교하며 최소값을 찾아가야겠다고 생각을 했다.

처음에는 bfs로 육지가 나올 때 마다 주변 4방향을 탐색하여 바다와 인접하는 경우에만 리스트에 담으며 테두리 좌표값을 구했다.

코드는 다음과 같다.

from collections import deque

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*n for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    side = set()
    q = deque()
    q.append((x, y))
    flag = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0:
                flag = 1
    if flag == 1:
        side.add((x, y))
        
    while q:
        x, y = q.popleft()
        visited[x][y] = 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1 and not visited[nx][ny]:
                q.append((nx, ny))
                for j in range(4):
                    nnx = nx + dx[j]
                    nny = ny + dy[j]
                    if 0 <= nnx < n and 0 <= nny < n and board[nnx][nny] == 0:
                        side.add((nx, ny))
    return side
    
islands = []
for x in range(n):
    for y in range(n):
        if board[x][y] == 1 and not visited[x][y]:
            temp = bfs(x, y)
            islands.append(list(temp))

combinations = []
answer = 1e9
for i in range(0, len(islands)-1):
    for j in range(i+1, len(islands)):
        for c1 in islands[i]:
            for c2 in islands[j]:
                temp_val = (abs(c2[0] - c1[0]) + abs(c2[1] - c1[1])) - 1
                if temp_val < answer:
                    answer = temp_val

print(answer)

문제는 이렇게 풀면 예제에 대한 답은 다 맞지만, 메모리 초과가 발생한다..!

 

좌표마다 4방향 메모리를 전부 열어 매번 확인하는 과정에서 메모리 낭비가 발생한다고 생각했다.

따라서 메모리를 많이 잡아먹는 bfs대신 dfs를 활용하여 풀어보았다.

import itertools
import sys
sys.setrecursionlimit(10000)

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*n for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):
    visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and board[nx][ny] == 1:
            dfs(nx, ny)
        elif 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and board[nx][ny] == 0:
            temp.add((x, y))
          
islands = []
for x in range(n):
    for y in range(n):
        if board[x][y] == 1 and not visited[x][y]:
            temp = set()
            dfs(x, y)
            islands.append(list(temp))

combinations = []
answer = 1e9
for i in range(0, len(islands)-1):
    for j in range(i+1, len(islands)):
        for c1, c2 in list(itertools.product(islands[i], islands[j])):
            temp_val = (abs(c2[0] - c1[0]) + abs(c2[1] - c1[1])) - 1
            if temp_val < answer:
                answer = temp_val

print(answer)

dfs로 푸니 코드도 훨씬 짧아지고 가독성이 좋은 것 같다.

 

if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and board[nx][ny] == 1:
    dfs(nx, ny)
elif 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and board[nx][ny] == 0:
    temp.add((x, y))

육지의 4방향에 대해서 육지인경우 해당 좌표에 대해 dfs를 돌고, 바다인 경우 배열에 추가해주었다.

이때 배열은 set 자료형으로 주어서 좌표가 겹치지 않도록 해주었다.

 

for i in range(0, len(islands)-1):   
    for j in range(i+1, len(islands)):       
        for c1, c2 in list(itertools.product(islands[i], islands[j])):
            temp_val = (abs(c2[0] - c1[0]) + abs(c2[1] - c1[1])) - 1           
            if temp_val < answer:
                answer = temp_val

모인 테두리 좌표들에 대해서는 itertools의 product를 사용해 조합을 만들어주었다.

Product는 combination, permutations와 다르게 2개 이상의 리스트에 대해서 조합을 만들어준다.
(DB의 join 연산 처럼)

현재 코드에서는 islands리스트 내의 i번째 리스트와 j번째 리스트를 조합하여 (i번째 섬, j번째 섬) 테두리들 간의 거리를 계산할 수 있도록 한다.