[백준(BOJ)] 10159번 : 저울 - C++[CPP]

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

10159번: 저울

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 플로이드-와샬

 

---

 

⊙ 문제 접근 과정

 

입력받을 때, 해당 경로에 대해 1이라는 값을 표시해준다.

플로이드 와샬로 검사하여 만약 거쳐갈 수 있다면 또다시 1 표시

 

1 표시가 둘 다 안 되어 있다면 count up!

N까지 다 돌고 count 출력 해준 뒤, count를 다시 0으로 초기화

 

다음 번호, 마지막 번호까지 반복

 

---

 

⊙ 문제 풀이

 

#include <iostream>

using namespace std;
#define MAX 101

int N, M, cnt;
int arr[MAX][MAX];

int main() {
    cin >> N >> M;

    for(int i=0;i<M;i++) {
        int a,b;
        cin >> a >> b;

        arr[a][b]=1; // 갈 수 있다고 표시
    }

    //플로이드 와샬
    for(int k=1;k<=N;k++) { //k = 거쳐가는 노드
        for(int i=1;i<=N;i++) { // i = 출발 노드
            for(int j=1; j<=N;j++) { // j = 도착 노드
                if(arr[i][k] && arr[k][j]) //만약 거쳐갈 수 있다면
                    arr[i][j] = 1; // 갈 수 있다고 표시
            }
        }
    }

    for(int i=1;i<=N;i++) {
        cnt=0; //초기화
        for(int j=1;j<=N;j++) {
            if(!arr[i][j] && !arr[j][i]) cnt++; //갈 수 없다면 count up
        }
        cout << cnt-1 << "\n"; //바로 출력
    }
}

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!