[2021 Kakao Blind Recruitment] 합승 택시 요금

문제 접근

하나의 출발지점 s에서 a와 b 두 도착지점에 대해 '최단 경로'를 찾는다고 생각하고 풀었다. 그림도 그래프로 주어졌고, 요금이 간선의 가중치라고 생각하고 최단 경로 알고리즘을 찾아보았다.

• 노드(지점)의 개수가 최대 200개로 적은 숫자이며 fares배열의 크기도 최대 2이상, 19900이하이다.
• 음수 가중치는 존재하지 않는다
• 탐색 경우의 수를 3가지로 가정해봤다

  1. s에서 출발해 합승 지점에서 흩어지는 경우
  2. 합승지점에서 a로 가는 경우
  3. 합승지점에서 b로 가는 경우

• 따라서, 최종 요금은 's->k + k->a + k->b'이다.

1트 (플로이드 와샬)

def solution(n, s, a, b, fares):
    INF = int(1e6)   
    answer = INF 

    # 2차원 리스트(그래프)를 만들고, 무한으로 초기화
    graph=[[INF]*(n) for _ in range(n)]


    # 자기 자신에서 자기 자신으로 가는 비용은 0 으로 초기화
    for i in range (n):
         graph[i][i]=0


    # 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
    for info in fares:
        # c - d 사이 요금을 f라고 설정. 양방향 간선
        c,d,f= info
        graph[c-1][d-1]=f
        graph[d-1][c-1]=f

    # 점화식에 따라 플로이드 워셜 알고리즘을 수행
    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])


    # 노드 s에서 출발해 a,b각각에 대한 최소 요금 경로를 계산
    # 최종 요금 = a+b 합동요금 + a 요금 + b 요금
    for i in range(n):
        cost = graph[s-1][i] + graph[i][a-1] + graph[i][b-1]
        answer = min(answer, cost)

    return answer

2트 성공

질문하기에서 효율성 테스트 케이스가 통과하지 않는 예시를 찾고 INF를 1e7로 수정했다.
최대 요금이 1e6이라 대충 통과할 줄 알았는데, 아무래도 안되나 보다.

def solution(n, s, a, b, fares):
    INF = int(1e7)   
    answer = INF 

    # 2차원 리스트(그래프)를 만들고, 무한으  로 초기화
    graph=[[INF]*(n) for _ in range(n)]


    # 자기 자신에서 자기 자신으로 가는 비용은 0 으로 초기화
    for i in range (n):
         graph[i][i]=0


    # 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
    for info in fares:
        # c - d 사이 요금을 f라고 설정
        c,d,f= info
        graph[c-1][d-1]=f
        graph[d-1][c-1]=f

    # 점화식에 따라 플로이드 워셜 알고리즘을 수행
    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])


    # 노드 s에서 출발해 a,b각각에 대한 최소 요금 경로를 계산
    # 최종 요금 = a+b 합동요금 + a 요금 + b 요금
    for i in range(n):
        cost = graph[s-1][i] + graph[i][a-1] + graph[i][b-1]
        answer = min(answer, cost)

    return answer

자바스크립트 코드

function solution(n, s, a, b, fares) {
    INF = Number(1e7)
    let answer = INF;
    let graph = new Array(n).fill().map(_ => new Array(n).fill(Infinity));

    for (let i=0; i<n; i++) graph[i][i] = 0;

      fares.forEach(info => {
        const [c, d, f] = info;
        graph[c-1][d-1] = f;
        graph[d-1][c-1] = f;
      }); 
 
    for (let k=0; k<n; k++){
        for(let i=0; i<n; i++){
            for(let j=0; j<n; j++){
                graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }  
 
    for (let i=0; i<n; i++){
        cost = graph[s-1][i] + graph[i][a-1] + graph[i][b-1]
        answer = Math.min(answer, cost)
    }


    return answer;
}

파이썬대신 js로 프론트 코테에 대비해보자.
근데 신기한건 효율성 테스트에서 통과 시간이 파이썬에 비해 매우 빠르다.

비고

알고리즘 공부 참고한 블로그
옛날에 그래프 탐색 알고리즘을 공부했던 터라 요약 블로그로 다시 복습했다.

정답 스포** 접근법 참고하기 좋은 글