📚 2146 - 다리 만들기

다리 만들기

이해

출력을 보면 가장 짧은 다리의 길이를 출력한다. ➡️ bfs를 사용해라!

전체적으로 돌면서 육지 구간을 나누어야 한다.

• 육지구간 표시를 하자!
• bfs를 돌리면서 연결되어 있는 구간마다 숫자를 주는 것이다. ➡️ 1번 공간이면 1, 2번 공간이면 2, 3번 공간이면 3

구간 나누는데 bfs를 1번, 다리를 연결하는데 bfs를 1번 사용한다. (총 2번)

1번 bfs는 위에 적혀있는 내용을 이용하면 된다.

✔️ 2번 bfs는 ?

• 바다일 경우, 방문한지 안한지 체크해야한다.
• 육지이지만, 현재 인덱스 육지가 아닌 다른 육지를 찾은 경우 거기까지 거리가 우리가 원하는 값이다. (이 값 중에서 가장 작은 값을 출력해야한다.)
  • 육지를 찾으면 바로 나가야한다. (첫 번째로 찾은 육지 지역이 가장 가깝기 때문) bfs는 너비 우선 탐색으로 가장 먼저 찾은 값이 현재 나올 수 있는 다리 길이 중 가장 짧은 다리 길이이다.

소스

from collections import deque
import sys

n = int(sys.stdin.readline())

graph = []
visited = [[False] * n for _ in range(n)]

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

x_coordinate = [-1, 0, 1, 0]
y_coordinate = [0, 1, 0, -1]


def bfs(x, y):
    global count
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    graph[x][y] = count
    while queue:
        cur_x, cur_y = queue.popleft()

        for i in range(4):
            nx = x_coordinate[i] + cur_x
            ny = y_coordinate[i] + cur_y

            if 0 <= nx < n and 0 <= ny < n:
                if visited[nx][ny] or (not graph[nx][ny]):
                    continue

                visited[nx][ny] = True
                graph[nx][ny] = count
                queue.append((nx, ny))


def bfs2(cur_idx):
    # 방문한지 안한지 확인하기 위해
    # dist -1로 초기화
    dist = [[-1] * n for _ in range(n)]
    queue = deque()
    global result

    for i in range(n):
        for j in range(n):
            if graph[i][j] == cur_idx:
                queue.append((i, j))
                dist[i][j] = 0
                # queue에 삽입하고 현재 위치를 0으로

    while queue:
        # 육지지역 좌표를 꺼낸다.
        cur_x, cur_y = queue.popleft()

        for i in range(4):
            nx = x_coordinate[i] + cur_x
            ny = y_coordinate[i] + cur_y

            if 0 <= nx < n and 0 <= ny < n:
                # 육지지역이지만, 현재 인덱스 육지가 아닌 다른 육지일 경우
                if graph[nx][ny] != cur_idx and graph[nx][ny]:
                    result = min(result, dist[cur_x][cur_y])
                    return
                elif dist[nx][ny] == -1 and not graph[nx][ny]:
                    # 방문하지 않은 바다일 경우
                    dist[nx][ny] = dist[cur_x][cur_y] + 1
                    queue.append((nx, ny))

    return result


count = 1

for i in range(n):
    for j in range(n):
        if graph[i][j] and (not visited[i][j]):
            bfs(i, j)

            # 육지 지역 구간 나누기 위해
            count += 1

result = sys.maxsize

# 총 육지 크기 만큼 돌리면서, 해당 인덱스가 1번 육지, 2번 육지 등이 된다.
for i in range(1, count):
    bfs2(i)

print(result)

실행 결과

• 1580ms 시간 걸린 것은 3차원 배열을 사용했을 때 나온 결과이다. (388ms는 위 코드 내용)
• 배열의 크기는 최대한 줄이고, 효율적으로 코드를 만들어야 하는 것 같다.

참고

• https://kyun2da.github.io/2021/04/22/makeBridge/