[백준 17472 파이썬] 다리 만들기 2 (골드 1, MST)

배코딩·2022년 8월 3일
0

PS(백준)

목록 보기
106/118

알고리즘 유형 : MST
풀이 참고 없이 스스로 풀었나요? : 테스트 케이스 참고

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




SOLVE 1

내 풀이

import sys
input = sys.stdin.readline

# 유니온 파인드
def find(x):
    if parent[x] < 0:
        return x
    
    parent[x] = find(parent[x])
    return parent[x]
    
def union(a, b):
    root_a = find(a)
    root_b = find(b)
    
    if root_a == root_b:
        return False
    
    if parent[root_a] < parent[root_b]:
        parent[root_b] = root_a
    elif parent[root_a] > parent[root_b]:
        parent[root_a] = root_b
    else:
        parent[root_a] = root_b
        parent[root_b] -= 1
    
    return True

# DFS에 활용할 제너레이터
def move(x, y, N, M):
    if N > 1:
        if 0 < x < N-1:
            yield (x-1, y)
            yield (x+1, y)
        elif x == 0:
            yield(x+1, y)
        else:
            yield(x-1, y)
    
    if M > 1:
        if 0 < y < M-1:
            yield (x, y-1)
            yield (x, y+1)
        elif y == 0:
            yield(x, y+1)
        else:
            yield(x, y-1)

# 섬마다 고유 번호를 주기 위한 DFS
# 값이 1인(=섬인) 모든 좌표에, 속한 섬의 번호와 그 좌표의 x, y 값을 튜플로 저장
def DFS(x, y, num, N, M):
    visited[x][y] = True
    island[-1].append((num, x, y))
    for adj_x, adj_y in move(x, y, N, M):
        if board[adj_x][adj_y] == 1 and visited[adj_x][adj_y] == False:
            DFS(adj_x, adj_y, num, N, M)

N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append([*map(int, input().split())])

visited = [[False]*M for _ in range(N)]
edges = [] # MST 후보 간선들을 담을 리스트
island = [] # 섬 별로 좌표를 그룹핑한 리스트를 모아둔 리스트
num = 1 # 섬 번호
for row in range(N):
    for col in range(M):
        if board[row][col] == 1 and visited[row][col] == False:
            island.append([])
            DFS(row, col, num, N, M)
            num += 1

# MST 후보 간선을 찾는 작업
for n1 in range(len(island)-1): # n1번째 섬
    for n2 in range(n1 + 1, len(island)): # n2번째 섬
        candidates = [] # n1섬과 n2섬 사이의 모든 간선을 구해서 여기에 저장할거임
        for num1, x1, y1 in island[n1]: # n1섬 위의 좌표 한 점
            for num2, x2, y2 in island[n2]: # n2섬 위의 좌표 한 점
                if x1 == x2 and abs(y1 - y2) - 1 > 1: # x축 기준 동일선상에 있고, y값의 차의 절댓값이 2 이상이여야 함
                    # 만약 x축 기준 동일선상에서, 두 좌표 사이의 좌표들 중에 값이 1인게 있으면
                    # 이 두 좌표 사이에는 다리를 놓을 수 없음
                    if y1 < y2 and sum(board[x1][y1+1:y2]) > 0:
                        continue
                    elif y1 > y2 and sum(board[x1][y1-1:y2:-1]) > 0:
                        continue
                    candidates.append(abs(y1 - y2) - 1)
                if y1 == y2 and abs(x1 - x2) - 1 > 1:
                    if x1 < x2 and sum([board[nx][y1] for nx in range(x1+1, x2)]) > 0:
                        continue
                    elif x1 > x2 and sum([board[nx][y1] for nx in range(x1-1, x2, -1)]) > 0:
                        continue
                    candidates.append(abs(x1 - x2) - 1)
        if candidates:
            edges.append((min(candidates), n1 + 1, n2 + 1)) # n1섬과 n2섬 사이 간선 중 최소 가중치 간선을 MST 후보 간선으로 저장

