백준 2146 다리 만들기

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

예제 입력 1 복사

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1 복사

3

 

 

많은 반성을 하게 되는 문제였다. 어떻게 구현할지 감을 잡아도, 코드 작성이 꽤 걸렸고, 계속해서 착오에 빠졌다. 

그럼에도 해결해내서 다행이지만 나는 골드 3은 힘들게 푸는 정도구나.. 싶었다. 앞으로 갈길이 멀다. 

그래도 bfs가 손에 많이 익어져서 다행이다. 

 

풀이 방법: 

1) 해당 문제는 각 섬이 다른 섬이란걸 표기하는 것부터 시작이다. 구분이 되지 않으면 출발섬과 도착섬이 같은 경우 최단 거리를 1로 오인한다. 

2) 섬의 외각을 출발지점으로 잡는다. 섬 내부에서 출발을 하는건 효율적이지 않을 뿐더러 여기가 바다인지 육지인지, 혹은 같은 섬인지 구분해야 할 것이 많아져서 복잡해진다. 

3) 모든 외각의 출발지점에서 bfs를 한다. 처음에 착각한 것이 각 외각의 지점들을 모두 queue에 집어넣은 후 각 지점에서 동시 출발을 시키면 어떨까 생각을 했다. 이건 한 섬에서 출발하는 경우에는 문제가 되지 않을 것으로 보이나 서로 다른 섬에서 출발하게 되면 서로 오다가 겹쳐버리는 문제가 발생한다. 시도는 안해봤지만 각 섬의 순서를 나누되, 섬 하나마다는 동시 출발하게 하면 시간적으로 많이 이득이 있지 않을까 싶다. 

 

특이사항: 섬의 외각을 먼저 찾아서 리스트에 넣은 후, 리스트에서 하나씩 꺼내서 bfs를 하는 것보다 

섬의 외각을 찾으면 바로 bfs를 수행하는 것이 시간적으로 공간적으로 이득으로 보임에도 

		2146	맞았습니다!!	230964	3636	PyPy3 / 수정	1813	10분 전
		2146	맞았습니다!!	230140	3308	PyPy3 / 수정	1730	24분 전

풀이 결과 오히려 시간 공간 모두 악화되는 결과가 나왔다. 왤까? 

아그리고 이 문제는 visit 을 새로 생성할 필요가 없다. 섬이 이미 visit 이므로 매번 생성하지말고 그냥 인풋값을 visit array로 사용하면 된다. 

import sys 
input = sys.stdin.readline
import copy
n = int(input())
from collections import deque

square = [list(map(int, input().split())) for _ in range(n) ]
visited = [row[:] for row in square] 
tmp = [row[:] for row in square] 
lst = []
q = deque()
dx, dy = [1, -1, 0, 0], [0,0, 1, -1]

island = 2


for i in range(n):
    for j in range(n):      
        if square[i][j] == 1:
            square[i][j] = island
            q.append((i,j))

            while q:
                y,x = q.popleft()
                for k in range(4):
                    nx, ny = x + dx[k], y + dy[k]
                    if 0 <= nx < n and 0 <= ny < n and square[ny][nx] != 0 and square[ny][nx] != island:
                        square[ny][nx] = island
                        q.append((ny,nx))
            island += 1

#print(*square)

for i in range(n):
    for j in range(n):
        for k in range(4):
            nx = j + dx[k]
            ny = i + dy[k]
            if 0 <= nx < n and 0 <= ny <n and square[ny][nx] == 0 and square[i][j] !=0: #  
                lst.append((i,j, square[i][j]))
                break

answer = 1e9


for start in lst:
    visited = [row[:] for row in tmp]
    q.append(start)
    while q:
        y,x,location = q.popleft()
        for k in range(4):
            nx, ny = x + dx[k] , y + dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                if visited[ny][nx] == 0:    
                    visited[ny][nx] = visited[y][x] + 1
                    q.append((ny, nx, location))

                elif location != square[ny][nx] and visited[ny][nx] == 1: 
                    #print(square[ny][nx])
                    answer = min(answer, visited[y][x])



print(answer-1)

그리고 python3 로는 시간초과가 난다. pypy3 를 쓰자.