[파이썬python] 백준 2146번 - 다리 만들기

백준 2146번 다리 만들기 문제를 풀어보겠습니다.

무려 골드 3짜리 문제입니다.

문제를 푼 아이디어와 과정을 자세히 적어봤으니

문제가 이해가 안되셨거나 풀이를 모르겠다하시면 끝까지 집중해주세요!

 

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

2146번: 다리 만들기

문제요약)

위에 동서남북으로 회색칸이 붙어있는 것을 하나의 섬이라고 합니다. (위 그림에선 섬이 3개지요..)

이때 섬을 잇는 다리(빨간색 칸)를 만들려고 할 때 다리의 최소길이를 구하라는 문제입니다. 

 

아이디어) 

1. 각각의 섬을 구별하고, 

2. 각 섬에서 다른 섬까지의 거리의 거리중 최소값을 구하면 되겠다는 생각을 했습니다.

 

문제에서 섬은 모두 1로 입력이 주어집니다.

이차원 평면을 for문으로 돌면서 값이 1인 칸을 찾아 dfs를 돌리고 

같은 섬끼리 라벨링을 하기 위해서 count를 2부터 시작해서 dfs를 돌 때마다 count를 1씩 더해주었습니다.

2	2	2					3	3	3
2	2	2	2					3	3
2		2	2					3	3
		2	2	2					3
			2						3
									3
				4	4
				4	4	4

그러면 위와 같이 섬이 라벨링이 됩니다.

 

그리고 이제 각 섬에서 다른섬까지의 거리 중 최솟값을 구하면 되는데요.

거리의 최솟값은 최단거리로 볼 수 있겠죠.

최단거리는 바로 bfs로 구하면 됩니다.

 

이 문제에서의 bfs에서의 핵심은

• 방문여부를 알 수 있고, 거리도 저장할 수 있는 배열을 만드는 것
• 조건 설정하기 입니다.

True/False로 구성된 배열이 대신 -1을 기본값으로 해서 

방문을 안했다면 -1, 방문을 했다면 0이상인 값으로 방문여부를 구분할 수 있고,

거리를 더해줌으로써 거리도 저장할 수 있습니다.

check = [[-1] * num for _ in range(num)]

먼저 각각 라벨링된 섬의 좌표를 큐에 넣어주고,

    for i in range(num):
        for j in range(num):
            if arr[i][j] == n: #n은 라벨링된 숫자
                q.append((i,j))
                check[i][j] = 0

상하좌우를 돌면서 

1. 범위 밖으로 나가는 경우 제외해주고

2. 다른 섬에 도착한 경우 최솟값을 갱신해주고

3. 바다(0인 칸)이면 거리를 +1 해줍니다.

        for a,b in (0,-1),(0,1),(1,0),(-1,0):
            nx = x+a
            ny = y+b
            if nx < 0 or nx >= num or ny < 0 or ny >= num:
                continue
            #다른 섬에 도착한 경우
            if arr[nx][ny] > 0 and arr[nx][ny] != n:
                ans = min(ans,check[x][y])
                return
            #바다이고, 방문한 적 없다면
            if arr[nx][ny] == 0 and check[nx][ny] == -1:
                check[nx][ny] = check[x][y]+1
                q.append((nx,ny))

모든 큐를 돌게 되면 ans에 최솟값이 저장되어 그대로 출력만 하면 됩니다.

 

정답코드)

import sys
from collections import deque
sys.setrecursionlimit(10**6)

num = int(input())
arr = [list(map(int,input().split())) for _ in range(num)]

ans = sys.maxsize

def dfs(i,j):
    global cnt
    if i < 0 or i >= num or j < 0 or j >= num:
        return False
    if arr[i][j] == 1:
        arr[i][j] = cnt
        for x,y in (0,1),(0,-1),(1,0),(-1,0):
            nx = x+i
            ny = y+j
            dfs(nx,ny)
        return True

def bfs(n):
    global ans
    check = [[-1] * num for _ in range(num)]
    q = deque()

    for i in range(num):
        for j in range(num):
            if arr[i][j] == n:
                q.append((i,j))
                check[i][j] = 0
    while q:
        x,y = q.popleft()
        for a,b in (0,-1),(0,1),(1,0),(-1,0):
            nx = x+a
            ny = y+b
            if nx < 0 or nx >= num or ny < 0 or ny >= num:
                continue
            #다른 섬에 도착한 경우
            if arr[nx][ny] > 0 and arr[nx][ny] != n:
                ans = min(ans,check[x][y])
                return
            #바다이고, 방문한 적이 없다면
            if arr[nx][ny] == 0 and check[nx][ny] == -1:
                check[nx][ny] = check[x][y]+1
                q.append((nx,ny))


cnt = 2
for i in range(num):
    for j in range(num):
        if dfs(i,j) == True:
            cnt+=1

for i in range(2,cnt):
    bfs(i)



print(ans)

 

최댓값을 구할 때는 초기값을 0으로 두면 되지만

최솟값을 구할 때는 초기값을 어떤값으로 정의해야 하는지 매번 문제조건을 확인하기 번거로우셨을 텐데요.

sys라이브러리에 있는 sys.maxsize를 이용하면 편합니다.

 

그럼 도움이 되셨다면 공감과 댓글 그리고 구독을 부탁드립니다.!!