[백준 10159번] 저울

문제번호: https://www.acmicpc.net/problem/10159

 

 

문제 조건 정리

물건들의 무게를 상대 비교를 통해 주어지고, 각각의 물건들에 대하여 무게를 비교할 수 없는 물건의 개수를 출력해라.

 

 

나의 풀이(List [] 배열 + DFS)

1. 입력값으로 주어진 무게에 대하여 자신보다 작은 무게들에 대하여 List 배열로 받아서 값을 저장한다.
2. 마찬가지로, 자신보다 큰 무게들에 대하여 List 배열로 값을 저장한다.
3. Stack을 활용해서 구하고자 하는 물건에 대한 무게들을 순회하면서 자신보다 큰 것들 모두 방문배열로 방문 처리하고, 자신보다 작은 무게들도 방문 처리해서 전체 N개에 대하여 count 개수만큼 빼준다. (물론 자기자신도 포함한다.)

전체 코드이다.

package _250514;

import java.util.*;
import java.io.*;
/**
 *packageName    : _250514
 * fileName       : BOJ_G4_10159_저울
 * author         : moongi
 * date           : 5/14/25
 * description    :
 *
 * 자신보다 큰 정렬과 작은 정렬을 각각 저장해서 거길 따라가면 되겠다.
 *
 */
public class BOJ_G4_10159_저울 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();

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

		List<Integer>[] smaller = new List[N + 1];
		List<Integer>[] larger = new List[N + 1];

		for (int i = 0; i < N + 1; i++) {
			smaller[i] = new ArrayList<>();
			larger[i] = new ArrayList<>();
		}

		int a, b;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());

			// a > b
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());

			smaller[a].add(b);
			larger[b].add(a);
		}

		boolean[] visited;
		ArrayDeque<Integer> q = new ArrayDeque<>();

		for (int i = 1; i < N + 1; i++) {
			visited = new boolean[N + 1];
			q.push(i);
			visited[i] = true;

			// 자신보다 작은 무게들에 대하여 비교할 수 있는 개수 구하기
			while (!q.isEmpty()) {
				int curr = q.pop();

				for (Integer nxt : smaller[curr]) {
					if (visited[nxt]) continue;
					visited[nxt] = true;
					q.push(nxt);
				}
			}

			q.push(i);

			// 자신보다 큰 무게들에 대하여 비교할 수 있는 개수 구하기
			while (!q.isEmpty()) {
				int curr = q.pop();

				for (Integer nxt : larger[curr]) {
					if (visited[nxt]) continue;
					visited[nxt] = true;
					q.offer(nxt);
				}
			}

			int count = 0;
			for (int j = 1; j < N + 1; j++) {
				if (visited[j]) count++;
			}

			sb.append(N - count).append('\n');
		}

		System.out.println(sb);

	}


}

 

다른 사람의 풀이 (플로이드 워셜)

플로이드 워셜을 이용해서 문제를 풀어주었다. 물론 전체적인 틀은 같고 배열로 경로를 저장하냐 리스트로 저장하냐에 따라서 3중 포문으로 이용한 방법이다. 현재 5<=N<=100 이므로, 시간복잡도는  O(10^6)이므로 괜찮을 것 같다.
추가 풀이를 참고한 블로그에서 더 무거운 물건과 가벼운 물건을 파악할 때, OR 연산자를 활용한 방식은 색다르게 보았다.

 

 

아래는 핵심 Code 부분이다. 더 자세하게 보고싶다면 아래 링크를 참조하자.

// 플로이드 와샬 알고리즘
for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][k] && arr[k][j]) {
                arr[i][j] = true;
            }

            if (reverse_arr[i][k] && reverse_arr[k][j]) {
                reverse_arr[i][j] = true;
            }
        }
    }
}

// 특정 물건에 대하여 더 무거운 물건과 더 가벼운 물건 모두를 파악 가능.
// 만약 |을 취한 값이 false라면, 그 물건과 무게 비교를 할 수 없다는 의미.
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        arr[i][j] |= reverse_arr[i][j];
    }
}

 

https://steady-coding.tistory.com/100

[BOJ] 백준 10159번 : 저울 (JAVA)