[프로그래머스] 배달 & 합승 택시 요금 (with 플로이드 와샬)

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

배달 & 합승 택시 요금 모두 "플로이드 와샬" 알고리즘으로 풀이할 수 있어 같이 알아보고자 한다. 

 

플로이드 와샬 알고리즘이란, "모든 정점"에서 "모든 정점"으로의 최단 경로를 구하는 방식이다. 

아래 사진을 통해 이해해보자.

 

Floyd Warshall

W 행렬의 행(i)과 열(j)를 각각의 노드(동그라미)라고 해보자. 즉, (1,2)는 0 -> 1로 가는 경우의 값을 말하는 것이다. (index 값이기에 -1씩 해주고 생각하기) 해당하는 값이 3이기에 알맞는 위치에 값을 입력해가면서 행렬을 채우게 된다. 바로 갈 수 없는 경우에 무한대 표시로 하여 갈 수 없음을 나타내준다. 대신 거쳐서라도 갈 수 있는 경우가 존재할 경우 해당 값을 무한대 대신 채워넣어준다. 

즉 직접적으로 갈 수 있는 경우, 간접적으로 거쳐서 가는 경우 중 최솟값을 해당 위치에 적어주면 되는 것이다. 

 

// k = 거쳐가는 지점 
// i = 출발 지점 
// j = 도착 지점 
// n = 노드의 수 
// arr = 2차원 배열

// arr[i][j] = 바로 가는 경우 
// arr[i][k] + arr[k][j] = 거쳐서 가는 경우 

for k in 0..<N {
    for i in 0..<N {
        for j in 0..<N {
            // 거쳐가는 값들은 재귀적으로 구해진다 
            arr[i][j] = min(arr[i][k] + arr[k][j], arr[i][j])
        }
    }
}

이것이 가장 핵심이 되는 알고리즘이다. 모든 출발지 ~ 도착지까지의 최단 경로를 구해주는 행렬로 나타내주기에, 문제의 상황에 맞게 행렬에서 값을 골라내면 된다. 

 

1. 배달 

위 예시와 마찬가지로 그래프로 주어져있다. 다만 일방향이 아닌 양방향에서 접근이 가능한 상황이다. 이 점을 유의하여 진행해야한다. 

 

프로그래머스 - 배달 

road라는 2차원 배열이 주어지는데, 배열의 원소는 [출발,도착,시간] 으로 구성되어있다. 

위의 예시와 동일하게 모든 지점 > 모든 지점의 최단 경로를 구하고, 해당 문제의 경우 1번에서 출발했을 때 K시간 이내에 접근 가능한 곳을 추리는 문제이기에 조건을 걸어주고 카운팅해주면 된다. 

 

import Foundation

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    // 본인은 항상 가능하기에 1로 초기 세팅
    var answer = 1
    // 배달 가능한 시간인 K가 500,000이하이기에
    let maxNum = 5000001
    
    // 노드 개수만큼, 최댓값으로 초기화 해두고 시작
    var dist : [[Int]] = (0..<N).map { _ in Array(repeating: maxNum, count: N) }
    
    // 본인 -> 본인은 시간 소요 : 0 
    for i in 0..<N {
        dist[i][i] = 0
    }
    
    // 각 노드마다 연결
    for r in road {
        // 출발점
        let s = r[0] - 1
        // 도착점
        let e = r[1] - 1
        // 소요 시간
        let v = r[2]
        
        // 두 지점을 잇는 여러 길이 있을 수 있기에 최소값 저장을 위해 값 비교
        // s,e가 존재한다는 건 갈 수 있다는 것이기에 INF값을 대체해야함
        if dist[s][e] > v || dist[s][e] == maxNum {
            dist[s][e] = v
            dist[e][s] = v
        }
    }
    
    func fw() {
        // k는 거쳐가는 지점
        for k in 0..<N {
            // i는 출발
            for i in 0..<N {
                // j는 도착
                for j in 0..<N {
                    dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])
                }
            }
        }
    }
    
    fw()

	// 1번에서 출발이기에 2번 도착 케이스부터 확인 
    for i in 1..<N {
    	// 시간 내일 경우
        if dist[0][i] <= k {
            answer += 1
        }
    }
    return answer
}

 

[ 프로세스 ] 

 

1. 최댓값 설정 

2. 최댓값으로 이루어지는 N x N 크기의 2차원 배열 생성 ( N : 노드의 개수 )

3. 본인 -> 본인 : 0으로 설정

4. 주어진 정보를 활용하여 N x N 배열에 연결 정보 표시 (여러 노선이 존재함을 고려하여 조건걸고 진행)

5. 플로이드 와샬 

6. 본인 이외의 케이스에서 K보다 적은 개수를 카운트 

 

여기서 조금 더 시간을 줄이고자 할 경우, 플로이드 와샬 알고리즘 내에섯 2가지 케이스를 고려하여 제외해주면 된다. 

 

1. 출발지와 거쳐가는 지점, 거쳐가는 지점과 도착 지점과 같은 경우 

