백준 17472. 다리 만들기 2(python)

• 17472. 다리 만들기 2

17472번: 다리 만들기 2

---

입력

• 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다.
• 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다.
• 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다.
• 0은 바다, 1은 땅을 의미한다.

---

문제풀이

• 다리는 중간에 방향이 바뀌지 않고, 다른 다리와 겹칠 수 있다.
• 겹치는 경우에는 해당 칸을 각 다리에 모두 포함시킨다.
• 다리는 섬과 수직하게 만나야한다.
• 각 섬에 번호를 부여하고 연결할 수 있는 다리의 길이를 모두 구한 후
• 유니온 파인드를 이용해 (섬의 수 - 1)개의 다리로 연결될 수 있는 지 체크하는 방식으로 풀이했다.

N, M = [*map(int, input().split())]
visited = [[0]*M for _ in range(N)]
mapp = [0]*N
island_num = 1      # 각 섬에 번호 붙여줄 변수
bridge = []         # 다리 정보 입력할 리스트
cnt = 0
leng_sum = 0

for i in range(N):
    mapp[i] = [*map(int, input().split())]

• 먼저 입력을 받는다.

for i in range(N):
    for j in range(M):
        if mapp[i][j] == 1 and visited[i][j] == 0:  # 방문하지 않은 섬이면
            bfs(i, j, island_num)                   # 탐색하며 번호 붙임
            island_num += 1                         # 다음 섬 위해 번호 1 증가

• bfs 탐색을 하여 각 섬에 순차적으로 번호를 부여한다.
• bfs 함수는 다음과 같다.

def bfs(y, x, num):             # 각 섬에 번호 붙여주기 위한 bfs (num - 섬에 붙여줄 번호)
    queue = deque()
    queue.append((y, x))
    visited[y][x] = 1
    mapp[y][x] = num
    while queue:
        now = queue.popleft()
        for i in range(4):
            ny = now[0] + dy[i]
            nx = now[1] + dx[i]
            if 0 <= ny < N and 0 <= nx < M:
                if visited[ny][nx] == 0 and mapp[ny][nx] == 1:
                    visited[ny][nx] = 1
                    mapp[ny][nx] = num
                    queue.append((ny, nx))

• dy, dx는 방향배열이다.

arr = [-1]*island_num

for i in range(N):
    for j in range(M):
        if mapp[i][j] != 0:     # 섬이면
            connect(i, j)       # 어떤 섬과 다리 놓을 수 있는지 탐색

• 유니온 파인드를 구현하기 위해 어떤 섬과 연결되었는지 체크할 리스트(위 코드의 arr)을 하나 만든다
• 리스트의 길이는 위에서 구한 섬의 개수이다.
• 또한 각 섬에서 최소 길이의 다리로 어떤 섬과 연결될 수 있는지 체크한다. -> 위의 connect 함수
• connect 함수의 구조는 다음과 같다.

def connect(y, x):          # 다리 연결 정보 생성할 함수
    for i in range(4):
        leng = 1
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < N and 0 <= nx < M:
            if mapp[ny][nx] == 0:       # 만약 주변이 바다(0)라면
                while True:
                    ny += dy[i]         # 같은 방향으로 거리 늘리며
                    nx += dx[i]
                    if 0 <= ny < N and 0 <= nx < M:
                        if mapp[ny][nx] > mapp[y][x]:   # 탐색 시작한 섬보다 번호가 큰 섬 만나면
                            if leng > 1:                # 다리 길이 2 이상일 때
                                bridge.append([mapp[y][x], mapp[ny][nx], leng])     # 다리 연결
                                break
                            break
                        elif mapp[ny][nx] == mapp[y][x]:    # 동일한 섬 만나면 다음 방향 탐색
                            break
                        elif mapp[ny][nx] == 0:             # 바다 만나면
                            leng += 1                       # 다리 길이 +1
                        else:
                            break
                    else:           # 범위 벗어나면 다음 방향 탐색
                        break

• 섬의 한 점이면 connect 함수로 좌표를 넘겨준다. 후에 주변 4칸(상, 하, 좌, 우)를 탐색하여
• 바다가 있다면 거리를 늘리며 다른 섬을 만날 때, 탐색을 시작한 섬을 만날 때 혹은 지도의 범위를 벗어날 때까지 탐색한다.
• 조건에 맞으면 연결된 섬의 번호와 다리 길이를 기록한다.

if len(bridge) <= island_num - 3:   # 다리 수가 부족하면 연결 불가
    print(-1)
else:
    bridge = sorted(bridge, key=lambda x:x[2])  # 다리 길이 오름차순으로 정렬
    for i in bridge:
        if findboss(i[0]) != findboss(i[1]):    # 두 섬이 이어져 있지 않으면
            leng_sum += i[2]                    # 다리 길이 합산
            union(i[0], i[1])                   # 연결 표시
            cnt += 1                            # 다리 개수 증가
        if cnt == island_num-2:                 # 다리 개수가 (섬 수)-1이면 연결 완료
            break
    if cnt == island_num-2:         # 연결 완료 시
        print(leng_sum)             # 다리 길이 합 출력
    else:                           # 그렇지 않으면 -1 출력
        print(-1)

• 위 함수의 결과에서 다리의 수가 최소로 필요한 수를 넘기지 못하면 -1 출력
• 그렇지 않으면 연결될 수 있는지 없는지 검사한다.
• 다리 길이를 기준으로 연결 가능한 정보를 정렬시킨다.
• findboss 함수를 사용하여 두 섬이 연결되어 있으면, 다음 다리로 넘어가고
• 그렇지 않다면, 연결한 후 다리길이를 결과값에 더해준다.
• findboss 함수와 union 함수의 구조는 아래와 같다.

def union(a, b):        # 다리 놓은 섬 묶어줄 함수(동일한 보스를 갖도록)
    fa, fb = findboss(a), findboss(b)
    if fa == fb:
        return
    arr[fb] = fa

def findboss(a):        # 섬의 보스 찾아줄 함수
    if arr[a] == -1:
        return a
    ret = findboss(arr[a])
    arr[a] = ret
    return ret