문제 설명

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

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

제한사항

  • 선수의 수는 1명 이상 100명 이하입니다.
  • 경기 결과는 1개 이상 4,500개 이하입니다.
  • results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
  • 모든 경기 결과에는 모순이 없습니다.

입출력 예

nresultsreturn
5[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

문제 풀이

def solution(n, results):
    answer = 0
    graph=[['N']*n for _ in range(n)]
    
    for i in range(len(results)):
        x,y=results[i]
        graph[x-1][y-1]=1
        graph[y-1][x-1]=-1
        
    for k in range(n):
        graph[k][k]=0
        for i in range(n):
            for j in range(n):
                if graph[i][k]!='N' and graph[k][j]!='N':
                    if graph[i][k]+graph[k][j]<0:
                        graph[i][j]=-1
                    elif graph[i][k]+graph[k][j]>0:
                        graph[i][j]=1
    
    for i in range(n):
        cnt=0
        for j in range(n):
            if type(graph[i][j])!=int:
                cnt+=1
                break
        if cnt==0:
            answer+=1
    return answer

어떻게 풀어야할지 감이 오지 않았던 문제이다. 이전에 푼 그래프 문제가 BFS로 풀 수 있었기 때문에 자꾸만 머릿속에서 BFS/DFS 풀이 방식이 떠올랐다. 하지만 아무리 생각해도 그 방식으로 푸는 방법이 아닌 것 같아서 결국 프로그래머스의 질문하기 기능을 이용했다. 내가 글을 올린 건 아니고 다른 사람들의 힌트를 얻기위해 들어갔다.

답을 올리지 않은 글들을 들어가 보니 공통적으로 플로이드-워셜이라는 방식을 이용하라고 조언을 해주었다. 처음 들어보는 알고리즘이라서 어떤 건지 공부부터 했다.

간단하게 설명하자면

기준이 되는 노드는 중간 노드이다.

예를 들어, 1번 -> 2번, 2번 -> 3번 으로 이루어져 있는 간선이 있다고 할 때, 1번에서 3번을 가기 위해서는 2번 노드를 거쳐야 한다.

이때, 2번 노드가 중간 노드가 되는 것이다. 플로이드-워셜은 최단거리를 찾는 알고리즘이기 때문에 이러한 로직을 이용해서 중간 노드를 거치는 경로와 직진하는 경로의 최단 거리의 값을 갱신하는 것이다.

아래는 플로이드-워셜의 기본 코드이다.

# k=거쳐가는 노드
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

k를 중간 노드라고 생각하고 모든 경로를 탐색해보면서 k를 거칠때에 경로가 짧은지 아닌지 판단해서 값을 갱신한다.

이번 문제도 이러한 방식을 이용해서 풀면 가능하다.

본인은 이긴 사람은 그래프 값에 1을, 지면 -1을 넣어줬다. 즉, ij를 이기면

graph[i][j]=1
graph[j][i]=-1

이런 방식으로 값을 준다.

그리고 중간 노드를 이용해서 합친 값이 0보다 작으면 -1, 0보다 크면 1을 넣어준다.

이러한 방식으로 문제를 풀면 테스트케이스에 통과한다!

다른 사람 풀이

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

이긴 사람, 진 사람의 dictionary를 따로 만들어서 두 딕셔너리를 확인하는 방식을 썼다.

참고 플로이드-워셜 알고리즘

profile
백엔드 개발자입니다.

0개의 댓글