[백준] 2146 다리 만들기 (파이썬)

골드 Ⅲ

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

2146번: 다리 만들기

 

📄 문제

• 여러 섬으로 이루어진 나라가 있다.
• 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다.
• 하지만, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고,
• 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
• 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 적은 다리를 말한다.

 

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

 

---

💡 아이디어

• 지도를 탐색하며 해안가를 찾는 함수가 필요하다. (BFS)
  • BFS, 너비우선 탐색을 활용한다.
  • 동서남북 4방향으로 방문체크를 하면서 섬을 탐색한다.
  • 단, 섬이 여러 개 존재하므로 섬에 번호를 매겨 섬 번호로 방문 체크를 해준다
  • 섬과 맞닿아 있는 바다를 만나면 바다의 위치를 저장한다.
• 해안가에서 다른 섬까지의 최소 거리를 찾는 함수가 필요하다.
  1. BFS, 너비우선 탐색
  2. 두 점 사이의 거리 찾기
• 각 섬에서 다른 섬까지의 최소 거리를 구하여 출력한다.

 

---

해안가에서 다른 섬까지의 최소 거리를 찾는 함수를 2가지 방법으로 구현할 수 있다.

같은 맥락을 가진 같은 아이디어지만 구현방법에 따른 속도 차이가 궁금하여 3가지 방법으로 구현해 보았다.

 

🟩 첫 번째 아이디어 (BFS 탐색 - 거리를 2차원 배열에 저장)

• 거리를 저장할 2차원 배열을 만들어준다. (dist)
• 즉, 섬을 탐색했는지 확인하는 visited와 거리를 저장하는 dist이 각각 존재한다.
• 각 섬의 해안가 좌표를 deque에 넣어준다.
• 4방향 탐색을 하면서 바다를 만나면 이전 이동 거리 +1을 하여 이동 거리를 저장한다.
• 출발한 섬과 다른 섬을 만나면 거리를 반환한다.

 

🟩 두 번째 아이디어 (BFS 탐색 - 거리를 deque에 같이 저장)

• 각 섬의 해안가 좌표와 출발 섬에서 거리를 deque에 넣어준다. (행, 열, 거리)
• 4방향 탐색을 하면서 visited에 각 섬의 번호를 활용하여 방문체크를 한다.
• 각 섬의 번호로 방문 체크를 하게 되면 dist을 여러 개 생성할 필요 없이 visited 하나로 해결이 가능하다.
  • 예를 들어, 해당 섬 번호가 3이면
  • 해당 섬은 해안가를 찾는 함수에서 모두 3으로 방문 체크가 되어있다.
  • 방문 체크가 3으로 되어있지 않은 길을 탐색하면서
  • 다른 섬을 만나게 될 경우와 바다를 만나게 될 경우를 구분하여 구현한다.

• 바다를 만나게 될 경우 새로운 위치와 현재까지 이동 거리 +1을 다시 deq에 넣어준다.
• 출발한 섬과 다른 섬을 만나게 될 경우 현재까지의 거리를 반환해 준다.

 

✅ 세 번째 아이디어 (두 점 사이의 거리로 최단 거리 찾기) - 최종코드

• 지도를 탐색하여 해안가를 찾을 때, 섬을 구분하여 각 섬의 해안가를 모두 저장한다.
• 서로 다른 두 섬을 선택한다.
• 서로 다른 두 섬의 해안가들 사이의 거리를 모두 비교하며 최소거리를 구한다.

 

📝 문제 풀이 (Code)

1. 두 점 사이의 거리로 최단 거리 찾기

from collections import deque
import sys
input = sys.stdin.readline

# 1. 각 섬의 해안가 모두 찾기 (bfs)
def findCoast(i, j):
    # 해안가 위치 저장 (바다와 맞닿은 섬 위치 저장)
    coast = set()
    stack = [(i,j)]
    # 섬 방문 체크 (섬 번호로 방문 체크)
    visited[i][j] = 1

    while stack:
        i, j = stack.pop()

        for k in range(4):
            ni = i + di[k]
            nj = j + dj[k]
            if 0 <= ni < n and 0 <= nj < n and visited[ni][nj] == 0:
                # 바다면, 바다와 맞닿은 섬 위치 저장
                if ocean[ni][nj] == '0':
                    coast.add((i,j))
                else:
                    # 섬이면 방문 체크
                    visited[ni][nj] = 1
                    stack.append((ni,nj))
    return coast


# 2. 해안가에서 다른 섬해안가 까지 최단거리 찾기
def findMindist(a, b):
    global minV
    # a 섬의 해안가 위치
    for r1, c1 in island[a]:
        # b 섬의 해안가 위치
        for r2, c2 in island[b]:
            # 각 섬의 해안가 사이 거리 구하기
            size = abs(r1-r2) + abs(c1-c2) - 1
            # 최단 거리 구하기
            minV = min(minV,size)
            # 최단 거리가 1이면 종료
            if minV == 1:
                print(1)
                exit()


n = int(input()) 
ocean = [input().split() for _ in range(n)]
visited = [[0]*n for _ in range(n)]

