문제 출처: 프로그래머스

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

처음 문제를 읽었을 때는 어떻게 접근 해야할지 고민을 오래한 문제다.

내 생각의 흐름은 이랬다.

순위를 정하는 문제 ➡ sort문제 ➡ 하지만 sort의 key를 설정하기 어려움 ➡ Tree 형식으로 질 때 마다 자식 노드로 추가해주면 되지 않을까? ➡ 이렇게 됐을 때 구현은 어떻게 해야하나..

이런 식으로 생각을 이어가면서 깨작깨작 작성하다보니 정답에 도달할 수 있었다.

<정답 코드>

def solution(n, results):
    answer = 0
    rank = {i + 1: [set(), set()] for i in range(n)}
    order = [0] * (n + 1)

    for win, lose in results:
        rank[win][0].add(lose)
        rank[lose][1].add(win)

    for _ in range(2):
        for i in rank.keys():
            for wins in rank[i][0]:
                rank[i][0] = rank[i][0].union(rank[wins][0])

            for loses in rank[i][1]:
                rank[i][1] = rank[i][1].union(rank[loses][1])

    for i in rank.keys():
        if len(rank[i][0]) + len(rank[i][1]) == n - 1:
            answer += 1

    return answer

접근은 아래와 같다.

어떤 선수의 총 경기 횟수가 n-1이면 해당 선수의 순위를 알 수 있다. (비기는 경우는 없기 때문에)

1. 선수 번호를 기준으로 해당 선수가 이긴 선수들과 패배한 선수들을 기록하는 dictionary를 만든다.
   1. 딕셔너리의 value는 두 set의 집합으로 만들어진다.
   2. 0번 index는 해당 선수가 이겼던 선수들을 기록했고, 1번 index에는 해당 선수가 졌던 선수들을 기록했다.
2. 경기 결과를 하나씩 살피면서 rank를 채워준다.
3. 채워진 rank를 순회하면서 한번 이겼던 선수에게 패배한 선수들이 있다면 채워주는 작업을 반복한다.
   1. 예를 들어 results가 [3, 1], [1, 2]이었다고 하면 최초의 rank는 {1: [(2), (3)], 2:[(1), ()], 3:[(), (1)]}이 된다. 이 때 아래 for문을 통해 한번 순회해주면 rank는 {1:[(2), (3)], 2:[(1), (3)], 3:[(),(1, 2)]가 되게 된다.
4. 마지막으로 모든 선수들 중 총 경기횟수가 n-1번 진행된 선수들만 count해준다.

운이 좋게 위 코드에서는 rank를 채워주는 작업이 총 3번 만에 모든 test case가 통과되었지만, 곰곰히 다시 생각해보니 rank에 업데이트가 새로 일어나지 않을 때 까지 반복해서 업데이트해주어야 진짜 정답이지 않을까 했다. (아닐수도 있음)

이렇게 보니 트리라기 보다 그래프 문제에 가까워 보였다. 실제 문제를 보니 그래프 문제로 분류되어 있었고 다른 사람들은 bfs나 플로이드-와샬 알고리즘으로 문제를 해결했다고 했다. 독특한 풀이를 했다고 좋아하긴 했지만, 남들이 생각하는 걸 생각하지 못했다는 점에서 약간의 아쉬움도 있었다.

이번 문제를 통해서 드디어 프로그래머스 level3에 도달할 수 있었다.

여러 번 시도하면서 운 좋게 몇일 전에 풀어봤던 문제가 나오기도 하고, level 3치고 쉬운 문제가 나온 적도 있었지만 항상 다른 문제에서 막혀서 뚫지 못했었는데 이번에는 둘다 모르는 문제였지만 천천히 생각하면서 푸니 통과할 수 있었다.

프로그래머스의 level이 현재 내 코딩 수준을 정의해주는 것은 아니지만 (현재까지 프로그래머스 문제만 300문제 가까이 풀었지만, 아직도 풀지 못한 level2, level3문제가 많다.) 꾸준히 성장하고 있고, 꼼수 부리지 않고 통과하겠다는 의지가 먹혀든 것 같아서 기분이 좋았다.

문제 출처: 프로그래머스

문제 설명

🔎 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다.

최단거리, 최저비용이라는 맥락에서 한가지 알고리즘을 떠올리는 것 자체는 어렵지 않으나 거기서 한단계 더 나아가야한다는 부분이 어려웠던 문제였다.

문제를 읽고 '다익스트라' 를 사용해야겠다 마음을 먹고,

s로 부터 a와 b까지의 최단 경로를 구해서 겹치는 부분의 비용을 제거하면 된다고 생각했으나, 그것과는 별개인 문제였다.

당장에 주어진 예시만 봐도 S -> A는 4->1->6이 최단경로고, S->B는 4->2가 최단거리였다. 여기서 겹치는 구간은 없었으나, 5까지 함께하면 더 저렴한 비용으로 갈 수 있었다.

한참을 고민하다가 결국 검색을 했었고, 생각보다 간단한 원리에 감탄했고 한번 더 배울 수 있었다.

<정답 코드>

from queue import PriorityQueue
def solution(n, s, a, b, fares):
    answer = float('inf')
    road = [[] for _ in range(n+1)]
    
    for u, v, cost in fares:
        road[u].append((v, cost))
        road[v].append((u, cost))
    
    def dijkstra(x):
        dist = [float('inf')] * (n+1)
        dist[x] = 0
        q = PriorityQueue()
        q.put((0, x)) # cost, 도착지, 출발지
        
        while q.qsize() > 0:
            cur = q.get()
            _x = cur[1]
            
            for nx, cost in road[_x]:
                if dist[_x] + cost < dist[nx]:
                    dist[nx] = min(dist[nx], dist[_x] + cost)
                    q.put((dist[nx], nx))
        
        return dist
    
    #----------------참고 코드----------------#
    dist = [[]]
    
    for i in range(1, n+1):
        dist.append(dijkstra(i))
        
    for i in range(1, n+1):
        answer = min(answer, dist[s][i] + dist[i][a] + dist[i][b])
    
    return answer

접근은 아래와 같다.

1. 모든 노드에 대해 각 지점 별 최단비용 거리를 다익스트라 함수로 구한다.
   1. 이를 기록하는 dist 배열은 빈 배열이 하나 추가된 상태로 구현한다. (index=0에 해당하는 노드가 존재하지 않기 때문)
2. 모든 노드의 최단거리 목록을 순회하면서,  S-> i, i->A, i->B를 모두 더한 값 중 최소가 되는 값이 정답이다. (i = 현재 순회중인 노드)

모든 경로에 대한 다익스트라 배열을 구한다는 것을 생각해내지 못해 스스로는 풀지 못했던 문제다.

레벨별 문제에 슬슬 익숙해지려 하니, level3문제들이 대체로 기본 알고리즘 + 한 단계 발전인 느낌이 드는 것 같다. 재미있다.

대체로 빠른 속도를 내는 O(E logV)의 시간복잡도를 가진 다익스트라 함수였지만, 꽤 오래걸리는 예제도 있었다.

오히려 O(n³)의 시간복잡도를 가진 플로이드-와샬 알고리즘이 더 빨리 작동할 수 있다는 글을 보아 아래에 정리했다.

플로이드-와샬 알고리즘 풀이

플로이드 와샬 : i에서 k를 거쳐 j로 가는 최단거리를 구하는 알고리즘, 3중 반복문을 사용하기 때문에 O(n³)의 시간복잡도를 갖는다.

<플로이드 와샬 풀이>

def solution(n, s, a, b, fares):
    answer = float('inf')
    cost = [[float('inf')] * (n+1) for _ in range(n+1)]

    # cost 중에서 fares에서 제시된 도로
    for u, v, _cost in fares:
        cost[u][v] = _cost
        cost[v][u] = _cost

    #플로이드 와샬 알고리즘
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if i == j:
                    cost[i][j] = 0
                else:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])


    for i in range(1, n+1):
        answer = min(cost[s][i] + cost[i][a] + cost[i][b], answer)

    return answer

