[Python][프로그래머스] Level 3 - 순위(그래프)

🍋 문제링크

코딩테스트 연습 - 순위

 

🍓 문제풀이

해당 문제는 BFS와 visited 를 사용해서 풀었습니다.

일단은, 매개변수로 들어오는 results 는  [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 으로 보기 쉽지 않게 저장되어있기 때문에

아래와 같이 i 가 j 를 이겼다면 win의 의미로 arr[i][j] = 'w'

                  i 가 j 에게 졌다면 lose 의 의미로 arr[i][j] = 'l'

                  아무 승패관계가 없는 칸은 nothing의 의미로 arr[i][j] = 'n'으로 2차원 배열 새롭게 저장하였습니다.

그 후 arr[i][j] 를 돌면서 각 칸이 자기 자신과의 관계가 아닌지 ( i == j) 혹은 visited 를 하진 않았는지 (visited[j] == 0) 체크해주고 

자신을 이긴 번호가 있으면 그 번호를 이긴 모든 사람 visited[i] == 1, 

그리고 자신에게 진 번호가 있으면 그 번호에게 진 모든 사람을 visited[i] == 1로 변경해줍니다.

그 후 visited 에서 1의 개수를 측정했을때 자기 자신을 제외한 N-1 개의 1이 있다면 자신의 순위를 알수있기 때문에 answer += 1을 해줍니다. visited.count(1) == N-1이면 자신의 순위를 알 수 있는 이유는 

자신을 이긴 사람의 수 + 자신에게 진 사람의 수 를 통해 자신의 위치를 알 수 있기 때문입니다!!

예를 들어 위의 표에서 2를 확인해보면 자신을 이긴 사람이 1명, 자신에게 진 사람이 3명이기 때문에 자신을 자연스럽게 2등임을 알수 있습니다!

🍉 Code

# check 가 안나올때까지 bfs 계속 돌리면서 visited 채워주기
def bfs(i, j, N, arr, visited, check):
    if arr[i][j] == check and visited[j] == 0:
                tmp = []
                tmp.append(j)
                while len(tmp) > 0:
                    p = tmp[0]
                    tmp.remove(p)
                    visited[p] = 1
                    for f in range(1, N+1):
                        if arr[p][f] == check and visited[f] == 0:
                            tmp.append(f)
    return visited

def solution(N, results):
    answer = 0
    arr = [['n' for _ in range(N+1)] for _ in range(N+1)]
    for tmp in results:
        arr[tmp[0]][tmp[1]] = 'w' # tmp[0] 이 tmp[1]을 이김
        arr[tmp[1]][tmp[0]] = 'l'
    
    for i in range(1, N+1):
        visited = [0 for i in range(N+1)]
        for j in range(1, N+1):
            visited = bfs(i, j, N, arr, visited, 'w')
            visited = bfs(i, j, N, arr, visited, 'l')
                
        if visited.count(1) == N-1:
            answer += 1
            
    return answer