di = [0,1,0,-1]
dj = [1,0,-1,0]
minV = 10000
# 섬에 번호를 붙여 구분한다.
island = []
for i in range(n):
    for j in range(n):
        # 방문 안한 섬이면
        if ocean[i][j] == '1' and visited[i][j] == 0:
            # 해당 섬의 해안가 찾기
            coast = findCoast(i, j)
            island.append(list(coast))

m = len(island)
for a in range(m-1):
    for b in range(a+1, m):
        # 섬 2개씩 선택
        findMindist(a,b)

print(minV)

 

2. BFS 탐색 - 거리를 deque에 같이 저장

from collections import deque

# 1. 해안가 찾기 (bfs)
def findCoast(i, j):
	# 해안가 위치 저장 (섬과 맞닿은 바다 위치 저장)
    coast = set()
    stack = [(i,j)]
    # 섬 방문 체크
    visited[i][j] = islandNum

    while stack:
        i, j = stack.pop()

        for k in range(4):
            ni = i + di[k]
            nj = j + dj[k]
            if 0 <= ni < n and 0 <= nj < n and visited[ni][nj] != islandNum:
                # 섬이면 방문 체크, 해안가에 맞닿은 바다도 미리 방문체크
                visited[ni][nj] = islandNum
                # 바다면 섬과 맞닿아 있는 바다면 위치, 다리 길이 개수 1로 초기화 하여 저장
                if ocean[ni][nj] == '0':
                    coast.add((ni, nj, 1))
                else:
                    stack.append((ni,nj))
    return coast


# 2. 해안가에서 다른 섬해안가 까지 최단거리 찾기
def bfs(coast):
    # 거리 저장
    deq = deque(coast)

    while deq:
        x, y, dist = deq.popleft()

        if dist >= minV:
            return 10000

        for k in range(4):
            nx = x + di[k]
            ny = y + dj[k]
            # 구역안에 들어오고, 탐색을 시작하는 섬에서 방문 안했으면 탐색
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] != islandNum:
                # 바다면 탐색
                if ocean[nx][ny] == '0':
                    visited[nx][ny] = islandNum
                    deq.append((nx, ny, dist+1))
                else:
                    # 섬 만나면 거리 반환
                    return dist


n = int(input())
ocean = [input().split() for _ in range(n)]
visited = [[0]*n for _ in range(n)]

di = [0,1,0,-1]
dj = [1,0,-1,0]
minV = 10000
# 섬에 번호를 붙여 구분한다.
islandNum = 0
for i in range(n):
    for j in range(n):
        # 방문 안한 섬이면
        if ocean[i][j] == '1' and visited[i][j] == 0:
            islandNum += 1
            # 해당 섬의 해안가 찾기
            coast = findCoast(i, j)
            # 최단 거리 찾기
            minV = min(minV, bfs(coast))
            if minV == 1:
                print(1)
                exit()
print(minV)

 

3. BFS 탐색 - 거리를 2차원 배열에 저장

from collections import deque

# 1. 해안가 찾기 (bfs)
def findCoast(i, j):
    # 해안가 위치 저장 (섬과 맞닿은 바다 위치 저장)
    coast = set()
    stack = [(i,j)]
    # 섬 방문 체크 (섬 번호로 방문 체크)
    visited[i][j] = islandNum

    while stack:
        i, j = stack.pop()

        for k in range(4):
            ni = i + di[k]
            nj = j + dj[k]
            if 0 <= ni < n and 0 <= nj < n and visited[ni][nj] == 0:
                # 바다면, 섬과 맞닿은 바다 위치 저장
                if ocean[ni][nj] == '0':
                    coast.add((ni,nj))
                else:
                    # 섬이면 방문 체크
                    visited[ni][nj] = islandNum
                    stack.append((ni,nj))
    return coast

# 2. 해안가에서 다른 섬해안가 까지 최단거리 찾기
def bfs(coast):
    # 거리 저장
    dist = [[0]*n for _ in range(n)]
    deq = deque(coast)
    # 해안가 1으로 초기화
    # 섬과 맞닿은 첫번째 바다
    for x, y in deq:
        dist[x][y] = 1

    while deq:
        x, y = deq.popleft()

        # 최소 거리보다 크면 탐색을 종료한다.
        if dist[x][y] >= minV:
            return 10000

        for k in range(4):
            nx = x + di[k]
            ny = y + dj[k]
            # 구역안에 들어오고, 방문안했고, 탐색을 시작하는 섬이 아니면 탐색
            if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] == 0 and visited[nx][ny] != islandNum:
                # 바다면 탐색
                if ocean[nx][ny] == '0':
                    dist[nx][ny] = dist[x][y] + 1
                    deq.append((nx,ny))
                else:
                    # 섬 만나면 거리 반환
                    return dist[x][y]


n = int(input())
ocean = [input().split() for _ in range(n)]
visited = [[0]*n for _ in range(n)]

di = [0,1,0,-1]
dj = [1,0,-1,0]
minV = 10000
# 섬에 번호를 붙여 구분한다.
islandNum = 0
for i in range(n):
    for j in range(n):
        # 방문 안한 섬이면
        if ocean[i][j] == '1' and visited[i][j] == 0:
            islandNum += 1
            # 해당 섬의 해안가 찾기
            coast = findCoast(i, j)
            # 최단 거리 찾기
            minV = min(minV, bfs(coast))
print(minV)