[99클럽 코테 스터디 25일차 TIL] 프로그래머스 | 순위

다시 풀어보기

25일차 graph, BFS

Problem

코딩테스트 연습 > 그래프 > 순위

프로그래머스

 

 

Sol

주어진 경기 결과를 분석했을 때 순위를 명확하게 알 수 있는 선수의 수를 세는 문제

 

해결 방법

👀 처음에는 어차피 방향([a,b]는 a가 b에게 이김)이 정해져있으니 wins 만 카운트 하면될 것 같아서 시작했는데 너무 복잡해지고 자꾸 틀려서 GPT의 도움을 받았습니다. +) 스터디 시간 코치님께서는 플로이드-워셜 알고리즘을 사용하셨다고 합니다. 초기에 떠올린 아이디어로 하려면 요걸 활용하면 좋을 것 같습니다. 한번도 공부를 안해봐서 다음에 해봐야겠습니다.

1. wins, loses 리스트 : 각 선수가 이긴 선수들과 진 선수들의 목록 저장
2. BFS : 각 선수별로 이긴 선수들 & 진 선수들을 탐색 -> 방문한 선수들의 수 반환
3. 모든 선수와 승패가 명확한 경우 count
- win_count와 close_count가 n-1 인 경우 

 

시간복잡도 O(n^2)

• n명 선수에 대해 BFS 수행 : O(n * (n+m))
  • m : 선수들이 이긴 선수들과 진 선수들의 총 수

---

✔ Answer

from collections import deque

def solution(n, results):
    # 그래프 초기화
    # 이긴 선수, 진 선수 리스트 저장
    wins = [[] for _ in range(n)]
    losses = [[] for _ in range(n)]
    
    # 경기 결과 기록
    for a, b in results:
    	# a가 b 이김
        wins[a-1].append(b-1)
        # b가 a한테 짐
        losses[b-1].append(a-1)
    
    def bfs(graph, start):
    	# 방문 여부
        visited = [False] * n
        queue = deque([start])
        # 시작 선수 방문 표시
        visited[start] = True
        # BFS 통해 방문한 선수 카운트
        count = 0
        
        while queue:
            node = queue.popleft()					# 큐에서 선수 하나씩 꺼내서
            for neighbor in graph[node]:			# 그 선수가 이겼거나 진 선수들에 대해
                if not visited[neighbor]:			# 아직 방문하지 않았다면
                    visited[neighbor] = True		# 방문 표시하고
                    queue.append(neighbor)			# 큐에 추가하여 BFS 진행
                    count += 1						# 방문한 선수 수 증가
        
        return count
    
    answer = 0
    for i in range(n):
        win_count = bfs(wins, i)					# 이긴 선수들에 대한 BFS
        lose_count = bfs(losses, i)					# 진 선수들에 대한 BFS
        
        # 각 선수가 이긴 선수 + 진 선수가 명확할때!
        if win_count + lose_count == n - 1:
            answer += 1
    
    return answer

---

💬 소감

요즘 문제가 너무 어렵게 느껴집니다. 🤒 아자아자