2. 출발 -> 거쳐가는 지점의 값이 최댓값 (즉, 갈 수 없는 경우)인 경우 

 

func fw() {
        // i는 거쳐가는
        for i in 0..<N {
            // j는 출발
            for j in 0..<N {
            	// 1,2번 케이스
                if dist[j][i] == maxNum || j == i {
                    continue
                }
                // k는 도착
                for k in 0..<N {
                    // 1번 케이스
                    if j == k || i == k {
                        continue
                    }
                    dist[j][k] = min(dist[j][i] + dist[i][k], dist[j][k])
                }
            }
        }
    }

이처럼 예외 케이스를 뛰어넘도록 해서 시간복잡도를 줄일 수 있다. 

 

2. 합승 택시 요금 

두 명의 사람이 한 지점에서 출발하여 택시를 타고 각자의 집에 갈 때 일부 합승하는게 저렴한지, 따로 가는게 저렴한지 구하는 문제. 

 

프로그래머스 - 합승 택시 요금 

이 문제 또한 이동 방향이 정해져있지 않은 쌍방향으로의 이동이 가능한 상황이다. 

 

A와 B가 S지점에서 같이 출발하여 가장 저렴하게 이동할 수 있는 방법은 무엇이 될까? 

배달 문제에서는 시간이었고, 이제는 비용이다. 마찬가지로 높을 수록 좋은게 아니기에 동일하게 접근하면 되겠다. 

 

4에서 6으로 가는 경우를 봐보자. 

 

4 -> 6 : 50

4 -> 1 -> 6 : 35

4 -> 1 -> 5 -> 6 : 36

 

바로 가는 방법 뿐만 아니라 중간에 "거쳐서" 가는 경우도 존재하며, 해당 경우가 최소한의 비용을 발생시키는 케이스일 수 있다. 

앞서 플로이드 와샬이 "거쳐가는" 경우도 고려한다고 했던 점에 착안하여 이 문제도 동일한 알고리즘으로 풀이될 수 있다. 

 

import Foundation

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
	// 지점의 개수 * 요금 = 즉 모든 지점을 돌 경우 나올 수 있는 값을 최댓값으로 설정
    let maxval = 200 * 100000
    // 최대값으로 이루어진 2차원 배열 생성
    var arr = (0..<n).map {_ in Array(repeating: maxval, count : n)}
    
    // 본인 -> 본인 케이스 최소값으로 
    for i in 0..<n {
        arr[i][i] = 0
    }
    
    // 연결정보 2차원 배열에 반영 
    for f in fares {
    	// 두 지점 간 요금은 무조건 1개 이기에 최솟값 비교하지 않고 값만 할당하면 됨. 
        arr[f[0] - 1][f[1] - 1] = f[2]
        arr[f[1] - 1][f[0] - 1] = f[2]

    }
    
    for i in 0..<n {
        for j in 0..<n {
        	// 위의 케이스 1,2 제외 
            if arr[j][i] == maxval || i==j {
                continue
            } else {
                for k in 0..<n {
                	// 위의 케이스 1 제외
                    if j == k || i == k {
                        continue
                    } else {
                        arr[j][k] = min(arr[j][i]+arr[i][k], arr[j][k])
                    }
                }
            }            
        }
    }
    
    // 이제 비교해야하는 건 "각자 출발" VS "합승을 조금이라도 하는 경우" 
    // 각자 출발 = arr[s-1][a-1] + arr[s-1][b-1]
    // 조금이라도 합승 = arr[s-1][i] + arr[i][a-1] + arr[i][b-1]
    
    var minval = arr[s-1][a-1] + arr[s-1][b-1]
    
    for i in 0..<n {
        let share = arr[s-1][i]
        // 출발지가 A의 집일 경우 0 
        let start = i == a-1 ? 0 : arr[i][a-1] 
        // 출발지가 B의 집일 경우 0         
        let end = i == b-1 ? 0 : arr[i][b-1]
        
        // 두 케이스 비교하여 최소값 할당
        minval = min(minval, share + start + end)
    }

    return minval
}

[ 프로세스 ] 

 

1. 최댓값 설정

2. 최댓값으로 이루어지는 N x N 크기의 2차원 배열 생성 ( N : 노드의 개수 )

3. 본인 -> 본인 : 0으로 설정

4. 주어진 정보를 활용하여 N x N 배열에 연결 정보 표시 (노선이 1개만 존재하는 점 유의)

5. 플로이드 와샬 

6. 합승하여 거쳐가는 경우 VS 바로 가는 경우 비교 

7. 최소값 반환

 

플로이드 와샬 뿐만 아니라, "하나의 정점에서 다른 모든 정점까지의 최단 경로"를 구하는 다익스트라나 벨만포드도 학습해봐야겠다!

 

 

ref : nsios.tistory.com/140?category=899499 

[Swift Algorithm] 72413 합승 택시 요금 (2021 카카오 블라인드)

(알고리즘 풀이에 도움을 많이 받고 있는 블로그...!🙏🏻)