[프로그래머스Lv.3] 등산코스정하기(파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

문제유형

그래프 탐색문제.

방향이 없는 그래프이니깐

그래프를 초기화할 때 양쪽 전부 방향을 넣어주자

 

처음에 문제를 접근했던 풀이

1. gate,봉우리를 설정하면서 bfs를 구한다면 시간초과가 뜰 것이다.

2. gate,봉우리를 제외한 지점의 intensity구하기

3. gate지점과 봉우리의 intensity를 구하고, 그 중 가장 큰 값을 받는다

 

반례

위의 예시에서 1-4처럼

봉우리-출입구가 바로 연결되어있다면

위의 풀이는 적용하기 힘듭니다.

 

구글링으로 개선한 풀이

1. 다익스트라를 활용한다

2. 시작점에서 산봉우리까지 한번에 Intensity를 구하고 

그 중 가장 큰 값을 리턴한다

 

코드

from heapq import heappop, heappush


def solution(n, paths, gates, summits):
    answer = [-1, 10000001]
    graph = [[] for _ in range(n + 1)]

    for a, b, c in paths:
        graph[a].append([b, c])
        graph[b].append([a, c])

    # 산봉우리 정렬이 안될 수 있으니 정렬해준다.
    summits.sort()
    summitset = set(summits)
    q = []
    visited = [1e9] * (n + 1)

    # 우선순위 큐에 시작점 다 넣어주기
    # 시작점은 Intensity가 0이라고 가정
    for start in gates:
        heappush(q, (0, start))
        visited[start] = 0

    # 우선순위 큐를 계속 돌려가면서 intensity구하기
    while q:
        nowIntensity, now = heappop(q)

        # 산봉우리에 도착했다면 탐색 중지
        # 산봉우리가 여러개 겹치는 경우가 있어, set을 활용
        if now in summitset:
            continue

        # 지금 intensity가 현재 노드의 intensity보다 크면 탐색중지
        if nowIntensity > visited[now]:
            continue

        for go, time in graph[now]:
            goIntensity = max(nowIntensity, time)
            if goIntensity < visited[go]:
                visited[go] = goIntensity
                heappush(q, (goIntensity, go))

    # 이제 답을 받아주기
    for summit in summits:
        if visited[summit] < answer[1]:
            answer = [summit, visited[summit]]
    #     #1. 출입구, 산봉우리를 제외한 bfs를 해주고 intensitiy를 구함
    #     visited=[False]*(n+1)
    #     roadIntensity=1e9
    #     for i in range(1,n+1):
    #         if i in gates or i in summits:
    #             continue
    #         if visited[i]==True:
    #             continue

    #         q=deque()
    #         q.append(i)
    #         visited[i]=True
    #         while q:
    #             now=q.popleft()

    #             for go,time in graph[now]:
    #                 if visited[go]==True:
    #                     continue

    #                 visited[go]=True
    #                 q.append(go)
    #                 roadIntensity=min(roadIntensity,time)

    #     #print(roadIntensity)

    #     #2.산봉우리의 최소 Intensity구하기
    #     for end in summits:
    #         endIntensity=1e9
    #         for go,time in graph[end]:
    #             if go in summits:
    #                 continue
    #             endIntensity=min(endIntensity,time)
    #         maxIntensity=max(roadIntensity,endIntensity)
    #         for start in gates:
    #             startIntensity=1e9
    #             for go,time in graph[start]:
    #                 if go in gates:
    #                     continue
    #                 startIntensity=min(startIntensity,time)    
    #             print(startIntensity,maxIntensity)
    #             maxIntensity=max(maxIntensity,startIntensity)
    #             if maxIntensity<answer[1]:
    #                 answer=[end,maxIntensity]

    return answer

 

체크 포인트 몇가지

 

1. 굳이 summit을 sort해야하는가?

-->문제에서 "intensity가 같다면 산봉우리 중 가장 번호가 낮은 거 부터"

라는 조건이 있다.

문제에서 summits배열이 번호순이라고 주어지지 않았기 때문에

sort를 해주는 편이 안전하다

 

2. 산봉우리인 걸 확인할 때 굳이 set을 써야하는가?

-->summits배열이 중복이 없다고 말한 적은 없다.

중복을 제거안하면 시간초과가 뜨는 케이스가 생긴다.

"이런 거 까지 생각해야하나"라는 불만도 들지만

문제를 푸는 입장에서는 고려해야할 요소라고 한다면 또 할 말이 없다.