99클럽 코테 스터디 6일차 TIL: 그래프

문제

https://www.acmicpc.net/problem/2458

풀이

일단 어떤 알고리즘을 사용해서 풀어야할 지 고민을 해봤다.

문제에 나와있는 그래프를 보면 4번만 자신의 키 순서를 명확히 할 수 있었다.
그 이유는 자기보다 작은 학생의 수 + 큰 학생의 수를 했을 때, 자기를 제외한 총 학생의 수이기 때문이다.

입력으로 키를 비교한 결과를 보여주고 있다.
이는 방향 그래프를 의미하며 문제에 나와있는 그래프와 동일하게 구현할 수 있다.

그래서 4번 학생을 시작노드로 DFS 혹은 BFS를 수행했을 때는 2번 6번에 도달할 수 있다.
이는 4번보다 큰 학생이 2번, 6번 총 2명이라는 뜻이다.

4번 보다 작은 노드는 어떻게 처리할 수 있을까.
4번 노드에 방문이 가능하다면, 4번보다 작다는 것으로 알 수 있지 않을까?
4번 노드로 방문이 가능한 노드들을 찾는 방법으로 간선의 방향을 반대로 하면 찾을 수 있지않을까?

위 그래프에서 4번 노드로 방문 가능한 노드들은 1, 3, 5번 노드이다.
방향을 반대로 설정하여 4번노드에서 DFS 혹은 BFS를 수행한다면 1, 3, 5번 총 3명에게 노드에 도달이 가능하다.

그렇다면 자신보다 작은 학생 (3) + 큰 학생 (2) 해서 나를 제외한 총 인원(5) 이므로, 자신의 순서를 명확하게 알 수 있다.

방향을 반대로 구현하기 위해서 두 그래프 배열을 만들어 간선들을 저장했다.
그리고 총 1번노드부터 n번노드까지 DFS를 두번 수행하여 작은 학생의 수와 큰 학생의 수를 구하는 방식으로 구현하였다.

먼저 DFS로 풀이하였는데, BFS로 해도 무방할 것 같아 BFS로도 풀어보았다.

소스코드

후기

그래프 알고리즘에 대한 약간의 응용이 들어간 문제였고 재밌는 문제였다.
문제를 풀고 알고리즘 분류를 확인해보니 그래프이론, DFS, 플로이드워셜, 최단경로 등이 있었지만 BFS는 없었다.
그냥 BFS도 머 그래프이론이니..
그런데 플로이드워셜로 풀 생각은 못해봤는데 풀어봐야겠다.