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

1 ~ N 번의 번호가 붙은 학생이 있다. 두 학생끼리 키를 비교한 결과가 주어지는데, 이 결과를 통해서 본인의 키 순서를 알 수 있는 학생이 몇 명인지 구하는 문제이다. (단, 모든 학생의 키는 다르다.)

2458번: 키 순서

 

 

---

풀이 과정

학생의 키가 몇 번째인 지 알려면 그 학생은 대소 관계에 있어서 모든 학생과 연결돼 있어야 한다. 즉 모든 학생을 노드로 하고, (키가 작은 학생 -> 키가 큰 학생)으로 노드를 연결한다고 했을 때, 모든 학생과 연결돼 있다면, 그 학생의 키 순서를 알 수 있다. 이를 위해서는 주어지는 두 학생의 키 대소 관계를 바탕으로 다른 학생과 연결해야 한다.

ex)

case 1:
input : 
3 3
1 2
3 1
3 - > 1 -> 2로 연결할 수 있고, 세 학생 모두 다른 학생과 연결돼 있으며, 키 순서를 알 수 있다.

case 2:
input:
6 4
1 2
2 4
2 5
5 6

case2의 연결 상태

위 그림과 같이 연결할 수 있으며 1, 2 의 키 순서를 알 수 있다. (5, 6번은 4번 학생과의 키 관계를 알 수 없으므로 세 학생의 키 순서를 정확히 알 수 없다.)

이처럼 주어진 연결 정보를 통해 다른 정점으로 연결을 확장한 다음에, 자신을 제외한 모든 정점과 연결돼있는지 확인하면 된다. 다른 정점으로 연결을 확장하는 데는 '플로이드-워셜 알고리즘'을 활용한다.

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

플로이드-워셜 알고리즘은 모든 정점에서 다른 모든 정점 간의 거리를 구하는 알고리즘이다. 여기서는 연결 여부를 검사하면 되므로 배열의 값으로 거리 대신 연결 여부(True / False)를 넣는다.

이렇게 플로이드-워셜 알고리즘으로 모든 정점간의 연결 여부가 나오게 되면, 각 정점마다 반복하며 다른 모든 정점들과 연결돼 있는지 확인한다. 이후 모든 정점과 연결된 정점의 개수를 정답으로 출력한다.

---

소스코드

#include <iostream>
#define MAXN 501
using namespace std;
 
 
bool arr[MAXN][MAXN] = { false };
 
int main(void) {
    int N, M;
    int a, b;
    int ans = 0;
 
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        arr[a][b] = true;
    }
 
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            if (k == i)
                continue;
            for (int j = 1; j <= N; j++) {
                arr[i][j] = (arr[i][j] | (arr[i][k] & arr[k][j]));
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        bool flag = true;
        for (int j = 1; j <= N; j++) {
            if (i == j || arr[i][j] || arr[j][i])
                continue;
            else {
                flag = false;
                break;
            }
        }
        if (flag) {
            ans++;
        }
    }
    cout << ans << endl;
}

 

주석추가

#include <iostream>
#define MAXN 501
using namespace std;
 
 
bool arr[MAXN][MAXN] = { false }; // 연결 여부를 저장할 배열
 
int main(void) {
    int N, M; // 학생의 수, 비교 횟수
    int a, b; // 키가 작은 학생, 키가 큰 학생
    int ans = 0; // 정답
 
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        arr[a][b] = true; // 키가 작은 학생 -> 키가 큰 학생 연결하기
    }
 
    //플로이드-워셜 알고리즘
    for (int k = 1; k <= N; k++) { //k:경유지, 경유지가 1 ~ N 까지
        for (int i = 1; i <= N; i++) { // 시작 위치
            if (k == i) // 시작위치와 경유지가 같다면 pass
                continue;
            for (int j = 1; j <= N; j++) { // 끝 위치
                arr[i][j] = (arr[i][j] | (arr[i][k] & arr[k][j])); // 시작위치와 끝 위치 연결 정보 갱신
            }
        }
    }
 
    //각 정점별로 다른 모든 정점과 연결돼있는지 확인
    for (int i = 1; i <= N; i++) {
        bool flag = true;
        for (int j = 1; j <= N; j++) {
            if (i == j || arr[i][j] || arr[j][i]) // i와 j가 같은 노드이거나, i -> j, j -> i 중 연결 돼 있는 방향이 있다면
                continue;
            else { //연결돼 있지 않다면
                flag = false; 
                break;
            }
        }
        if (flag) {
            ans++; //반복을 다 돌았는데 모든 정점과 연결 돼 있다면 정답 + 1
        }
    }
    cout << ans << endl;
}

 

정점 간 연결 여부는 bool 값을 통해 True / False로 계산했다. 25번째 라인(주석 추가 26번째 라인)의 연결 정보 갱신 과정은 비트 연산을 통해 계산했다.

| : or 연산
& : and 연산

arr[i][j]가 이미 true였던 경우 뒤의 값과 상관없이 arr[i][j]가 true로 갱신되며, arr[i][j]가 false 였다면, arr[i][k]와 arr[k][j]가 모두 true 여야 arr[i][j]가 true로 갱신된다.

---

실행 결과

코드 실행 결과