# 크루스칼
edges.sort()
parent = [-1]*(len(island)+1)
res = 0
for w, x, y in edges:
    if union(x, y):
        res += w

# 만약 크루스칼 실행 후 모든 섬이 연결되어 있지 않다면 -1 출력
isMST = True
for i in range(1, len(island)):
    if find(i) != find(i+1):
        isMST = False

if isMST == False:
    print(-1)
else:
    print(res)


SOLVE 2

다른 사람 코드를 참고한 풀이

import sys
from collections import deque
input = sys.stdin.readline

# 유니온 파인드
def find(x):
    if parent[x] < 0:
        return x
        
    parent[x] = find(parent[x])
    return parent[x]
    
def union(a, b):
    root_a = find(a)
    root_b = find(b)
    
    if root_a == root_b:
        return False
    
    if parent[root_a] < parent[root_b]:
        parent[root_b] = root_a
    elif parent[root_a] > parent[root_b]:
        parent[root_a] = root_b
    else:
        parent[root_a] = root_b
        parent[root_b] -= 1
    
    return True

# 상하좌우로 한 칸 이동
def move():
    yield (-1, 0)
    yield (1, 0)
    yield (0, -1)
    yield (0, 1)

# BFS로 섬 마다 번호 부여하고, 각각의 섬에 속하는 좌표들을 그룹핑
def BFS(start_x, start_y, island_num):
    visited[start_x][start_y] = True
    q = deque([(start_x, start_y)])
    island_search[(start_x, start_y)] = island_num
    island_cdns.append((island_num, start_x, start_y))
    
    while q:
        x, y = q.pop()
        
        for dx, dy in move():
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < M:
                if board[nx][ny] == 1 and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    island_search[(nx, ny)] = island_num
                    island_cdns.append((island_num, nx, ny))
                    q.appendleft((nx, ny))

N, M = map(int, input().split())
board = []

for _ in range(N):
    board.append([*map(int, input().split())])

visited = [[False]*M for _ in range(N)]
island_search = dict() # 어떤 좌표가 어느 섬에 속하는지 조회
island_cdns = [] # 땅인 모든 좌표들
island_num = 0 # 섬 번호 붙일 때 사용(모두 붙이고 나면, 이 변수는 총 섬의 개수를 의미)

for row in range(N):
    for col in range(M):
        if board[row][col] == 1 and visited[row][col] == False:
            island_num += 1
            BFS(row, col, island_num)

edges = [] # MST 후보 간선들 모아놓는 리스트

# MST 후보 간선 모으는 코드
# 모든 땅 좌표를 순회하면서, 상하좌우 네 방향으로 모두 뻗어나가서,
# 다른 섬과 다리 건설이 가능하면 그 간선을 edges에 저장
for num, x, y in island_cdns:
    for dx, dy in move():
        nx = x + dx
        ny = y + dy
        dist = 0 # 다리 길이 기록
        island_fin = None # 다른 섬 도착 여부와 도착한 섬의 번호를 의미
        
        while True:
            # 방문한 땅이 같은 섬에 속한 땅일 경우 이 방향은 다리 건설 불가능
            if island_search.get((nx, ny)) == num:
                break
            
            # 방문하려는 좌표가 지도를 벗어날 때 break 해주기
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                break
            
            # 방문한 땅이 다른 섬에 속한 땅일 때
            if island_search.get((nx, ny)) != None and island_search.get((nx, ny)) != num:
                island_fin = island_search.get((nx, ny))
                break
            
            nx += dx
            ny += dy
            dist += 1
        
        # 기록한 길이가 2 이상이고, 다른 섬에 도착한 경우
        if dist >= 2 and island_fin != None:
            edges.append((dist, num, island_fin))

edges.sort(reverse=True)
parent = [-1]*(island_num+1)
cnt = island_num-1
res = 0

