7/20 Coding Test

✅ Graph

🎈 가장 먼 노드 (level 3)

그래프 내 노드가 n개 있고, 가장 멀리 떨어져 있는 노드란 최단 경로로 이동했을 때 간선 수가 가장 많은 노드들을 의미한다.

• 입력값 : 노드 개수 n, 간선 정보가 담긴 2차원 배열 vertex
• 출력값 : 1번 노드로부터 가장 멀리 떨어진 노드 개수

from collections import deque

def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    dist = [-1] * (n+1)
    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)
    queue = deque([1])
    dist[1] = 0
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if dist[i] == -1:
                dist[i] = dist[x] + 1
                queue.append(i)
    for i in dist:
        if i == max(dist):
            answer += 1
    return answer

< 풀이 과정 >
그래프 문제에서 초기 노드 ~ 모든 노드 탐색 후 각 거리를 비교하여 최대값이 동일한 경우 1씩 더해주도록 설계한 문제.
노드 탐색에 있어 dfs가 아닌 bfs를 활용하여 진행했다. 순서대로 풀이를 진행하면 다음과 같다.

• graph를 노드 수만큼 빈 리스트를 생성해주고 간선 별 양방향인 점을 고려해 다음 위치를 저장해준다. 이후 초기노드 ~ 각 노드까지의 거리를 나타내는 dist 리스트도 생성해준다.
• 빈 deque을 만들어 초기 시작 노드인 1을 집어넣고, 초기 시작점의 dist는 당연히 0으로 고정시켜준다.
• while문으로 queue를 돌며 초기노드부터 시작해 인접 노드들을 방문하며 방문하지 않은 곳에 한해 dist를 갱신해준다.
• 최종적으로 dist for문을 돌며 최대값인 개수만큼 answer에 저장해주고 리턴한다.

🎈 순위 (level 3)

n명의 권투 선수가 대회에 참여해 1:1 방식으로 경기는 진행되고 심판은 주어진 경기 내 선수들의 실력을 기반한 결과를 가지고 순위를 매기고자 한다.

• 선수당 1명 이상 100명 이하, 경기 결과는 1개 이상 4,500개 이하이고 배열 내 [A,B]는 A선수가 B선수를 이겼다는 의미, 배열 내 숫자는 선수 등번호를 의미
• 입력값 : 선수 수 n명, 경기 결과 2차원 배열 results
• 출력값 : 정확하게 순위를 매길 수 있는 선수 수 리턴

def solution(n, results):
    answer = 0
    winner = [[] for _ in range(n+1)]
    loser = [[] for _ in range(n+1)]
    for i, j in results:
    	# 승자 리스트에는 자신에게 진 상대 번호 저장
        winner[i].append(j)
        # 패자 리스트에는 자신을 이긴 상대 번호 저장
        loser[j].append(i)
    # 각 선수를 i로 표현
    for i in range(1, n+1):
        # i에게 진 선수 번호 : w
        for w in winner[i]:
        	# i에게 이긴 상대 번호가 있다면 번호를 l로 두고 
            if loser[i]:
                for l in loser[i]:
                	# 패자 리스트 내 i에게 진 선수 번호 위치에 i선수에게 이긴 상대 번호 저장
                    if l not in loser[w]:
                        loser[w].append(l)
                    # 승자 리스트 내 i를 이긴 선수 번호 위치에 i선수에게 진 상대 번호 저장
                    if w not in winner[l]:
                        winner[l].append(w)
    # 순위를 알려면 승자 + 패자 리스트 내 길이가 n-1이어야 함.
    for w, l in zip(winner, loser):
        if len(w) + len(l) == n-1:
            answer += 1
    return answer

< 풀이 과정 >
문제에서 핵심은 A가 B를 이긴 것뿐만 아니라, 다음과 같은 상황이다.
주어진 결과가 만일 [A,B], [B,C]인 경우 A는 결국 C보다 높은 랭크임을 알 수 있다.
이를 적용시켜주기 위해 고민이 많이 필요했던 문제. 해당 [A,B], [B,C] 결과를 예시로 두고 이해하면 쉽게 느껴진다.
순서는 다음과 같다.

• 주어진 2차원 배열인 results의 승자, 패자 결과를 각각 리스트로 저장해주고 각 리스트에는 내가 이긴 상대, 진 상대의 정보를 저장한다.
• (1~n) for문을 돌며 i번째 선수마다 탐색을 진행한다.
• i에게 진 선수와 i에게 이긴 선수가 있는 경우, 패자 리스트에는 i를 이긴 상대 번호가 담기게 되는데, i에게 진 선수는 i가 이긴 상대에 대해서도 지게 되고, 승자 리스트에는 i에게 진 상대 번호가 담기게 되는데, i를 이긴 상대는 i가 진 상대에 대해서도 승리하게 되므로 이를 적용해준다.
• 이후 순위를 알기 위해선 각 위치별 승자 리스트 + 패자 리스트의 길이가 n-1이어야 하기에 이를 적용해 순위를 알게 된다면 answer에 1씩 더해준다.