[프로그래머스] 그래프 2. 순위

문제

---

풀이

 

혼자 여러 방법으로 고민해보다가 아무래도 정답인 것 같은 방법이 생각나지 않아 검색해보았다.

( https://roomedia.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%9C%EC%9C%84-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B7%B8%EB%9E%98%ED%94%84-Floyd-Warshall-Level3 )

 

플루이드 와샬 알고리즘을 적용하는 문제라고 하는 부분까지 보고 아래와 같이 로직을 생각해 보았다.

한 점에서 다른 점까지의 거리를 점을 기준으로 계산하는 알고리즘이다. O(n^3)이다.

( https://blog.naver.com/ndb796/221234427842 )

먼저 각 선수의 이기고 진 결과를 이중배열에 저장한다. O는 자기 자신이라는 뜻, X는 연관되어있지 않다는 뜻이다.

점을 기준으로 반복문을 수행하며 X로 저장된 값이 다른 점을 통해 업데이트 될 수 있다면 변경해준다.

모든 반복문을 수행하고 자신의 행에 X가 없다면 그 선수는 순위가 정해졌다는 뜻이다.

구현하려고 하니 O, X, Win, Lose를 다르게 표현해야 구현하기 쉬워질 것 같았다.

O/X = 0, Win = 1, Lose = -1 로 표현하기로 했다.

 

def solution(n, results):
    answer = 0
    graph = [[0]*(n+1) for _ in range(n+1)]
    
    for win, lose in results:
        graph[win][lose] = 1
        graph[lose][win] = -1
        
    for i in range(n+1):
        for j in range(n+1):
            for k in range(n+1):
                if graph[j][k] == 1 or graph[j][k] == -1: # 이미 승패가 결정된 경우 스루
                    continue     
                if graph[j][i] == graph[i][k]: # i 노드를 거쳤을 때 승,승 이거나 패, 패 일 경우 연쇄적으로 j-> k의 승패를 확인할 수 있음
                    graph[j][k] = graph[i][k]
    
    for i, g in enumerate(graph):
        if 0 not in g[1:i] + g[i+1:]:
            answer += 1
    
    
    return answer

앞서 적은 표기법과 0 체크 부분은 다른 분의 코드를 참고했다.

 

역시 그래프라 그런지 진짜 어려웠다 ㅠ

코드를 작성하고 나니 간단해 보이는데, 로직을 생각하기까지가 어려웠다. 그래프 카테고리에 있는 걸 알았는데도 이정도면 나는 많이 부족한 듯 싶다 흑흑

---

다른 사람의 풀이

 

DFS를 이용해 푸는 방법도 있는 듯 하다 (https://velog.io/@tjdud0123/%EC%88%9C%EC%9C%84-python)