[백준] 2458 키 순서

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

2458번: 키 순서

https://codeup.kr/problem.php?id=4714

키 순서

#1 시작

코드업 BFS/DFS 문제집을 성공률순으로 정렬해 지뢰찾기2까지 푸는 동안 계속 못풀었던 문제,,,
나름 이렇게 저렇게 풀이를 세웠는데, 도대체 어떻게 구현해야할지 막막해서 손놓고 있었다.
플로이드 워셜 알고리즘을 알아야 풀수 있다는데, 플루이드 워셜은 DP에 가까운 알고리즘이라 아직 건드리고싶지 않았다.
그리고 처음에 세운 풀이는 플루이드 워셜을 쓰지 않았기 때문에, 어떻게든 풀 수는 있을것이라고 생각하다가 도저히 못풀겠어서
구글신의 도움을 청하던 중, 나와 풀이법이 똑같은 분의 코드를 만나게 되었다.
결국 해결했고, 참 얻어가는 것이 많았던 문제.

#2 접근

자신의 키가 몇번째인지 알 수 있는 조건은 다음과 같다.

자신보다 큰 학생 수  + 자신보다 작은 학생 수 =  전체학생수 - 1 

자신보다 작은 학생 수는 DFS탐색을 실행하면 될것 같았다.
최초에 방문엔 노드엔 0을, 그 다음 방문한 노드엔 1을, 그 다음 방문한 노드엔 이전노드값+1 을 해서 쭉쭉쭉....
그렇게 들어오는 간선이 없는 노드들을 시작으로 탐색하고 나면 모든 학생이 자신보다 작은 학생 수가 몇명 있는지 알 수 있다.
(이때는 이미 방문했을경우는 어떻게 처리해야하는지에 대한 생각을 같이 엮어서 생각치는 못했다)
이때 문제는 최초에 방문할 노드들을 정하는 방법에 있었는데, 입력받을때 어떤 정점에 연결되는 간선들을 기록해 들어오는 간선이 없다면 방문할 노드로 설정한다..뭐 이런 아이디어를 냈었는데, 이게 맞을까? 구현하면 이게 맞겠지만 ㅠㅠ 너무 막 푸는 느낌이 들었다.

그리고 자신보다 큰 학생 수를 구하는건 어떻게 할것이냐는 두번째 문제에 막혔는데, 간선의 방향을 뒤집어 역방향으로 DFS를 탐색하면 구할수 있다는걸 찾아냈지만 ㅠㅠ,,, 그러면 함수도 따로만들고, 방문처리는 어떻게 해야하는지,,,,
한번에 하는 방법은 정말 없을까? 이대로 플로이드 워셜 알고리즘을 써야만 하는 것인가..?
하는 생각에 문제를 완전히 놓으려고 할때 쯤! 이분의 글을 발견했다.

#3 구현

자바로 구현해놓은 코드를 보며, 어떻게 동작하는것일까 끙끙대며 살피다 잠깐 접고 새로나온 민초맛 다이제를 먹으며 잠시 머리를 식힌후이런식으로 할수도 있구나 라는 큰 깨달음을 얻었다. 정말 상상치도 못했던 방법,,,ㅠㅠ 자 코드를 보자.

    for (int i = 0; i < M; ++i) {
        int tmp1, tmp2;
        cin>>tmp1>>tmp2;
        stu[tmp1].push_back(tmp2);
    }

먼저 입력부이다. 인접리스트 방식으로 구현했고, 행에 해당하는 정점에서 뻗는 정점을 삽입해줬다.

int DFS(int v,int visited[]){

    int front = 0;

    for (int i = 0; i < stu[v].size(); ++i) {
        int next = stu[v][i];
        if(visited[next]){
            continue;
        }
        back[next]++;
        visited[next] = 1;
        front += DFS(next, visited);
    }
    return front + 1;

}

다음으로 탐색부를 살펴보자. 평범한 DFS구조다. 단, 단방향 그래프에다가 자신보다 큰 정점과 연결된 상태에서 그 정점보다 큰 정점이 다시 그보다 작은 정점으로 간선이 뻗는 경우는 없기때문에 visited는 단지 방문 여부만 확인하는 용도로 썼다.
한번 방문한 정점은, 다시 방문할 수는 있지만 카운트는 오르면 안된다.
즉, 특정 정점에서 깊이우선탐색을 시행해 뻗어나가는 모든 정점들에 대해 한번씩 카운터를 쌓고, 이를 모든 정점에 대해 시행하는 것이다.
front 변수는 앞으로 탐색하는 정점, 즉 자신보다 큰 키인 학생 수가 몇명 있는지 세는 변수다.
이러면 자신이 뻗은 정점과, 그 정점에 연결된 정점의 수를 저장하는 것과 같기때문에 자신보다 키가 큰 학생수를 세는것과 같다.
함수가 끝날때 front+1로 끝나는데, 재귀가 끝나고 되돌아오며 첫 호출 함수가 끝날때 재귀구조를 완성시키려고 처음부터 1을 더했으므로 저장할때는 1을 빼고 저장한다. (자기 자신은 자기 자신보다 크지 않기 때문이다.)
이것을 보고 정말 크게 감탄했다....!

    for (int i = 1; i < N+1; ++i) {
        int visited[500]={0,};
        front[i] = DFS(i, visited) - 1;
    }

그러한 연고로 시행부는 이렇다.
방문 배열은 함수가 시작할 때 마다 초기화된다.
저 정점에서 시작해 이미 방문한 정점은, 이번 정점 입장에선 아직 방문한 정점이 아니기 때문에 ^^...
풀어보면 무슨 말인지 알것이다.

    for (int i = 1; i < N + 1; ++i) {
        if(front[i] + back[i] == N - 1){
            answer++;
        }
    }

이제 처음으로 돌아와서, 자신보다 큰 학생 수  + 자신보다 작은 학생 수 =  전체학생수 - 1  를 만족하는 경우를 센 후에, 리턴해주면 끝!

#4 마무리

그리고 문제를 푼 후에 알고리즘에 문제가 없다고 생각한 저는 자신 만만하게 제출을 눌렀지만..

..?

생각해보니 나 저장공간을 어떻게 할당했더라...?

나는 메모리 관리에 나름 엄격한 편이라, 유연할 필요가 없는 경우엔 손수 공간을 할당한다.
이러면 최악의 상황이든 아니든 간에 메모리가 얼마나 할당되는지 체크할 수 있기 때문.
문제는 내 코드에 있었다.

int N,M;
vector<int> stu[250 * 499];

int back[500] = {0, };
int front[500] = {0, };

그리고 이 문제는 인덱스를 0번이 아닌 1번부터 할당하니, 공간을 500이 아니라 501 이상 할당해주었어야 했다. ㅎㅎ....

good!

세그먼트 오류가 뜨지 않고, 틀린 풀이라고 떠서 당황했지만 입력부를 보고 아차 싶었다.
아마 코드업이 아니라 백준이었다면 잡는데 한참 걸렸을 것이다.

DFS에서 카운터를 이용하면 방문한 정점의 개수를 알수 있다는 점, 메모리 공간에 항상 유의해야 한다는 점!
꼭꼭 잊지 말자.