[백준] 2146번 : 다리 만들기

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

2146번: 다리 만들기

너비우선탐색(BFS)로 문제를 해결하였습니다. 문제의 요점은 다리의 최소길이를 구해야하는 문제임으로 BFS탐색을 사용하였습니다.

1. BFS 탐색으로 각각의 섬 그룹핑하기

2. BFS 탐색으로 각각의 섬에서 다른섬까지의 최소길이 구하기

 

각각의 섬을 BFS 탐색을 통하여 그룹핑을 하였습니다. 저는 각 섬을 1번 2번 3번... N번으로 라벨링하여 섬을 구분하였습니다.

def byGroup(i,j):
    global groupLabel
    groupLabel += 1
    
    graph[i][j] = groupLabel
    visited[i][j] = True
    queue = deque()
    queue.append((i,j))
    while queue:
        y,x = queue.popleft()
        for dy, dx in move:
            ny = dy + y
            nx = dx + x
            if N > ny >=0 and N > nx >= 0 and graph[ny][nx] != 0: # 바다가 아니라면 그룹핑을 한다.
                if not visited[ny][nx]:
                    graph[ny][nx] = groupLabel
                    visited[ny][nx] = True
                    queue.append((ny, nx))

각각의 섬을 라벨링 한뒤 자신의 그룹이 아닐때 방문하여 최소거리를 구하였습니다.

최소값이 초기에 구해진다면 앞으로 탐색을 더 하지 못하도록 막아야합니다.

바다가 아니라면 섬간의 길이가 나옵니다.

def getDistance(i,j):
    global min_distance
    visited[i][j] = True
    queue = deque()
    queue.append((i,j, 0))
    myGroup = graph[i][j]
    while queue:
        y,x, cost = queue.popleft()
        for dy, dx in move:
            ny = dy + y
            nx = dx + x
            if N > ny >=0 and N > nx >= 0 and graph[ny][nx] != myGroup: # 자기자신의 그룹이 아니라면 방문하여
                if not visited[ny][nx]:
                    visited[ny][nx] = True
                    if graph[ny][nx] == 0 and min_distance > cost + 1: # 바다라면 계속 방문한다. 앞으로 방문해도 더 작은 값이라면 방문가능
                        queue.append((ny, nx, cost + 1))
                    elif graph[ny][nx] != 0:
                        min_distance = min(cost, min_distance)

 

 

전체코드

INF = int(10e9)
from collections import deque
from pprint import pprint
move = ((1,0), (-1,0), (0,1), (0,-1))
N = int(input())

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
    

def getDistance(i,j):
    global min_distance
    visited[i][j] = True
    queue = deque()
    queue.append((i,j, 0))
    myGroup = graph[i][j]
    while queue:
        y,x, cost = queue.popleft()
        for dy, dx in move:
            ny = dy + y
            nx = dx + x
            if N > ny >=0 and N > nx >= 0 and graph[ny][nx] != myGroup: # 자기자신의 그룹이 아니라면 방문하여
                if not visited[ny][nx]:
                    visited[ny][nx] = True
                    if graph[ny][nx] == 0 and min_distance > cost + 1: # 바다라면 계속 방문한다. 앞으로 방문해도 더 작은 값이라면 방문가능
                        queue.append((ny, nx, cost + 1))
                    elif graph[ny][nx] != 0:
                        min_distance = min(cost, min_distance)

def byGroup(i,j):
    global groupLabel
    groupLabel += 1
    
    graph[i][j] = groupLabel
    visited[i][j] = True
    queue = deque()
    queue.append((i,j))
    while queue:
        y,x = queue.popleft()
        for dy, dx in move:
            ny = dy + y
            nx = dx + x
            if N > ny >=0 and N > nx >= 0 and graph[ny][nx] != 0: # 바다가 아니라면 그룹핑을 한다.
                if not visited[ny][nx]:
                    graph[ny][nx] = groupLabel
                    visited[ny][nx] = True
                    queue.append((ny, nx))


visited = [[False for _ in range(N)] for _ in range(N)]
groupLabel = 0
for i in range(N):
    for j in range(N):
        if graph[i][j] != 0 and not visited[i][j]:
            byGroup(i,j)

min_distance = INF

for i in range(N):
    for j in range(N):
        visited = [[False for _ in range(N)] for _ in range(N)]
        if graph[i][j] != 0 and not visited[i][j]:
            
            getDistance(i,j)
            
print(min_distance)