[Swift] 프로그래머스 2018 Summer/Winter Coding 배달

 

Problem

 

코딩테스트 연습 - 배달

---

Solution

 

해당 문제는 한 정점에서의 거리만 구하면 되기 때문에 다익스트라 알고리즘으로 풀어야 하는 문제다.

 

(플로이드로 풀면 효율적이진 않지만 풀리긴 풀린다...)

 

다익스트라 풀이

 

1.모든 거리를 저장할 이차원 배열을 만들어줌.

 

(allDistances 변수를 참고해주세요!)

 

2.다익스트라로 시작하는 정점에서 가장 가까운 거리를 찾아줌.

 

(dijkstra 함수를 참고해주세요!)

 

4.1과 연결된 정점 중 주어진 시간 이하인 것을 찾음

 

(findEnableDelivery 함수를 참고해주세요!)

---

플로이드 와샬 풀이

 

1.모든 거리를 저장할 이차원 배열을 만들어줌.

 

(allDistances 변수를 참고해주세요!)

 

2. road에 있는 정보를 allDistances에 넣어줌

 

(setConnections 함수를 참고해주세요!)

 

3.floyd warshall로 각 정점에서 가장 짧은 거리를 찾음

 

(floyd 함수를 참고해주세요!)

 

4.1과 연결된 정점 중 주어진 시간 이하인 것을 찾음

 

(findEnableDelivery 함수를 참고해주세요!)

---

Source Code

 

다익스트라 풀이

 

	import Foundation
	func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
	//마을이 하나라면 자기 자신밖에 안되므로 1을 반환
	if N == 1 { return 1 }
	var allDistances = Array(repeating: Int.max, count: N+1)
	//시작값으 1으로 다익스트라 시작
	dijkstra(allDistances: &allDistances ,road:road,start:1,n:N)
	//배달할 수 있는 마을의 갯수를 반환
	return findEnableDelivery(n: N, allDistances: allDistances, k: k)
	}
	//k보다 작거나 같은 마을을 반환함.
	func findEnableDelivery(n:Int,allDistances:[Int],k:Int) -> Int {
	return allDistances.filter{$0 <= k}.count
	}
	//다익스트라로 시작 정점에서 가장 가까운 거리로 업데이트해줌.
	func dijkstra(allDistances:inout [Int],road:[[Int]],start:Int,n:Int) {
	//자기 자신과의 거리는 0
	allDistances[start] = 0
	//시작 인덱스를 담은 큐를 만들어줌.
	var queue:[Int] = [start]
	//큐가 모두 없어질때까지 반복
	while !queue.isEmpty {
	//큐의 가장 첫번째 값을 저장하면서 삭제해줌.
	let first = queue.removeFirst()
	//road에서 가장 첫번째 값이 있는 것들로 필터링 해줌.
	let filter = road.filter{$0[0] == first || $0[1] == first}
	//필터링한 것들을 순회
	for f in filter {
	//첫번째 값이 아닌 것을 other로 설정
	let other = f[0] == first ? f[1] : f[0]
	//만약 Int 최댓값이라면 continue
	if allDistances[first] == Int.max {continue}
	//첫번째 값에 거리를 더한 것이 원래 있는 값보다 작다면
	if allDistances[first]+f[2] < allDistances[other] {
	//첫번째 값에 거리를 더한 것으로 업데이트
	allDistances[other] = allDistances[first]+f[2]
	//다른 인덱스를 큐에 넣어줌.
	queue.append(other)
	}
	}
	}
	}

view raw 배달.swift hosted with ❤ by GitHub

 

플로이드 와샬 풀이

 

	import Foundation
	func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
	//마을이 하나라면 자기 자신밖에 안되므로 1을 반환
	if N == 1 { return 1}
	//모든 거리를 저장
	var allDistances = Array(repeating: Array(repeating: Int.max, count: N+1), count: N+1)
	//모든 연결을 세팅
	setConnection(n:N,connections: road, allDistances: &allDistances)
	//플로이드로 가장 짧은 거리를 찾음
	floyd(n: N, allDistances: &allDistances)
	//배달 가능한 마을을 반환
	return findEnableDelivery(n: N, allDistances: allDistances, k: k)
	}
	//k보다 작거나 같은 마을을 반환함.
	func findEnableDelivery(n:Int,allDistances:[[Int]],k:Int) -> Int {
	return allDistances[1].filter{$0 <= k}.count
	}
	//모든 연결을 저장
	func setConnection(n:Int,connections:[[Int]],allDistances:inout[[Int]]) {
	//자기 자신은 0으로 처리
	for i in 1...n {
	allDistances[i][i] = 0
	}
	//만약 연결된 도로가 2개 이상이라면 더 작은 거리를 넣어줌.
	for connection in connections {
	allDistances[connection[0]][connection[1]] = min(allDistances[connection[0]][connection[1]],connection[2])
	allDistances[connection[1]][connection[0]] = min(allDistances[connection[1]][connection[0]],connection[2])
	}
	}
	//플로이드로 가장 짧은 거리를 넣어줌.
	func floyd(n:Int,allDistances:inout [[Int]]) {
	for i in 1...n {
	for j in 1...n {
	for k in 1...n {
	if allDistances[j][i] == Int.max || allDistances[i][k] == Int.max { continue }
	if allDistances[j][i] + allDistances[i][k] < allDistances[j][k] {
	allDistances[j][k] = allDistances[j][i] + allDistances[i][k]
	}
	}
	}
	}
	}

view raw 배달.swift hosted with ❤ by GitHub