다익스트라에서 dist로 구현되었던 전체 구간에 대한 비용을 cost로 작성하였다.

1. fares에서 제시된 노드 간의 연결은 해당 비용으로 업데이트 해준다.
2. cost 배열에서 서로 다른 상수 i, j에서 i -> j의 비용 중에서 i -> k -> j로 방문했을 때 더 저렴한 경우 그 비용으로 업데이트 해준다. (반복문의 순서를 바꾸면 다르게 작동하므로 순서에 유의)

이후의 과정은 다익스트라와 동일하다.

평균적인 속도는 다익스트라보다 느리게 작동하지만, 최대의 경우에도 2600ms 이내에 해결한다는 것에서 의미가 있는 풀이었다.

문제 출처: 백준 온라인 저지 13023 ABCDE

문제 설명

🔎BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

(문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.)

위 그림에서 나타난 것 처럼, 주어진 여러 관계 속에서 A➡B➡C➡D➡E 로 이어지는 관계가 존재하는지 묻는 문제이다.

해당 관계가 몇번이 나타나는지는 상관없이 하나라도 존재하면 1, 하나도 존재하지 않는다면 0을 출력한다.

문제를 읽기만 했을 때는 그래프 문제라고 파악하기 힘들지만, 주어진 예제들을 통해 그래프 탐색을 통해 문제를 해결해야하는 것을 확인할 수 있다.

<정답 코드>

def dfs(cur, depth=0):
    if depth == 4:
        return True

    visit[cur] = True

    for nx in relation[cur]:
        if not visit[nx]:
            flag = dfs(nx, depth+1)
            if flag:
                return True

    visit[cur] = False
    return False


n, m = map(int, input().split())
relation = [[] for _ in range(n)]
ans = 0
for _ in range(m):
    v, w = map(int, input().split())
    relation[v].append(w)
    relation[w].append(v)


for i in range(n):
    visit = [False] * n
    ans = dfs(i)
    if ans:
        break

print(int(ans))

한번만 관계를 확인하면 되기에 flag와 DFS를 활용해 문제를 풀이하였다.

접근은 아래와 같다.

1. 입력을 2차원 리스트에 그래프형태로 저장한다.

2. 그래프를 dfs를 통해 순회한다. dfs를 수행할 때는 depth 인자를 주어 depth가 4가 되면 탈출하게 작성하였다.

3. depth가 4일 때만 True를 반환하여 flag를 변경해주었고, flag가 True가 되면 True를 반환하며 탈출한다.

dfs의 특성을 통해 깊이 = 관계의 깊이로 생각하여 문제를 풀었다.

주의해야할 점은 탐색에 실패하였을 때 visit[cur]을 False로 바꾸어 다음 진행에 차질이 생기지 않도록 하는 것이다.