알고리즘 유형 : 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) 풀이 요약 (내 풀이)
-
이 문제는 모든 섬을 연결해야하고, 그 때 사용된 다리 길이의 합이 최소가 되고자하므로, MST 문제이다.
이 문제에서의 핵심은 간선을 구하는 것인데, 간선을 구할 때 고려해야 할 사항이 많아 코드가 조금 복잡해진다.
-
먼저 해야할 것은 섬에 번호를 부여하는 것이다. 크루스칼을 돌릴 때 유니온 파인드를 활용하는데, 각 섬을 노드로 취급하여 트리 자료구조를 만들기 위해, 섬에 번호를 부여하고 그 섬에 해당하는 좌표들을 그룹핑해야한다.
지도 전체를 순회하면서 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
-
그 다음으로 해야할 것은 간선 찾기이다.
두 섬을 짝을 짓는 모든 경우의 수를 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)
- 이제 크루스칼을 돌리면 된다. 진행 후, find 함수를 통해 모든 노드의 루트 노드가 하나로 동일한지 검사하고, 그 여부에 따라 -1 또는 res를 출력해주면 된다.
SOLVE 2 풀이 요약 (다른 사람 코드를 참고한 풀이)
-
1번 풀이와 단계는 같다.
1) 섬에 번호 부여하고 각 섬에 속하는 좌표들 그룹핑하기
2) MST 후보 간선 구하기
3) 크루스칼 실행
-
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 이상인지의 여부로 판단)
- 고려할 점이 많아 복잡한 문제였다. 그래도 스스로 풀만은 한 문제였던 것 같다.
