[C++] BOJ 백준 - 키 순서 (2458)

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

2458번: 키 순서

 

문제 설명 : 

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다. 

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다. 

 

출력 : 

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다. 

 

예제 입력 : 

6 6
1 5
3 4
5 4
4 2
4 6
5 2

 

예제 출력 : 

1

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

3) 공간복잡도

 

 

TIL

1) 풀면서 놓쳤던점

오늘 아침에는 내가 (완전) 잘못 접근했고

그 이후로는 테스트 케이스 잘 나오고 알고리즘적으로는 절대절대 이상한게 안보이는데 계속 시간초과났다 .. 결국 강사님께 SOS 쳤는데 .. !

 

내가 시간 초과 난 이유 : set 자체가 느릴뿐더러, set을 clear하는게 특히 더 오래걸리는듯하다 ..

ㅎ 기본기 부족한 스스로를 탓하며 ..

 

사실 알고리즘 짜놓고도 indegree, outdegree 배열 등 디게 비효율적으로 구현한거 같긴했어서 좀 부끄러웠지만 ^^ 무튼 시간복잡도 문제는 없어보였는데.. !! 이런문제였다니 역시 경험지 + 개념 중요중요

 

글구 vector 관련해서 설마설마 알고리즘을 잘못 짠건가 싶었는데 그게 아니라서 정말 다행수 .. 마니 슬퍼질뻔 ..

결국 set말고 visit배열로 dfs 돌리니 잘 작동했다 흑흑흑

혹시모르니 기록기록

 

- 시간 초과 관련 set 사용한 코드

#include<cstdio>
#include<vector>
#include<set>
int N, M, a, b, indegree[500+1], outdegree[500 + 1],an;
std::vector<int>down[500 + 1];
std::vector<int>up[500 + 1];
std::set<int>node;

void dfs(int curr) { //아래로 향하는 dfs
    if (outdegree[curr] == 0) {
        return;
    }
    for (auto next: down[curr])
    {
        node.insert(next);
        dfs(next);
    }
    return;
}
void rdfs(int curr) { //윗방향으로 향하는 dfs
    if (indegree[curr] == 0) {
        return;
    }
    for (auto next : up[curr])
    {
        node.insert(next);
        rdfs(next);
    }
    return;
}
int main() {
    an = 0;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &a, &b);
        indegree[b]++;
        outdegree[a]++;
        down[a].push_back(b);
        up[b].push_back(a);
    }

    for (int i = 1; i <= N; i++) {
        // 1. 나보다 큰애들 DFS
        dfs(i);
        // 2. 나보다 작은애들 DFS
        rdfs(i);
        if (node.size()+ 1 == N)
            an++;
        node.clear(); //노드 갯수 초기화
    }
    printf("%d",an);
    return 0;
}

 

2) 이 문제를 통해 얻어갈 것

set .. 정말 필요할때만 쓰자 ..
set은 기본적으로 느리다
set을 clear하는것도 또한 느리다

저번에 다른 문제 풀때 set 쓰니까 중복안되게 알아서 insert되는거에 혹해서 함 써볼라했더니 하핫 꽤나 슬퍼유

글구 사실 이건 플로이드-워셜 알고리즘 관련한 문제라 나중에 그 방법으로 다시 풀어보려 한닷!!

오기로 끝까지 이 방법을 고수했던.. ㅎㅎ

 

정답 코드

#include<cstdio>
#include<vector>
int N, M, a, b, an,cnt;
std::vector<int>down[500 + 1];
std::vector<int>up[500 + 1];
bool visit[500 + 1];

void dfs(int curr,int prev) { //아래로 향하는 dfs
	if (prev != 0)
		visit[curr] = true;
	for (auto next: down[curr])
	{
		if (visit[next])
			continue;
		dfs(next,curr);
	}
	return;
}
void rdfs(int curr,int prev) { //윗방향으로 향하는 dfs
	if (prev != 0)
		visit[curr] = true;
	for (auto next : up[curr])
	{
		if (visit[next])
			continue;
		rdfs(next,curr);
	}
	return;
}
int main() {
	an = 0;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		down[a].push_back(b);
		up[b].push_back(a);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++)
			visit[j] = false;
		// 1. 나보다 큰애들 DFS
		dfs(i,0);
		// 2. 나보다 작은애들 DFS
		rdfs(i,0);
		cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (visit[j])
				cnt++;
		}
		if (cnt + 1 == N)
			an++;
	}
	printf("%d",an);
	return 0;
}