문제 출처: 프로그래머스 (https://school.programmers.co.kr/learn/courses/30/lessons/42861)

문제 설명

🔎n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항
1. 섬의 개수 n은 1 이상 100 이하입니다.
2. costs의 길이는 ((n-1) * n) / 2이하입니다.
3. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
4.같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
5. 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
6. 연결할 수 없는 섬은 주어지지 않습니다.

해당 문제는 프로그래머스의 코딩 테스트 고득점 kit에 있는 문제다.

섬, 연결, 최소 비용이라는 단어를 보자마자 bfs, 다익스트라 등을 생각했고 실제 바로 그리디한 방법이 떠오르지 않아 다익스트라로 먼저 시도했었다.

<틀린 코드 보기>

from queue import PriorityQueue
# 다익스트라 x
def solution(n, costs):
    answer = 0
    island = [[] for _ in range(n)]

    for e1, e2, w in costs:
        island[e1].append((e2, w))
        island[e2].append((e1, w))

    visited = [False] * (n+1)
    dist = [float('inf')] * (n+1)
    q = PriorityQueue()
    q.put((0, 0)) # 최단거리, 노드번호
    dist[0] = 0
    bridge = [0] * (n+1)
    while q.qsize()>0:
        cur_node = q.get()[1]
        if visited[cur_node]: continue

        visited[cur_node] = True

        for nx, val in island[cur_node]:
            if dist[nx] > dist[cur_node] + val:
                dist[nx] = dist[cur_node] + val
                bridge[nx] = val
                q.put((dist[nx], nx))

    print(dist)
    print(bridge)

다익스트라를 통한 구현의 문제점은 아래와 같다.

1. 결국은 모든 costs에 대한 점검을 해야한다.

2. 다익스트라로 구현된 dist 리스트는 시작점부터 해당 노드까지의 비용으로 산정되기 때문에 sum으로 답을 구할 수 없다.

제한 사항에서 섬의 개수(n)은 100이하라고 했고, costs의 길이는 ((n-1) * n) / 2 이라 규정하였으므로, 실제 costs를 전체 도는데만 해도 O(n²) 만큼의 시간이 들기 때문에 1번 문제점은 꽤나 크게 작용하였다.

이후 이 문제가 그리디로 분류되었다는 사실을 다시 한번 깨닫고 아래와 같은 코드를 작성하였다.

<정답 코드>

from collections import deque
def solution(n, costs):
    answer = 0
    costs = sorted(costs, key=lambda x: x[2])
    isl = [[] for _ in range(n)]

    
    for start, end, cost in costs:
        q = deque()
        flag = False
        q.append(start)
        visit = [False] * n
        visit[start] = True
        while q:
            a = q.popleft()
            if a == end:
                visit[a] = True
                flag = True
                break
            
            visit[a] = True
            for i in isl[a]:
                if not visit[i]:
                    q.append(i)
        
        if sum(visit) == n:
            break
        
        if not flag:
            isl[start].append(end)
            isl[end].append(start)
            answer += cost
    
    return answer

접근 방법은 아래와 같다.

1. 가장 낮은 비용의 다리부터 우선적으로 고려한다. (비용을 기준으로 costs를 정렬한다.)

2. 비용을 기준으로 정렬된 costs를 순회하면서, 연결되지 않은 섬에 대해서만 다리를 건설한다.

3. 모든 섬을 방문할 수 있게 되었으면 반복문을 탈출하게 한다.

연결되지 않은 섬을 판단하는 알고리즘으로는 bfs를 사용하였다. 

bfs를 채택할 수 있었던 것은, 다리를 하나씩 건설하기 때문에 bfs를 통한 연산 횟수가 0에서 부터 지수적으로 상승한다는 사실 때문이다.

해당 섬과 연결이 되었는가에 대한 판단은 flag를 통해 진행하였고, 만약 모든 섬을 방문할 수 있게 되었다면 반복문을 탈출하는 것으로 마무리 지었다. 이 부분이 다익스트라에서 모든 costs를 점검해야한다는 부분을 해소할 수 있게 해주었다.

사실 이 문제는 수개월 전에 먼저 도전했다가 실패한 문제이다. 최근에는 그래프나 트리 문제를 많이 풀지 않고 DP와 브루트포스 문제를 많이 풀어 해당 문제를 푸는데 도움이 되었던 것 같다.

문제 출처: 프로그래머스 (https://school.programmers.co.kr/learn/courses/30/lessons/42884#)

문제 설명

🔎고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

처음 문제를 접했을 때는 완전탐색인가?라고 생각했었다. (아마 DP문제를 계속 풀다와서 그런 것 같다.)

첫 시도로 defaultdict로 모든 경로에 대해 방문하는 차량의 대수를 기록하여 문제 풀이를 시도했다.

<틀린코드 보기>

from collections import defaultdict
def solution(routes):
    answer = 0
    routes.sort()
    road = defaultdict(int)
    
    for enter, out in routes:
    	for i in range(enter, out+1):
        	road[i] += 1
    
    start = list(road.keys())[0]
    end = list(road.keys())[-1]
    cur = start
    rec = 0
    
    while cur < end:
    	answer += 1
    	rec = road[cur]
        while rec == road[cur]:
        	cur += 1
            
    return answer

다시 살펴보니 틀린 코드는 여기 올리기 민망할 정도로 논리가 안맞는 수준이었다. 점검을 위해 돌렸을 때 대부분의 케이스에서 시간 초과가 발생하였고, 제대로 돌아간 3개 조차 실패로 나왔다.

패착은 이렇다.

1. 방문한 전체 길이의 경로를 탐색하므로 인해 연산이 지나치게 많이 발생하였다.

2. 방문과 탐색을 따로 진행함으로 인해 연산이 두배정도 증가하였다.

3. 해당 도로의 방문 차량 숫자가 달라지는 것과 CCTV 수는 항상 관련이 있는 것은 아니다.

나의 잘못된 버릇이 항상 그렇듯 문제를 너무 꼬아 생각하게 되는 것을 하루 빨리 고쳐야 실력 향상에 도움이 될 것 같다..

정답은 다음과 같다.

<정답 코드>

from collections import deque
def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[1])
    q = deque(routes)
    
    while q:
        enter, out = q.popleft()
        answer += 1
        while q and q[0][0] <= out:
            q.popleft()

    return answer

이전에 짰던 코드보다 훨씬 간결하게 답안을 작성할 수 있는 것이었다.

접근은 아래와 같다.

1. 주어진 route에 대해, 먼저 나가는 차량들을 기준으로 정렬한다. 

2. 정렬된 리스트를 queue형식으로 변경한다.

3. queue에서 차량경로를 하나씩 꺼낸 후, 해당 경로 상 임의의 위치에 CCTV 하나를 배치한다 가정하고, 해당 경로 안에서 출발을 하는 차량들을 모두 pop해준다.

처음엔 나가는 차량을 기준으로 정렬을 하는게 아닌, 출입하는 차량을 기준으로 정렬을 해야한다고 생각했다.

이와 같이 생각한 이유는, 먼저 출발한 차량이 탈출하기 전에 있었던 모든 차량들을 pop해야한다고 생각했기 때문이다.

하지만 이런 접근이 틀린 이유는 가장 먼저 출발한 차량이 가장 나중에 탈출하는 경우가 있다면, CCTV 대수는 1대로 출력되기 때문이다. (그리고 가장 먼저 탈출하는 차량을 기준으로 정렬해야한다는 사실을 3시간 만에 떠올렸다...)

그리디 문제를 풀 때 가끔씩 드는 생각이지만 해당 코드가 항상 정답을 배출하는 코드일까?라는 의문이 아직까지 남아있지만, 그렇다할 반례를 아직 못찾았다. 반례를 찾게 된다면 추가로 업로드 해야겠다.