문제
중간 번호가 될 수 없는 구슬의 개수를 구하는 문제
- n 구슬의 개수 (1 ≤ n ≤ 99, n은 홀수)
- m 무게 정보의 개수 (1 ≤ M ≤ N(N-1)/2)
- 설명
만약 문제의 입력이 다음과 같이 주어지면
5 4
2 1
4 3
5 1
4 21) 구슬의 개수는 5개이며,
2) 무게 정보는 다음과 같다.
구슬 2번이 구슬 1번보다 무겁다.
구슬 4번이 구슬 3번보다 무겁다.
구슬 5번이 구슬 1번보다 무겁다.
구슬 4번이 구슬 2번보다 무겁다.- 출력, 첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.
- 시간 제한 1초
- 문제 링크
풀이 과정
1. 무슨 문제
문제를 보면, 굉장히 그래프 문제 처럼 생겼다. 정점의 수, 간선의 수가 조금 노골적으로 주어졌다는 느낌을 받았다.
중간 번호가 될 수 없는 구슬의 개수를 구하는 문제이고, 중간 번호란 N(N-1)/2 을 의미한다.
그렇기 때문에, 그래프 탐색하면서 현재 구슬 보다 1) 가볍거나, 2)무거운 것의 개수가 중간 번호 N(N-1)/2 보다 크면, 중간 구슬이 될 수 없다.
그래프 탐색을 통해 중간 번호가 될 수 없는 구슬의 개수를 구해보자!
2. BFS, DFS
사실 문제 분류에 DFS가 적혀 있지만... BFS, DFS 무엇을 사용하든 상관없다.
(그리고, 알고리즘이 딱 무엇이다라고 한정하는건 좋아하지 않지만, 그냥 BFS, DFS에 대한 저의 생각은 다음과 같습니다...)
1) BFS
BFS를 사용하는 목적은 최단경로를 구할때 (단, 모든 간선의 가중치가 1일때)
2) DFS
DFS을 사용하는 목적은 시작점에서 끝점까지 도달하는 경로로 무언가를 얻고 싶을 때
3) 이 문제의 목적은?
이 문제에서의 탐색은 특별한 목적 없이 모든 정점을 방문하는 완전 탐색이기 때문에 무엇이든 상관없다.
3. 그래프 탐색
1) 목적
현재 구슬 보다 무겁거나 가벼운 구슬의 개수를 구하는 것이 목적
2) 개수
무겁가나 가벼운 구슬의 개수는 현재 구슬에 도달 할 수 있는 구슬의 개수이다.
3) 도달
구슬을 정점, 무게 정보를 간선이라고 했을때 BFS를 쓰든, DFS를 쓰든 상관없다. 시작 구슬에서 도달 할 수 있으면 된다.
4) 그래프 설계
무게 정보를 보면 간선이 한 방향이다. 이렇게 주어졌기 때문에 나보다 가벼운것만 알 수 있다. 인접 리스트를 하나 더 만들고 간선을 거꾸로 넣어준다. 결과적으로, 그래프 탐색을 **1) 정방향, 2) 역방향 두번* 돌아준다.
4. 더 생각해볼 내용
플로이드 와샬 로도 풀 수 있습니다. n^4 걸립니다. (n^3 을 n번 수행)
이 문제의 경우 시작점에서 간선을 따라 방문할 수 있는 모든 정점의 개수를 구하는 완전 탐색문제라고 생각했습니다.
하지만, 1) 시작점에서 모든 정점의 까지의 거리를 무한대로 놓고, 2) 시작점에서 해당 정점까지 최단경로가 생기는 경우에도 방문할 수 있는 정점이기 때문에. 최단 경로로 풀어도 될것 같습니다.
n^3 걸리는 플로이드 와샬도 사용했으면 다른 최단경로 알고리즘도 가능하겠지만.
그냥 제가 하고 싶은말은...음, BFS, DFS 사용 목적 이라고 적었지만, 이 알고리즘은 이럴때 사용하는거 라고 딱! 생각을 한정하는 것 보다는 넓은 가능성에서 봤을 때 이렇게 사용하기도 하는구나라고 생각하는게 좋은 것 같습니다.
1. C++
1) DFS
#include <iostream>
#include <vector>
#define max_int 101
using namespace std;
/*
시간 복잡도: O(n^2+nm)
공간 복잡도: O(n+m)
사용한 알고리즘: DFS
사용한 자료구조: 인접 리스트
설명: 정방향, 역방향 DFS를 각각 진행했을때 자신의 순서가 중간번호보다 크다면 중간 숫자가 될 수 없다.
*/
int n, m, a, b, cnt, rcnt, result, baseNum;
bool check[max_int], rcheck[max_int];
// 정방향 간선의 정보를 저장할 인접리스트 v
vector<int> v[max_int];
// 역방향 간선의 정보를 저장할 인접리스트 r
vector<int> r[max_int];
// 정방향 dfs
void dfs(int node){
check[node] = true;
for(int i=0; i<v[node].size(); i++){
int next = v[node][i];
if(!check[next]){
cnt++;
dfs(next);
}
}
}
// 역방향 dfs
void rdfs(int node){
rcheck[node] = true;
for(int i=0; i<r[node].size(); i++){
int next = r[node][i];
if(!rcheck[next]){
rcnt++;
rdfs(next);
}
}
}
// 방문 기록 및 방문 개수 초기화
void clear(){
cnt = 0;
rcnt = 0;
for(int i=1; i<=n; i++){
check[i] = false;
rcheck[i] = false;
}
}
int main(){
// 1. 입력
scanf("%d %d", &n, &m);
// 2. 간선의 정보를 입력받는다.
for(int i=0; i<m; i++){
scanf("%d %d", &a, &b);
// 1) 정방향은 인접 리스트 v에 넣고
v[a].push_back(b);
// 2) 역방향은 인접 리스트 r에 넣는다.
r[b].push_back(a);
}
// 3. 무게 순서 중간인 숫자를 계산한다.
// 예) n이 5일 때 baseNum 은 3이다.
baseNum = (n+1)/2;
// 4. 각 정점마다 DFS 수행
for(int i=1; i<=n; i++){
// 1) 방문 기록 및 방문 개수 초기화
clear();
// 2) 정방향, 역방향 DFS 각각 돌아준다.
dfs(i);
rdfs(i);
// 3) 정방향, 역방향 순회 결과
// 순서가 중간 번호 보다 크다면, 절대 중간 번호가 될 수 없다.
if(cnt >= baseNum || rcnt >= baseNum){
result++;
}
}
// 5. 출력
printf("%d\n", result);
}
2) BFS
#include <iostream>
#include <vector>
#include <queue>
#define max_int 101
using namespace std;
/*
시간 복잡도: O(n^2+nm)
공간 복잡도: O(n+m)
사용한 알고리즘: BFS
사용한 자료구조: 인접 리스트
설명: 정방향, 역방향 BFS를 각각 진행했을때 자신의 순서가 중간번호보다 크다면 중간 숫자가 될 수 없다.
*/
int n, m, a, b, cnt, rcnt, result, baseNum;
bool check[max_int], rcheck[max_int];
// 정방향 간선의 정보를 저장할 인접리스트 v
vector<int> v[max_int];
// 역방향 간선의 정보를 저장할 인접리스트 r
vector<int> r[max_int];
// 정방향 bfs
void bfs(int start){
check[start] = true;
queue<int> q;
q.push(start);
while(!q.empty()){
int node = q.front();
q.pop();
for(int i=0; i<v[node].size(); i++){
int next = v[node][i];
if(!check[next]){
check[next] = true;
cnt++;
q.push(next);
}
}
}
}
// 역방향 bfs
void rbfs(int start){
rcheck[start] = true;
queue<int> q;
q.push(start);
while(!q.empty()){
int node = q.front();
q.pop();
for(int i=0; i<r[node].size(); i++){
int next = r[node][i];
if(!rcheck[next]){
rcheck[next] = true;
rcnt++;
q.push(next);
}
}
}
}
// 방문 기록 및 방문 개수 초기화
void clear(){
cnt = 0;
rcnt = 0;
for(int i=1; i<=n; i++){
check[i] = false;
rcheck[i] = false;
}
}
int main(){
// 1. 입력
scanf("%d %d", &n, &m);
// 2. 간선의 정보를 입력받는다.
for(int i=0; i<m; i++){
scanf("%d %d", &a, &b);
// 1) 정방향은 인접 리스트 v에 넣고
v[a].push_back(b);
// 2) 역방향은 인접 리스트 r에 넣는다.
r[b].push_back(a);
}
// 3. 무게 순서 중간인 숫자를 계산한다.
// 예) n이 5일 때 baseNum 은 3이다.
baseNum = (n+1)/2;
// 4. 각 정점마다 BFS 수행
for(int i=1; i<=n; i++){
// 1) 방문 기록 및 방문 개수 초기화
clear();
// 2) 정방향, 역방향 BFS 각각 돌아준다.
bfs(i);
rbfs(i);
// 3) 정방향, 역방향 순회 결과
// 순서가 중간 번호 보다 크다면, 절대 중간 번호가 될 수 없다.
if(cnt >= baseNum || rcnt >= baseNum){
result++;
}
}
// 5. 출력
printf("%d\n", result);
}3) 플로이드 와샬
#include <iostream>
#include <vector>
#include <queue>
#define max_int 101
using namespace std;
int n, m, a, b, cnt, rcnt, result, baseNum, d[max_int][max_int], r[max_int][max_int], pd[max_int][max_int], pr[max_int][max_int];
/*
시간 복잡도: O(n^4)
공간 복잡도: O(n^2)
사용한 알고리즘: 플로이드 와샬
사용한 자료구조: 인접 행렬
설명: 플로이드 와샬을 통해 시작점에서 도달할 수 있는 모든 구슬을 구한다.
도달 할 수 있으면 나보다 무겁거나, 가볍다는 의미
이 때의 무겁거나 가벼운 구슬의 개수가 중간번호(n+1)/2 보다 크면 이 구슬은 중간 구슬이 될 수 없다.
*/
void clear(){
cnt = 0;
rcnt = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
d[i][j] = max_int;
r[i][j] = max_int;
if(pd[i][j] == 1) d[i][j] = 1;
if(pr[i][j] == 1) r[i][j] = 1;
}
}
}
int main(){
scanf("%d %d", &n, &m);
baseNum = (n+1)/2;
for(int i=0; i<m; i++){
scanf("%d %d", &a, &b);
pd[a][b] = 1;
pr[b][a] = 1;
}
for(int node=1; node<=n; node++){
clear();
for(int k=1; k<=n; k++){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(d[i][j] > d[i][k] + d[k][j]){
d[i][j] = d[i][k] + d[k][j];
}
if(r[i][j] > r[i][k] + r[k][j]){
r[i][j] = r[i][k] + r[k][j];
}
}
}
}
for(int j=1; j<=n; j++){
if(d[node][j] != max_int) cnt++;
if(r[node][j] != max_int) rcnt++;
}
if(cnt >= baseNum || rcnt >= baseNum){
result++;
}
}
printf("%d\n", result);
}
중간 번호가 (N+1)/2 인데 위에 오타가 난 듯 하네요!