BOJ (C/C++, Java) 10159번: 저울

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

 

---

풀이

처음엔 dfs로 연결된 노드들을 탐색하려 했으나, 같은 루프에 있는 값인지를 확인하기 어려워 답을 봤다.

플로이드-워셜을 모든 노드 간의 관계를 조회하도록 하는 방법을 사용했는데 떠올리지 못 했다.

 

풀이 참고

https://loosie.tistory.com/264

[BOJ] 백준 10159번 저울 (Java)

 

---

C/C++ 코드

#include <cstdio>
#include <vector>
#include <string>

using namespace std;

int N;
int map[100][100];

int main() {
    // input
    int M;
    scanf("%d\n%d", &N, &M);


    for (int i = 0; i < N; i++) 
        map[i][i] = 1;

    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        map[a - 1][b - 1] = 1;
        map[b - 1][a - 1] = -1;
    }

    // search
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][k] == 1 && map[k][j] == 1)
                    map[i][j] = 1;

                if (map[i][k] == -1 && map[k][j] == -1)
                    map[i][j] = -1;
            }
        }
    }

    // output
    for (int i = 0; i < N; i++) {
        int known = 0;
        for (int j = 0; j < N; j++) {
            if (map[i][j] != 0)
                known++;
        }
        printf("%d\n", N - known);
    }

    return 0;
}

 

Java 코드

import java.io.*;

public class Main {
    private static int N;
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());
        int M = Integer.parseInt(bf.readLine());

        map = new int[N][N];
        for (int i = 0; i < N; i++)
            map[i][i] = 1;

        for (int i = 0; i < M; i++) {
            String[] input = bf.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            map[a - 1][b - 1] = 1;
            map[b - 1][a - 1] = -1;
        }

        // search
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][k] == 1 && map[k][j] == 1)
                        map[i][j] = 1;

                    if(map[i][k] == -1 && map[k][j] == -1)
                        map[i][j] = -1;
                }
            }
        }

        // output
        for (int i = 0; i < N; i++) {
            int known = 0;
            for (int j = 0; j < N; j++) {
                if (map[i][j] != 0) known++;
            }
            System.out.println(N - known);
        }
    }
}