# N-1개의 유효한 간선을 사용하여 MST를 만들 때까지 반복
while cnt:
    # 만약 모든 간선을 다 pop했는데도 아직 MST를 만들지 못한 경우
    try:
        w, n1, n2 = edges.pop()
    except:
        res = -1
        break
    
    if union(n1, n2):
        res += w
        cnt -= 1

print(res)



SOLVE 1) 풀이 요약 (내 풀이)

  1. 이 문제는 모든 섬을 연결해야하고, 그 때 사용된 다리 길이의 합이 최소가 되고자하므로, MST 문제이다.

    이 문제에서의 핵심은 간선을 구하는 것인데, 간선을 구할 때 고려해야 할 사항이 많아 코드가 조금 복잡해진다.


  1. 먼저 해야할 것은 섬에 번호를 부여하는 것이다. 크루스칼을 돌릴 때 유니온 파인드를 활용하는데, 각 섬을 노드로 취급하여 트리 자료구조를 만들기 위해, 섬에 번호를 부여하고 그 섬에 해당하는 좌표들을 그룹핑해야한다.

    지도 전체를 순회하면서 DFS를 돌아서, 값이 1인 좌표의 좌표값과 소속 섬 번호를 같이 튜플로 island 리스트에 넣어준다.

    for row in range(N):
      for col in range(M):
          if board[row][col] == 1 and visited[row][col] == False:
              island.append([])
              DFS(row, col, num, N, M)
              num += 1

  1. 그 다음으로 해야할 것은 간선 찾기이다.

    두 섬을 짝을 짓는 모든 경우의 수를 for로 돌면서, 두 섬 각각의 모든 좌표에 대해, 두 좌표 사이에 다리를 세울 수 있는지를 검토하고 세울 수 있는 경우 MST의 간선 후보 리스트 edges에 넣어준다.

    어떤 두 섬의 각 좌표 사이에 다리를 놓을 수 있는지 검토할 때, 고려해야 할 조건은

    1) 다리는 바다 위에만 놓을 수 있다.

    2) 다리 길이가 2 이상이여야 한다.

    3) 다리는 가로 방향 또는 세로 방향이여야만 한다. 중간에 휘면 안됨

    4) 다리 양 끝에 땅이 있어야된다.

    if x1 == x2 and abs(y1 - y2) - 1 > 1: # x축 기준 동일선상에 있고, y값의 차의 절댓값이 2 이상이여야 함
      # 만약 x축 기준 동일선상에서, 두 좌표 사이의 좌표들 중에 값이 1인게 있으면
      # 이 두 좌표 사이에는 다리를 놓을 수 없음
      if y1 < y2 and sum(board[x1][y1+1:y2]) > 0:
        continue
      elif y1 > y2 and sum(board[x1][y1-1:y2:-1]) > 0:
        continue
      candidates.append(abs(y1 - y2) - 1)
    if y1 == y2 and abs(x1 - x2) - 1 > 1:
      if x1 < x2 and sum([board[nx][y1] for nx in range(x1+1, x2)]) > 0:
        continue
      elif x1 > x2 and sum([board[nx][y1] for nx in range(x1-1, x2, -1)]) > 0:
        continue
      candidates.append(abs(x1 - x2) - 1)

  1. 이제 크루스칼을 돌리면 된다. 진행 후, find 함수를 통해 모든 노드의 루트 노드가 하나로 동일한지 검사하고, 그 여부에 따라 -1 또는 res를 출력해주면 된다.


SOLVE 2 풀이 요약 (다른 사람 코드를 참고한 풀이)

  1. 1번 풀이와 단계는 같다.

    1) 섬에 번호 부여하고 각 섬에 속하는 좌표들 그룹핑하기

    2) MST 후보 간선 구하기

    3) 크루스칼 실행


  1. 1번 풀이와 다른 점은 섬의 좌표들을 그룹핑하는 방식과 간선을 구하는 방식이다.

    이 풀이에서는 BFS로 섬을 그룹핑하면서, 땅의 좌표와 소속 섬 번호를 튜플로 리스트에 저장하고, 땅의 좌표로 소속 섬 번호를 조회할 수 있는 딕셔너리를 만든다.

    딕셔너리를 만드는 이유는 간선을 구하는 방식에서 알 수 있다.


