[백준] 17472 다리만들기2 (Python)

[백준] 17472 다리만들기2 (Python)

반응형

1. 문제 조건

지도는 NxM 이차원 격자(1 <=N, M <=10)

섬은 1, 바다는 0으로 입력 받음(2 <= 섬의 개수 <=6)

다리를 연결해서 모든 섬을 연결하려 하는데, 이때 다리 길이의 최솟값 구하기(불가능하면 -1 출력)

[다리 생성 조건]

-다리 방향은 중간에 바뀔 수 없음

-다리 길이는 2 이상

2. 풀이 전 생각정리

일단 각각의 섬들을 다른 섬으로 식별해야 하기 때문에 2부터 라벨링 해보자 island_num=2로 세팅한 뒤 이중 for문으로 맵 전체를 돌다가 1을 발견하면 DFS로 1이 있는 영역을 다 island_num으로 만들어준 뒤, island_num+=1

섬들을 연결하는 다리에 대한 정보를 길이가 최소인 정보만 남겨서 distance 리스트에 저장 섬의 개수가 최대 6이므로 6*6 이차원 리스트 distance의 모든 요소를 0으로 세팅 다리 생성 조건을 충족시키는 상황이 발생하고, 다리 길이기 기존에 distance에 있는 값보다 작으면 distance에 넣어줌 ex) island_num 2와 3을 연결하는 다리 길이가 2이면 distance [0][1]에 2를 넣어줌(기존 값이 0 혹은 2보다 작은 값일 때)

distance리스트에는 중복 값, 0이 존재하므로 보기 쉽게 [다리 길이, 섬 번호 1, 섬 번호 2]의 형태로 편집 arranged_d = list() distance 리스트를 한 바퀴 돌면서 0이 아닌 값을 발견하면 arranged_d 리스트에 넣어줌 단, arranged_d에 [2,1,2]가 있으면 [2,2,1]은 안 넣어줘도 됨(중복 값이므로)

크루스칼 알고리즘을 이용하여 MST구함

이렇게 했는데도 섬들이 다 연결되지 않았다면 -1을 출력

3. 코드 구현

#map의 크기 -> N행, M열 #다리 조건 -> 방향 바꿀수 없음, 길이 2이상, 교차가능 #육지는 1, 바다는 0 from collections import deque #섬 정보를 2부터 라벨링하는 함수 def labeling(start, mapp, island_num): queue = deque() queue.append(start) while queue: x,y = queue.popleft() mapp[x][y] = island_num for dx, dy in move_list: nx, ny = x+dx, y+dy if 0<=nx=N or ny>=M: break #같은 섬이면 break if mapp[nx][ny] == idx: break #더 나아갈 수 있으면 한번 더 움직이기 if mapp[nx][ny] == 0: nx += dx ny += dy count += 1 continue #벗어나지도 않고, 같은 섬도 아니고, 바다도 아닐 때 -> 다른섬 if count<2: break num = mapp[nx][ny] cost = distance[idx-2][num-2] if cost == 0: distance[idx-2][num-2] = count else: distance[idx-2][num-2] = min(cost, count) break #부모노드 정보 def getParent(idx): if parent[idx] == idx: return idx parent[idx] = getParent(parent[idx]) return parent[idx] #병함 def unionParent(a,b): a = getParent(a) b = getParent(b) if a

반응형

from http://tipsyziasu.tistory.com/123 by ccl(A) rewrite - 2021-08-24 17:00:25