[백준 17616] 등수 찾기

문제 출처 : https://www.acmicpc.net/problem/17616

 

이 문제는 2019년 정보 올림피아드 초등부 2차 3번 문제 입니다.

 

문제 이해하기

두 학생중 누가 더 잘했느냐를 종합하여 특정 학생 X의 등수 범위를 파악해야하는 문제 입니다.

문제의 예제 입력3번을 보겠습니다. 

5 5 1
1 3
2 3
3 4
3 5
4 5

 

해당 입력을 그림으로 표현하면 아래와 같습니다.

1, 2번을 제외한 3, 4, 5번의 등수는 확실하게 알 수 있습니다. 하지만 1번이 1등인지 2번이 1등인지 알 수 없습니다. 따라서 1번의 범위는 최대 1등, 최소 2등이 됩니다.

보통 DFS, BFS 문제를 풀 때 방향성을 고려하지 않는 양방향으로 구현하지만 이 문제에서는 단방향으로 해야 합니다. 단방향으로 자신보다 높은 성적을 가진 친구들의 그래프, 단방향으로 자신보다 낮은 성적을 가진 친구들의 그래프를 가지고 있다면 해당 번호의 등수의 범위를 쉽게 알 수 있습니다.

가령 3번의 등수를 찾기 위해서는 3번보다 높은 등수의 친구들이 몇 명인지 찾아야 합니다. 위에서는 1, 2번으로 최소 3등이라는 것을 알 수 있습니다. 반대로 3번보다 낮은 등수의 친구들이 몇 명인지 파악합니다. 4, 5번으로 전체 5명 중 2명보다 상위이기 때문에 최대 3등이라는 것을 알 수 있습니다.

코드 작성하기

그럼 코드를 직접 작성해 보겠습니다.

입력 받기

N, M, X = map(int, input().split())

win_arr = [[] for _ in range(N+1)]
lose_arr = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    lose_arr[a].append(b)
    win_arr[b].append(a)

전체 인원인 N명의 학생, 총 질문 수 M번, 등수를 알고 싶은 학생 X를 입력으로 받습니다. 다음으로 M번의 질문을 통해 학생들의 관계를 입력 받습니다. win_arr에는 자신보다 등수가 높은 학생들로 연결되고, lose_arr에는 자신보다 등수가 낮은 학생들로 연결 됩니다. 따라서 어떤 학생을 기준으로 win_arr에 몇 명이나 연결되어 있는지 확인하면 최대 몇 등인지 알 수 있습니다. 자신보다 잘하는 친구들 3명이 앞에 있다면 아무리 잘해도 4등이상 할 수 없습니다.

반대로 lose_arr에 몇 명이나 연결되어 있는지 확인하면 최소 몇 등이 되는지 알 수 있습니다. 전체 인원이 10명인데 자신보다 등 수가 낮은 친구들이 2명 있다면 10 - 2로 최소 8등을 할 수 있다는 것을 알 수 있습니다.

BFS 함수

from collections import deque

visited = [False] * (1+N)
def bfs(x, arr):
    q = deque([x])
    cnt = 0
    while q:
        node = q.popleft()
        for nxt in arr[node]:
            if visited[nxt]:
                continue
            visited[nxt] = True
            q.append(nxt)
            cnt += 1
            
    return cnt

간단한 bfs 함수 입니다. arr에 연결되어 있는 친구들이 몇 명인지 cnt를 통해 확인할 수 있습니다. 마지막에 cnt를 리턴하여 원하는 자신보다 등수가 높은 친구들이 몇 명인지, 반대로 자신보다 등수가 낮은 친구들이 몇 명인지 확인할 수 있습니다.

출력하기

U = bfs(X, win_arr)
V = bfs(X, lose_arr)

print(f'{U + 1} {N - V}')

U는 자신보다 등 수가 높은 친구들이 몇 명인지 알 수 있습니다. V는 자신보다 등 수가 낮은 친구들이 몇 명인지 알 수 있습니다.

자신보다 등 수가 높은 친구가 없다면 0이 리턴됩니다. 이 경우 자신의 위치인 1을 더해 1등이 됩니다. 자신의 앞에 있는 친구의 수에다가 1을 더해 몇 등인지 파악이 가능합니다.

V는 자신보다 낮은 등수의 친구들이 몇 명인지를 확인할 수 있습니다. 전체 인원에서 V값을 빼 최소 몇 등인지 확인할 수 있습니다.

visited의 경우 U를 구할 때, V를 구할 때 각각 초기화를 해야되는거 아닌가 생각할 수 있습니다. 하지만 그럴 필요가 없습니다. 왜냐하면 문제에서 입력이 정확하다는 점을 보장하였기 때문입니다. 어떤 친구 X를 기준으로 자신보다 등수가 높으면서, 낮은 경우가 없습니다. 즉 한 번 방문한 친구는 더 이상 방문하는 경우가 없다는 뜻입니다. 따라서 visited를 매 번 초기화 하지 않아도 됩니다.

전체 코드

전체 코드를 확인해 보겠습니다.

from collections import deque

N, M, X = map(int, input().split())

win_arr = [[] for _ in range(N+1)]
lose_arr = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    lose_arr[a].append(b)
    win_arr[b].append(a)

visited = [False] * (1+N)
def bfs(x, arr):
    q = deque([x])
    cnt = 0
    while q:
        node = q.popleft()
        for nxt in arr[node]:
            if visited[nxt]:
                continue
            visited[nxt] = True
            q.append(nxt)
            cnt += 1
    return cnt

U = bfs(X, win_arr)
V = bfs(X, lose_arr)

print(f'{U + 1} {N - V}')