백준 2617 자바 - 구슬 찾기 (BOJ 2617 JAVA)

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

 

  홀수인 N개의 구슬 중 '중간이 될 수 없으려면' 자신보다 무게가 작은게 (N/2+1)개 존재하거나, 무게가 큰게 (N/2+1)개 존재하면 된다. 예를들어 N이 7일 때 자신보다 큰게 4개라면 무조건 중간엔 가고싶어도 갈 수 없다.

빨간색을 기준으로 빨간색보다 큰게 N/2+1개이다. 나머지 2개는 크던 작던 상관없이, 빨간색을 가장 중간에 가깝게 놓아도(최악의 경우) 중간지점에는 갈 수 없다!

  이 문제는 다소 이해하기 난해할수도 있으나, 결국 '자신보다 큰게 (N/2+1)개 이상 있거나, 자신보다 작은게 (N/2+1)개 이상 있는 구슬의 갯수를 구하면 된다.'

그럼 어떻게 구할까? M개의 쌍에 대해 어느쪽이 무거운지 알려줬는데 이걸 단방향 그래프(=directed graph =유향 그래프 =방향 그래프)의 edge라 생각하면 쉽다!

 

  문제에서 제시된 예시를 단방향 그래프로 그려보겠다. 우선은 '무게가 큰 곳에서 작은 곳으로 간선이 있는 방향 그래프'를 그려본다.

이렇게 그려놓고 보면 무엇을 알 수 있을까? 각 지점에서 화살표를 따라 진행하면 자신보다 작은 지점을 모두 찾을 수 있다.

 

- 1 : 없음

- 2 : 2->1이므로 1보다 크다

- 3 : 없음

- 4 : 4->3에서 3보다 크고, 4->2->1에서 2와 1보다 크다. 즉 4는 3,2,1보다 크다.

- 5 : 5->1이므로 1보다 크다.

 

그럼 N=5일 때 N/2+1 = 3 이므로 4는 3가지보다 크기 때문에 중간에 올 수 없음을 알 수 있다.

다음으로 이번엔 '무게가 작은 곳에서 큰 곳으로 간선이 있는 방향 그래프'를 그려본다. 위 그래프의 역방향 그래프이다.

마찬가지 방식으로 1은 5,2,4의 3가지 보다 작으므로 중간에 올 수 없음을 알 수 있다.

 

  그럼 풀 수 있는 방법은 찾았고, 이젠 단순히 방향 그래프를 코드로 표현하고, 탐색만 돌리면 된다. 간선에 가중치는 없고 단순히 탐색 가능한지만 확인하면 되므로 bfs, dfs, 다익스트라 등 뭘 써도 상관없다. 내 경우엔 이렇게 N의 갯수가 적을 시 무지성으로 사용하기 딱 좋은 floyd-washall을 사용했다. 3중 반복문 한방에 모든 지점에서 모든 지점까지의 거리를 알 수 있고 구현도 매우 간단하지만, 시간 복잡도가 O(N^3)이라 N이 적을때만 사용할 수 있다는 치명적인 단점이 있는 알고리즘이다.

 

  예를들어 문제에서 나왔던 예시에 대해 간선이 무게가 큰 곳에서 작은 곳으로의 방향 그래프로 나타낼 경우, 인접행렬로 플로이드 와샬 알고리즘을 돌린 결과는 다음과 같다.

arr[row][column] 은 row -> column 으로의 거리를 나타낸다. 이 문제에서 거리는 의미가 없으며, 아무튼 갈 수만 있으면(거리가 무한이 아니고, 자기 자신만 아니라면) 자신보다 무게가 작은 지점이다.

 

그럼 위와 같이 row를 본다면 자신보다 작은게 몇 개 있는지 알 수 있다. 그럼 역방향 그래프에 대해 다시 계산할 것 없이 반대로 column -> row로 보면 자신보다 큰게 몇 개 있는지 알 수 있다.

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02600/BOJ_2617.java