코테 문제 풀이 - 프로그래머스/고득점kit/그래프/순위

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49191#

풀이 1

어떤 노드 X가 순위가 정해진 노드인지 확인하기 위해서는,

X를 제외한 모든 노드 Y에 대하여 X→Y 혹은 Y→X 가 가능해야 한다.

X→Y가 가능한지 확인하기 위한 함수로 can_A_to_B라는 함수를 정의했으며, bfs 알고리즘을 사용했다.

graph는 인접 리스트로 구현했으며, 이 경우 bfs의 시간복잡도는 $O(N + E)$이다.

만약 인접 행렬로 구현했다면, bfs의 시간 복잡도는 $O(N^2)$이다. 이 문제에서는 노드의 최댓값이 100, 간선의 최댓값이 4500이어서, 인접행렬로 graph를 구현했을 때 더 유리하다.

시간 복잡도

• 노드의 개수 $N$의 최댓값이 100, 간선의 개수 $E$의 최댓값이 4500이다.
• 최대 45,000,000 인데, 가능할 것 같은데 안 된다…

CODE

from collections import deque

def can_A_to_B(graph, A, B):
    # 단방향 그래프 graph에서 노드 A에서 B로 이동 가능하면 True, 불가능하면 False 반환
    q = deque([])
    # A, B가 같으면 방문 가능하다 취급
    if A == B:
        return True
    
    # A->? 모든 노드 q에 저장    
    for Y in graph[A]:
        q.append(Y)
    
    # bfs 수행 중 B를 만나면 True 반환
    while q:
        X = q.popleft()
        if X == B:
            return True
        for Y in graph[X]:
            q.append(Y)

    # bfs가 끝났는데 B를 못만났으면 False 반환
    return False # A->B 불가능

def solution(n, results):
    # 순위가 정해지는 기준 : 어떤 노드 X를 제외한 모든 노드 V가 (X -> V) or (V -> X) 가능
    
    # graph 구현
    graph = [[] for _ in range(n+1)]
    for result in results:
        v1, v2 = result
        graph[v1].append(v2)
    
    answer = 0
    for X in range(1, n+1):
        # 어떤 노드 X를 제외한 모든 노드 V가 (X -> V) or (V -> X) 가능한지 확인
        for V in range(1, n+1):
            if not can_A_to_B(graph, V, X) and not can_A_to_B(graph, X, V):
                break
        else: # X는 순위가 정해진 노드이다.
            answer += 1

    return answer

풀이 2

(N+1)x(N+1) 크기의 인접 행렬 graph를 준비해준다.

편의상 index 0 은 무시하고 1부터 저장해준다.

graph[a][b] 의 의미는 a가 b를 이겼다는 의미이다.

results 원소들을 기반으로 직접적인 승리들을 graph에 기록해준다.

그리고 플로이드-워셜 알고리즘을 이용하여 a→b and b→c 이면 a→c인 것 처럼 간접적인 승리를 graph에 기록해준다.

그럼 최종적으로 graph[a][b] 값은 직접적으로든 간접적으로든 a가 b를 이길 수 있는지가 저장된다.

어떤 노드 X가 순위가 정해져있는지 확인하기 위해서는, X를 제외한 모든 노드들 Y가 graph[X][Y]=True 이거나 graph[Y][X]=True 여야 한다. 즉, X는 모든 노드들에 대하여 승패 여부를 알 수 있어야 한다. 하나라도 승패 여부를 모르는 노드 Y가 있다면, 순위를 지정할 수 없다는 뜻이다.

시간 복잡도

• 노드의 개수 $N$의 최대 크기가 100인 점에서 플로이드-워셜 알고리즘을 떠올리면 좋다.
• 플로이드-워셜 알고리즘은 최대 크기가 1000이 되면 쓸 수 없다.

CODE

def solution(n, results):
    graph = [[False] * (n+1) for _ in range(n+1)]
    
    for result in results:
        win, lose = result
        graph[win][lose] = True
    
    for k in range(1, n+1):
        for w in range(1, n+1):
            for l in range(1, n+1):
                if graph[w][k] and graph[k][l]:
                    # print(f'{w} -> {k}, {k} -> {l} so {w} -> {l}')
                    graph[w][l] = True
    
    answer = 0
    for x in range(1, n+1):
        # x가 순위가 정해져있는지 확인
        for y in range(1, n+1):
            if x == y:
                continue
            # x->y 이거나 y->x 이면 
            if not graph[x][y] and not graph[y][x]:
                break
        else: # for문을 다 돌았으면
            answer += 1
    
    return answer