edges = [] # MST 후보 간선들 모아놓는 리스트

# MST 후보 간선 모으는 코드
# 모든 땅 좌표를 순회하면서, 상하좌우 네 방향으로 모두 뻗어나가서,
# 다른 섬과 다리 건설이 가능하면 그 간선을 edges에 저장
for num, x, y in island_cdns:
    for dx, dy in move():
        nx = x + dx
        ny = y + dy
        dist = 0 # 다리 길이 기록
        island_fin = None # 다른 섬 도착 여부와 도착한 섬의 번호를 의미
        
        while True:
            # 방문한 땅이 같은 섬에 속한 땅일 경우 이 방향은 다리 건설 불가능
            if island_search.get((nx, ny)) == num:
                break
            
            # 방문하려는 좌표가 지도를 벗어날 때 break 해주기
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                break
            
            # 방문한 땅이 다른 섬에 속한 땅일 때
            if island_search.get((nx, ny)) != None and island_search.get((nx, ny)) != num:
                island_fin = island_search.get((nx, ny))
                break
            
            nx += dx
            ny += dy
            dist += 1
        
        # 기록한 길이가 2 이상이고, 다른 섬에 도착한 경우
        if dist >= 2 and island_fin != None:
            edges.append((dist, num, island_fin))

이 코드는 MST 후보 간선을 구하는 코드이다.

우선 for문으로 모든 땅의 좌표를 순회한다. 각각의 땅 좌표에 대해, 상하좌우 4방향으로 뻗어나가서 다리 건설이 가능한지를 조사한다.

그 방식을 살펴보면, 다리 건설 가능 여부가 확실해질 때까지 특정 방향으로 한 칸씩 이동하는 것을 반복한다.

while문 안에서 다리 건설 가능 여부를 조건문으로 판단한다. 마주친 땅이 같은 섬에 속한 땅이거나, 좌표 자체가 지도 범위를 벗어나거나, 기록한 길이가 2 미만이면 다리 건설이 불가능하다.

반면 방문한 땅이 다른 섬에 속한 땅이면 다리 건설이 가능한 경우이므로, 이 경우에 island_fin에 도착한 땅의 소속 섬 번호를 기록하고, while문을 벗어나서 기록한 다리 길이 dist와 출발 섬, 도착 섬 번호를 튜플로 edges에 append 해준다.

이 후 크루스칼을 실행해주면 MST 비용을 구할 수 있다.






배운 점, 어려웠던 점

  • 처음에 푼 풀이가 계속 WA가 떠서 테스트 케이스를 검색해보고 실행해보고 문제점을 발견하여 수정 후 AC를 받았다.

    처음에 푼 풀이는 다리 건설 가능 여부를 판단하는 부분에서, 출발 땅 좌표에서 진행 방향 바로 다음 칸에 1이 나오면 다리 건설이 불가능한 것으로 판단했었는데,

    10111001
    01000001

    이 경우에서, 왼쪽 섬의 좌측상단 좌표에서 오른쪽 방향 바로 다음 칸이 0이다. 하지만 이 좌표와 오른쪽 섬 사이에 다리를 놓는 것은 불가능하다.

    이 경우를 해결하기 위해, 출발 섬의 땅과 도착 섬의 땅 사이에 땅이 하나라도 존재한다면 다리 건설이 불가능한 것으로 판단하는 코드로 수정했다. (출발과 도착 사이의 값들의 sum 값이 1 이상인지의 여부로 판단)


  • 고려할 점이 많아 복잡한 문제였다. 그래도 스스로 풀만은 한 문제였던 것 같다.
profile
PS, 풀스택, 앱 개발, 각종 프로젝트 내용 정리 (https://github.com/minsu-cnu)

0개의 댓글