알고리즘 유형 : 그래프
풀이 참고 없이 스스로 풀었나요? : X
https://school.programmers.co.kr/learn/courses/30/lessons/49191?language=python3
SOLVE 1
플로이드 워셜 로직 응용 풀이
import sys
input = sys.stdin.readline
def solution(n, results):
answer = 0
graph = [[None]*(n+1) for _ in range(n+1)]
# 간선 정보 2차원 리스트에 저장
for A, B in results:
graph[A][B] = True
graph[B][A] = False
for mid_node in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if graph[i][mid_node] == None or graph[mid_node][j]:
continue
# A가 B를 이기고 B가 C를 이기면 A도 C를 이김
# 지는 경우도 마찬가지
if graph[i][mid_node] == graph[mid_node][j]:
graph[i][j] = graph[i][mid_node]
graph[j][i] = not graph[i][mid_node]
# 자기 자신과는 승패 관계가 없으므로 None이 저장되어 있음
# 순위를 확정지을 수 있다는 것은 자신을 제외한 모든 선수와
# 승패 관계가 있다는 것이므로, None이 하나만 있으면 그 선수는
# 순위를 확정지을 수 있음
for player in graph:
cnt_none = len([x for x in player[1:] if x == None])
if cnt_none == 1:
answer += 1
return answerSOLVE 2
dictionary, set 풀이
import sys
from collections import defaultdict
input = sys.stdin.readline
def solution(n, results):
answer = 0
# wins[key]는 key가 이긴 사람들의 집합
# loses[key]는 key가 진 사람들의 집합
wins, loses = defaultdict(set), defaultdict(set)
for A, B in results:
wins[A].add(B)
loses[B].add(A)
for player in range(1, n+1):
# player가 진 사람들은 player가 이긴 사람들도 이긴다.
for winner in loses[player]:
wins[winner].update(wins[player])
# player가 이긴 사람들은 player가 진 사람들에게도 진다.
for loser in wins[player]:
loses[loser].update(loses[player])
# player가 자신을 제외한 모든 선수와 승패 관계가 존재한다면
# 그 player는 순위를 확정지을 수 있다.
for player in range(1, n+1):
if len(wins[player]) + len(loses[player]) == n-1:
answer += 1
return answerSOLVE 1) 풀이 요약 (플로이드 워셜 로직 응용 풀이)
-
해당 문제는 n개의 노드와 간선 정보가 주어지고, 특정 조건을 만족하는 노드 개수를 찾는 문제이다.
여기서 특정 조건이란
순위를 확정지을 수 있는 선수의 수이다.문제에서 순위 개념을 따로 정의해줬다.
A가 B를 이겼다는 것은 곧 A의 순위가 B보다 높다는 것을 의미함그렇다면 정확하게 순위를 매길 수 있다는 것은 어떻게 판단할 수 있을까?
자신을 제외한 모든 선수들과 승패 여부가 존재한다면, 그 여부를 모두 만족하는 위치가 본인의 순위로 확정될 수 있다.
즉, 선수들 사이의 모든 승패 여부를 구해놓은 다음, 자신을 제외한 모든 선수들과 승패 여부가 존재하는 특정 선수들을 찾으면 된다.
-
문제에서 주어진 조건에 의하면
A가 B를 이기고 B가 C를 이기면 A도 C를 이긴다라는 명제가 성립하고, 지는 경우에도 마찬가지로 성립한다.이 경우를 모두 탐색하고 난 뒤에 순위 확정 가능 선수를 구해야한다.
모든 선수에 대해, 모든 선수와의 승패 관계 존재 여부를 알아야하고, 그 것을 위해 중간 노드 C에 대해 A -> C, C -> B 간선으로부터 A -> B 관계를 파악한다.
이 로직은 플로이드 워셜 로직과 상당히 유사하다.
다만 최단 거리를 갱신하는 상황이 아니므로 그냥 A -> B 관계가 존재한다는 사실만 따로 저장해주면 된다.
-
2차원 리스트를 만들 때 초기값은 None이다. 간선은 승패 관계를 의미하므로 None이라는 것은 곧 승패 관계가 전혀 없다는 의미이다.
results를 순회하며 간선 정보를 등록할 때, A가 B를 이기는 간선이 있다면 B가 A에게 진다는 간선이 있다. 두 경우 다 추가해주자.
-
이제 3중 for문을 돈다. i -> mid_node, mid_node -> j 두 간선에 대해 하나라도 None이면 건너뛰자.
둘 다 승패 관계가 존재하는 경우에는, 둘 다 True이면 i -> j도 True(j -> i False), 둘다 False이면 i -> j도 False(j -> i True) 이므로 i -> j 간선을 등록해준다.
- 모든 선수들을 순회(graph의 행)하면서, 자기 자신을 제외한 모든 선수들과 승패 관계가 존재한다면 그 선수는 순위를 확정지을 수 있는 선수이므로 카운팅해주자.
SOLVE 2 풀이 요약 (dictionary, set 풀이)
-
1번 풀이와 마찬가지로
임의의 player에 대해, 자신을 제외한 모든 선수들과 승패 관계가 존재할 때, player의 순위를 확정지을 수 있다를 구현한다.말을 조금 바꿔서,
자신을 제외한 모든 선수들과 승패 관계가 존재한다를자신이 이기는 선수의 수와 지는 선수의 수의 합이 n-1이다로 바꿔보자.이 명제대로라면 임의의 선수 player에 대해, player가 이기는 선수와 지는 선수를 모두 구해주면 된다.
이 때 활용할 명제는 두 가지가 있다. player를 기준으로 작성해보면,
1)
player가 이긴 사람은player가 진 사람에게도 진다.2)
player가 진 사람은player가 이긴 사람에게도 이긴다.이를 위해 wins, loses 딕셔너리를 만든다.
wins[key]는 key가 이긴 사람의 집합
loses[key]는 key가 진 사람의 집합을 의미한다.
-
위 로직을 그대로 구현하면 된다.
우선 results를 wins, loses에 알맞게 넣어주자.
이 후 1부터 n까지 player를 돌면서, 각 player에 대해 위의 1)과 2)를 수행해주면 된다.
- 임의의 player에 대해, 이기는 사람과 지는 사람의 합이 n-1이면 그 player는 순위 확정이 가능하므로 카운팅 해주자.
배운 점, 어려웠던 점
-
노드들 사이에 단방향 간선이 존재하고, 순위라는 개념이 있어서 위상 정렬을 생각하고 풀었는데, 순위를 확정지을 수 있는 선수를 판단하는 로직에서 막혀서 결국 다른 사람 풀이를 참고해서 풀었다.
플로이드 워셜에 익숙한 상태였다면 유사한 로직을 발견하고 응용해서 풀었을 법도 한데.. 복습 잘 해놔야겠다.
