프로그래머스 - 순위(level3, 그래프) + 내 풀이 비교

문제 풀러 가기

이 문제를 보았을 때 가장 직관적으로 생각할 수 있는 풀이는 , 그래프를 그려서 내가 이길 수 있는 노드와 내가 질 수 있는 노드를 파악하는 것이였다.
즉 주어진 예시에서는 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 다음과 같이 경기 결과 리스트가 주어졌는데, 해당 경기 결과를 바탕으로 각 노드가 이기는 노드와 지는 노드를 결정할 수 있다.

여기서 현재 노드가 이길 수 있는 노드를 파악하는 방법은 이기는 방향으로 도달 할 수 있는가를 파악하면 되고 반대로 마찬가지로 질 수 있는 것도 파악하면 된다.

코드를 보면 직관적으로 이해할 수 있다.

def solution(n, results):
    answer = 0
    graph = [[] for _ in range(n+1)]
    graphReverse = [[] for _ in range(n+1)]
    
    for [A,B] in results:
        graph[B].append(A)  # B -> A 로 이동 가능 
        graphReverse[A].append(B)  # A -> B 로 이동 가능 
    for i in range(1,n+1):
        visit = [False for _ in range(n+1)]
        CanArrive(i,visit,graph)
        CanArrive(i,visit,graphReverse)
        
        if sum(visit) == n:
            answer += 1
            
    return answer

def CanArrive(x,visit,graph):    
    visit[x] = True
    for nextNode in graph[x]:
        if not visit[nextNode]:
            CanArrive(nextNode,visit,graph
    return

하지만 해당 방식은 각 노드에 대해서 중복적으로 모든 경로를 검사하기 때문에 실행시간이 길게 발생한다.
이를 보완한 방식은 다음과 같은데, 해당 코드는 내가 푼 것은 아니고 다른 사람의 풀이를 참고한 것이다. 해당 풀이를 보면 뭔가 플로이드 와샬 알고리즘의 원리랑 비슷한 것 같다. 계속해서 lose,win을 갱신하면서 판단하는게..

from collections import defaultdict
def solution(n, results):
    answer = 0
    win, lose = defaultdict(set), defaultdict(set)
    for result in results:
            lose[result[1]].add(result[0])
            win[result[0]].add(result[1])

    for i in range(1, n + 1):
        for winner in lose[i]: win[winner].update(win[i])
        for loser in win[i]: lose[loser].update(lose[i])

    for i in range(1, n+1):
        if len(win[i]) + len(lose[i]) == n - 1: answer += 1
    return answer

실제로 찾아보니 플로이드 와샬을 문자열로 구현한 풀이가 있었다.

def solution(n, results):
    total = [['?' for i in range(n)] for j in range(n)]

    for i in range(n):
        total[i][i] = 'SELF'

    for result in results:
        total[result[0]-1][result[1]-1] = 'WIN'
        total[result[1]-1][result[0]-1] = 'LOSE'

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if total[i][k] == 'WIN' and total[k][j] == 'WIN':
                    total[i][j] = 'WIN'
                elif total[i][k] == 'LOSE' and total[k][j] == 'LOSE':
                    total[i][j] = 'LOSE'

    answer = 0

    for i in total:
        if '?' not in i:
            answer += 1

    return answer

마지막은 맨 위에 있는 내 풀이에서 중복을 제거한 풀이..

def solution(n, results):
    answer = 0
    graph = [[] for _ in range(n+1)]
    graphReverse = [[] for _ in range(n+1)]
    visit = [[set(),set()] for _ in range(n+1)]
    
    for [A,B] in results:
        graph[B].append(A)  # B -> A 로 이동 가능 
        graphReverse[A].append(B)  # A -> B 로 이동 가능 
        
    for i in range(1,n+1):
        dfs(i,visit,graph,0)
        dfs(i,visit,graphReverse,1)
        
    for i in range(1,n+1):
        if len(visit[i][0]) + len(visit[i][1]) == n + 1:
            answer += 1
    
    return answer

def dfs(x,visit,graph,direction):
    
    if visit[x][direction]:
        return visit[x][direction]
    
    CanArriveNode = set([x])
    for nextNode in graph[x]:
        CanArriveNode = CanArriveNode | dfs(nextNode,visit,graph,direction)
    
    visit[x][direction] = CanArriveNode
    return visit[x][direction]