Problem 문제풀이
롯데정보통신 코딩테스트를 대비해서 오랜만에 문제풀이를 해보았다. 간단히 문제를 설명하자면
n명의 선수가 있고 m번의 경기 결과가 있다. m번의 경기결과를 토대로 선수들의 순위를 몇 명이나
파악할 수 있는지 묻는 문제이다.
여기서 잠깐 시간 복잡도를 생각해보자. 선수는 100명밖에 없기 때문에 n^3까지는 충분히 가능하다.
선수간의 승리 여부를 간선의 유무로 생각하고 선수들을 정점으로 생각하여 그래프를 만들어보자.
한 선수의 등수를 알기 위해선 나머지 모든 선수와의 승,패 여부를 알 수 있으면 된다.
-
n+1*n+1의 graph를 생성한다. -
A가B를 이겼으면 graph[A][B] =true가 된다. -
플로이드 와샬 알고리즘을 사용하여 모든 정점간의 관계를 구한다.
-
한 정점에 대해 나머지 모든 정점과 승,패 여부를 알 수 있으면 answer을 1증가시킨다.
1.
bool graph[101][101];
2.
for(int i=0;i<results.size();i++)
{
int start = results[i][0];
int end = results[i][1];
graph[start][end]=true;
}
3.
for(int k=1;k<=n;k++) // 거쳐가는 정점
{
for(int i=1;i<=n;i++) //출발하는 정점
{
for(int j=1;j<=n;j++) //도착하는 정점
{
if(graph[i][k] && graph[k][j])
{
graph[i][j]=true;
}
}
}
}
4.
for(int i=1;i<=n;i++)
{
int cnt = 0;
for(int j=1;j<=n;j++)
{
if(graph[i][j] || graph[j][i])
{
cnt++;
}
}
if(cnt==n-1)
{
answer++;
}
}
문제를 보고 플로이드 와샬을 떠올릴 수 있다면 푸는데 그리 어렵지 않은 문제일 것이다.
오랜만에 푸는 문제라 조금 헤맸지만 여러분은 쉽게 풀 거라 믿는다. 전체 코드를 남기며 마무리한다.
#include <string>
#include <iostream>
#include <vector>
using namespace std;
bool graph[101][101];
int solution(int n, vector<vector<int>> results) {
int answer = 0;
for(int i=0;i<results.size();i++)
{
int start = results[i][0];
int end = results[i][1];
graph[start][end]=true;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(graph[i][k] && graph[k][j])
{
graph[i][j]=true;
}
}
}
}
for(int i=1;i<=n;i++)
{
int cnt = 0;
for(int j=1;j<=n;j++)
{
if(graph[i][j] || graph[j][i])
{
cnt++;
}
}
if(cnt==n-1)
{
answer++;
}
}
return answer;
}