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

문제

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

17472번: 다리 만들기 2

풀이

구현할게 많았던 문제였습니다.

먼저, 저는 BFS를 사용해 섬에 번호를 부여해주었습니다.

그리고 다리를 놓는 방법에 대해서 고민을 했는데, 다리를 놓으려면 섬의 외각에 있어야 합니다.
섬에 외각에 있다는 것은 자신을 중심으로 상, 하, 좌, 우에 한 뱡향이라도 바다가 있으면 섬의 외각이라고 판별하였습니다.

섬의 좌표에서 상 하 좌 우를 확인하고, 바다가 있다면 다리는 직선으로만 이동하기 때문에 해당 방향을 인덱스로 넣어주었습니다.
0, 1, 2, 3 (동 남 서 북) 순으로 넣어주었습니다.

이제 다리를 놓아야 하는데, 그래프를 확인하면서 바다가 아니라면, (현재 x, y 좌표가 0이 아니라면)
위의 인덱스로 넣어준 방향 (바다로 이동하는 방향)으로 다른 섬을 만나거나, 그래프의 범위를 벗어날 때 까지 이동시켜주었습니다.
이동중에 자신과 같은 섬을 만난다면 break 문으로 탈출하였습니다.

다리의 길이는 1 이상이여아 하므로, 2칸 이상 바다를 이동하고 다른 번호의 섬을 만났다면,
출발 노드, 도착 노드, 비용으로 사용하기 위해 출발 섬 번호, 도착 섬 번호, 다리의 길이를 넣어주었습니다.

이제 이 간선들을 확인하면서 크루스칼 알고리즘을 사용하여서 MST를 만들었습니다.
하지만 주의해야 할 점이 있습니다.

MST가 안되는 경우가 있을 수 있습니다. MST를 이루는 간선의 개수는 노드의 개수 - 1 이므로
이를 확인하고 MST가 안된다면 -1을 출력시켜줍시다.

소스코드

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let n = input[0], m = input[1]
	var graph: [[Int]] = []
	var visited = [[Bool]](repeating: [Bool](repeating: false, count: m), count: n)
	let dx = [1, 0, -1, 0]
	let dy = [0, 1, 0, -1]
	for _ in 0..<n {
	graph.append(readLine()!.split(separator: " ").map { Int($0)! })
	}
	func isValidCoord(y: Int, x: Int) -> Bool {
	return 0..<n ~= y && 0..<m ~= x
	}
	/// 현재 좌표에서 상하좌우 확인 후, 바다인 방향 인덱스로 리턴
	/// 0, 1, 2, 3 (동 남 서 북)
	func getBridgeDirections(y: Int, x: Int) -> [Int] {
	var directions: [Int] = []
	for i in 0..<4 {
	let ny = y + dy[i]
	let nx = x + dx[i]
	if !isValidCoord(y: ny, x: nx) {
	continue
	}
	if graph[ny][nx] == 0 {
	directions.append(i)
	}
	}
	return directions
	}
	/// 섬에 번호 부여
	func numberingGrand(y: Int, x: Int, n: Int) {
	var queue = [(y, x)]
	var index = 0
	graph[y][x] = n
	visited[y][x] = true
	while queue.count > index {
	let y = queue[index].0
	let x = queue[index].1
	for i in 0..<4 {
	let ny = y + dy[i]
	let nx = x + dx[i]
	if isValidCoord(y: ny, x: nx) && !visited[ny][nx] && graph[ny][nx] == 1 {
	visited[ny][nx] = true
	graph[ny][nx] = n
	queue.append((ny, nx))
	}
	}
	index += 1
	}
	}
	var groundNumber = 0
	for y in 0..<n {
	for x in 0..<m {
	if graph[y][x] == 1 && !visited[y][x] {
	groundNumber += 1
	numberingGrand(y: y, x: x, n: groundNumber)
	}
	}
	}
	var edges: [(Int, Int, Int)] = []
	/// 해당 좌표에서 다리 놓기
	/// - Parameters:
	/// - y: y 좌표
	/// - x: x 좌표
	/// - groundNumber: 출발 섬 번호
	/// - direction: 다리를 놓는 방향
	/// - depth: 다리의 길이
	func makeBridge(y: Int, x: Int, groundNumber: Int, direction: Int, depth: Int) {
	var queue = [(y, x, direction, depth)]
	var index = 0
	while queue.count > index {
	let y = queue[index].0
	let x = queue[index].1
	let direction = queue[index].2
	let depth = queue[index].3
	if graph[y][x] == groundNumber && depth > 1 {
	break
	}
	if graph[y][x] > 0 && graph[y][x] != groundNumber {
	if depth > 2 {
	edges.append((groundNumber, graph[y][x], depth - 1))
	}
	break
	}
	let ny = y + dy[direction]
	let nx = x + dx[direction]
	if !isValidCoord(y: ny, x: nx) {
	break
	}
	queue.append((ny, nx, direction, depth + 1))
	index += 1
	}
	}
	for y in 0..<n {
	for x in 0..<m {
	if graph[y][x] > 0 {
	let direction = getBridgeDirections(y: y, x: x)
	direction.forEach {
	makeBridge(y: y, x: x, groundNumber: graph[y][x], direction: $0, depth: 0)
	}
	}
	}
	}
	edges.sort { $0.2 <$1.2 }
	var parent = [Int](0...groundNumber)
	func find(_ x: Int) -> Int {
	if parent[x] == x {
	return x
	}
	parent[x] = find(parent[x])
	return parent[x]
	}
	func union(_ a: Int, _ b: Int) {
	let a = find(a)
	let b = find(b)
	if a == b {
	return
	}
	if a > b {
	parent[a] = b
	} else {
	parent[b] = a
	}
	}
	var answer = 0
	var count = 0
	/// 간선을 오름차순으로 확인하면서 최소 비용 구하기
	/// 연결을 이루려면 간선의 개수는 노드개수 -1 임
	/// 간선이 연결되는 것을 count 프로퍼티로 확인
	for edge in edges {
	let a = find(edge.0)
	let b = find(edge.1)
	let cost = edge.2
	if a != b {
	union(a, b)
	answer += cost
	count += 1
	}
	}
	/// 간선의 개수가 노드개수 - 1이 아니라면 연결된 것이 아님. -1 출력
	print(count != groundNumber - 1 ? -1 : answer)

view raw 다리 만들기 2.swift hosted with ❤ by GitHub

후기

푸는데 은근 시간이 오래걸렸던 문제였습니다..
엄청나게 어렵진 않았는데 구현할게 많은 문제였습니다.

예제는 다 맞았는데 계속 틀렸습니다 판정을 받아서 의아했었는데,
MST가 안되는 경우를 제대로 판별하지 못했었던 문제였습니다.