파이썬으로 풀어보는 백준 17472번: 다리 만들기 2 (삼성 A형 기출 문제)

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

17472번: 다리 만들기 2

 

 

내 풀이:

def issafe (y, x):
    global N, M
    if 0 <= y <= N-1 and 0 <= x <= M-1:
        return True
    else:
        return False
 
 
def check_island(i, j, island_num):
    global N, M
    s = [(i, j)]
    arr[i][j] = island_num
    edge = []
 
    while s:
        y, x = s.pop()
        edge_check = False
 
        for dirc in range(4):
            ny = y + dy[dirc]
            nx = x + dx[dirc]
 
            if issafe(ny, nx):
                if arr[ny][nx] == 1:
                    arr[ny][nx] = island_num
                    s.append((ny, nx))
                elif arr[ny][nx] == 0:
                    edge_check = True
        if edge_check:
            edge.append((y, x))
 
    island_edge.append(edge)
 
 
def check(lst):
    global island_num
    road_map = [[0] * island_num for _ in range(island_num)]
    res = 0
    for y, x in lst:
        road_map[y][x] = bridge_info[y][x]
        road_map[x][y] = bridge_info[x][y]
        res += bridge_info[y][x]
 
    visited = [False] * island_num
    s = [2]
    visited[2] = True
    while s:
        i = s.pop()
        for j in range(2, island_num):
            if road_map[i][j] and not visited[j]:
                s.append(j)
                visited[j] = True
    for i in range(2, island_num):
        if not visited[i]:
            return 10000
    return res
 
 
def choose(idx, lst):
    global island_num, roads_num, ans
    if len(lst) == island_num-3:
        ans = min(ans, check(lst))
        return
    if idx == roads_num:
        return
 
    lst.append(roads[idx])
    choose(idx+1, lst)
    lst.pop()
    choose(idx+1, lst)
 
 
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
island_edge = [[],[]]
island_num = 2
 
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            check_island(i, j, island_num)
            island_num += 1
bridge_info = [[0] * island_num for _ in range(island_num)]
 
for idx in range(2, island_num):
    for y, x in island_edge[idx]:
        for dirc in range(4):
            ny = y + dy[dirc]
            nx = x + dx[dirc]
            if issafe(ny, nx):
                cnt = 0
                while arr[ny][nx] == 0:
                    cnt += 1
                    ny += dy[dirc]
                    nx += dx[dirc]
                    if not issafe(ny, nx):
                        cnt = 0
                        break
                if cnt >= 2:
                    if bridge_info[idx][arr[ny][nx]]:
                        bridge_info[idx][arr[ny][nx]] = min(bridge_info[idx][arr[ny][nx]], cnt)
                        bridge_info[arr[ny][nx]][idx] = bridge_info[idx][arr[ny][nx]]
                    else:
                        bridge_info[idx][arr[ny][nx]] = cnt
                        bridge_info[arr[ny][nx]][idx] = cnt
 
roads = []
for i in range(2, island_num):
    for j in range(i+1, island_num):
        if bridge_info[i][j]:
            roads.append((i, j))
roads_num = len(roads)
ans = 10000
choose(0, [])
if ans == 10000:
    print(-1)
else:
    print(ans)

Python3, 56ms

아는 알고리즘만을 이용하는 문제에서는 크게 어려움을 느낀 적이 없었는데 이번 문제는 생각보다 매우 까다로웠다. 문제를 풀기 위해서 사전 작업이 필요하였고 처리해줘야 할 것이 많다고 느껴졌다. 가다듬으면 조금 줄어들지도 모르겠지만 당장에는 변수도 정말 많고 리스트도 많이 활용하여 꽤 이해하기 어려운 코드가 되어버렸다. 가장 먼저 해준 일은 각 섬에 넘버링(라벨링)을 해준 것이다. 문제에서 주어진 지도 정보에서 섬을 1로 처리해주었기 때문에 섬의 번호를 2번부터 시작하여 지도를 바꿔주었다. 그 다음으로 해준 작업은 각각의 섬끼리 다리를 연결할 수 있을 때 가장 짧은 다리의 길이를 알아내는 것이었다. 섬의 라벨링을 해줄 때 섬의 테두리를 미리 island_edge에 저장해두어 같은 일을 반복하지 않을 수 있었다. 각 섬에 대한 가장 짧은 다리 길이를 bridge_info에 저장해두고 (섬 갯수)-1 에 해당하는 다리의 길이를 선택해주었다. (위의 island_num은 섬을 라벨링해줄 이용한 변수를 그대로 사용해주었기 때문에 섬 갯수가 아닌 섬 갯수 + 2 값을 갖는다.) 선택된 다리들로 모든 섬이 연결되는지 check함수로 검토 후 최종 답을 출력해주었다.

 

이용해야하는 알고리즘이 많아 다소 까다롭고 시간이 오래 걸리는 문제였던 것 같다. 이럴줄 알았으면 손으로 써가며 문제를 풀어봤을텐데 바로 코딩으로 옮겨 조금 더 헤멘 느낌이다.