C++: 순위

https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스에서 추천문제로 주어진 문제이다. 그래프 문제는 오랜만에 접해봐서 푸는게 약간은 새롭다.

조건

• 복싱 경기를 치룬 선수들이 n명있다.
• 누가 누구와 싸워서 이겼는지 목록으로 주어진다.
  • 4번 선수가 3번 선수를 이겼으면 [4, 3]이며, 이것들이 모여 [[4, 3], [4, 1], …] 처럼 주어진다.
  • 경기 결과들 조합에 순위를 정하는데 있어서 모순은 없다. 가위바위보처럼 순환관계가 발생하지 않는다는 말일 것이다.
• 다만 일부 경기 결과들을 분실해버렸다. 당장 순위를 확정할 수 있는 선수가 몇명인지 찾아야 한다.

  그래프

  하나의 노드에서 다른노드로의 연결로 구성된 자료구조를 그래프라고 부른다. 그렇기에 크게 보면 다른 모든 자료구조도 특수한 규칙을 가진 그래프라고 볼 수 있다. 트리는 각 노드가 부모, 자식2개까지 3개의 연결을 가지고 노드값 사이에 규칙을 가진, 리스트는 앞뒤로 2개의 연결을 가진 그래프로 치환할 수 있다. 다만 보통 그래프라 함은 그런 특수한 자료구조가 아닌, 정말로 각 노드가 랜덤한 연결 갯수를 가질 수 있는 자료구조를 말한다. 그래프는 지도를 데이터 형태로 변환하여 이동거리를 계산하거나, 신경망의 구조를 복사하는등 복잡한 구조의 데이터를 표현하는데 사용할 수 있다. 그래프를 표현하는 방법은 크게 노드의 갯수만큼의 길이를 가진 정사각형 배열을 이용하는 인접 행렬(Adjecency Matrix)방식과, 노드들의 연결만 가진 집합으로 표현하는 인접 리스트(Adjecency list)방식이 있다. 전자는 접근속도와 탐색,수정이 빠르지만 공간을 처음부터 크게 차지한다는 단점이 있고, 후자는 그 반대로 존재하는 연결만 남기기에 공간은 덜차지하지만 탐색하고 수정하는데 시간이 더 필요할 수 있다. 문제에서 주어진 구조는 어느 선수가 어느 선수를 이겼는지, 즉 존재하는 관계만 리스트로 주어지기에 후자라고 할 수 있다. 다만 여기에 방향성, 어느 노드에서 어떤 노드로만 갈수있는지 연결에 방향이 존재한다는 점만 추가하면 지금 문제의 구조와 같다. 연결의 가중치(Weight)와 다른 개념까지 들어가면 설명할 내용이 많으니 찾아보도록 하자. 이번 문제에서 주로 활용할 요소는 그래프의 탐색이다.

  풀이

  연결에 방향성이 존재하지 않는, 그러니까 연결에 있어 양쪽으로의 이동이 모두 가능하다는 전제가 붙은 그래프에서는 탐색을 하는게 보다 용이하다. 다만 현재 문제는 방향이 존재하는, 특정한 선수가 다른 선수를 이긴 관계를 나타내는 유향 그래프이기 때문에 탐색이 더 성가시다. 어떤 노드에서 탐색을 시작하는지에 따라 탐색할 수 있는 그래프의 영역이 달라지기 때문이다. 이긴 선수 노드에서 진 선수 노드로만 이동할 수 있다고 한다면, 꼴지 선수 노드에서 움직이는건 자기자신만 확인할 수 있겠지만, 1등선수 노드에서 움직이면 모든 선수 노드를 다 확인할 수 있을 것이다. 때문에 지금 문제에서 모든 선수의 순위를 특정하기 위해서는 모든 선수에서 각각 시작해 탐색을 진행해보아야 한다. 선수 위와 아래로 각각 몇명이 있는지 확인할 수 있어야 순위를 특정할 수 있지 않겠나? 그래서 생각한 알고리즘의 흐름은 다음과 같다.

  1. 선수 명수 만큼 긴 배열을 선언한다.
  2. 모든 선수 번호에 대해 다음을 반복한다.
  1. 선수 번호 노드에서 갈수 있는 모든 노드를 확인한다. (정방향)
  2. 확인된 노드 번호들에 대해 먼저 선언해놓은 배열에서 +1을 해놓는다.
  3. 선수 번호 노드로 올 수 있는 모든 노드를 확인한다(역방향)
  4. 확인된 노드 번호들에 대해 먼저 선언해놓은 배열에서 +1을 해놓는다.
     1. 모든 선수에 대해 반복이 끝난 후 배열에 남은 숫자가 선수의 명수와 동일한 선수들을 세어서 반환한다. * 다른 번호 노드에서 자신을 방문했다면 자신을 이긴 선수다. * 특정 번호 노드에서 출발해 방문한 다른 노드들은 그 번호 선수가 이긴 노드들이다. * 이 두 수에 자기자신까지 두번 카운트한 + 1해서 전체 선수와 같다면, 자신이 몇위인지 특정 가능한 선수다. 어차피 모든 선수에서 반복하고, 방문 순서가 아닌 방문 가능 여부만 확인하면 되기에, 깊이 우선 탐색(DFS)인지 아니면 너비 우선 탐색(BFS)인지는 상관 없겠다. 다만 탐색 과정에서 방문한 노드들을 확인하긴 해야하기에 하나의 함수로 결합해놓기위해 BFS를 쓰도록 하겠다. ```c++ #include #include #include

using namespace std;

int solution(int n, vector<vector> results) { vector Players(n, 0); //접근 가능 선수 카운트 //모든 노드에 대해 BFS, 접근가능한 노드 수 + 1만큼 저장 for (int i = 0; i < n; i++) { //정방향 탐색(이긴 상대) vector Visited(n, false); queue SearchQueue; SearchQueue.push(i); while (!SearchQueue.empty()) { if (Visited[SearchQueue.front()]) { SearchQueue.pop(); continue; } int Current = SearchQueue.front(); SearchQueue.pop(); Visited[Current] = true; for (int j = 0; j < results.size(); j++) { if (results[j][0] == Current + 1) { SearchQueue.push(results[j][1] - 1); } } } for (int j = 0; j < n; j++) { Players[i] += Visited[j]; } //역방향 탐색(진 상대) Visited = vector(n, false); SearchQueue.push(i); while (!SearchQueue.empty()) { if (Visited[SearchQueue.front()]) { SearchQueue.pop(); continue; } int Current = SearchQueue.front(); SearchQueue.pop(); Visited[Current] = true; for (int j = 0; j < results.size(); j++) { if (results[j][1] == Current + 1) { SearchQueue.push(results[j][0] - 1); } } } for (int j = 0; j < n; j++) { Players[i] += Visited[j]; } } //Players 카운트 확인 후 전체 선수 + 1과 같으면 answer+1 int answer = 0; for (int i = 0; i < n; i++) { if (Players[i] == n + 1) { answer++; } } return answer; } ``` 다만 지금은 전체 선수가 100명 이하라 괜찮았지만, n명의 선수와 m명의 경기에 대해 시간복잡도가 $O(n*m)$으로 높다. 만약 표본수가 더 많아진다면, 방식 자체는 유사하더라도 BFS/DFS대신 다른 방법으로 가야 제시간안에 풀릴 것이다.