백준 10159번 - 저울

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

10159번: 저울

 

 

 

 

 

문제

• 물건의 개수 N 과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력
• 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.)
• [1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5]
• 우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없다. 이와 같이, 물건 2는 물건 1, 3, 4와의 비교 결과는 알 수 있지만, 물건 5, 6과의 비교 결과는 알 수 없다. 물건 4는 모든 다른 물건과의 비교 결과를 알 수 있다. 

 

 

 

 

 

풀이

어떠한 두 개의 순서를 비교해 이를 바탕으로 모든 원소 간의 순서 관계를 알아내야 하는 문제로 이전에 프로그래머스에서 풀었던 '순위'와 비슷한 유형의 문제라고 생각했다. 그래서 풀이법을 바로 떠올릴 수 있었다.

https://school.programmers.co.kr/learn/courses/30/lessons/49191

 

 

 

• 그래프의 자료구조 : 연결 리스트

 A > B의 순서 관계가 주어지고, 이어서 B > C가 주어지면  A > B > C로 관계가 연결되므로 이를 표현하기에는 2차원 배열의 그래프보다는 연결 리스트가 적합하다. 그리고 입력이  5 ≤ N ≤ 100이고, 0 ≤ M ≤ 2,000이므로 공간복잡도 측면에서도 효율적이다. 2차원 배열의 그래프로 표현한다면 100 * 100 = 10,000으로 비교 결과(M)의 최대치인 2,000을 훨씬 넘는다.

 

 

 

• 그래프 탐색 : BFS

 물건과의 비교 결과를 알 수 없는 물건의 개수를 알기 위해서는 반대로 물건과의 비교 결과를 알 수 있는 물건의 개수를 알아내야 한다. 연결 리스트에 A > B로 비교할 수 있는 물건 간의 관계가 저장되어 있으므로, 해당 물건을 시작점으로 그래프 탐색을 한다면 자신보다 가벼운 물건들의 번호를 알 수 있다.

 

 BFS(너비우선탐색)을 통해 큐에 담겨 탐색하게 되는 원소들의 개수를 카운트해 종료될 때 개수를 반환하도록 했다.

 

 

 

• 양방향의 관계를 저장하기 위한 두 개의 그래프

 연결리스트를 하나로 두어 A > B의 관계만 저장을 하게 된다면, 자신보다 가벼운 원소들만 알 수 있을 뿐, 무거운 원소들은 알지 못하게 될 것이다. 그렇다고 하나의 그래프에 양방향으로 저장하게 된다면 A > B, A > C인 경우, B를 시작으로 탐색하게 된다면 관계를 알 수 없는 C도 탐색을 해 순서를 알 수 있게 되어버린다.

 

 그래서 자신보다 무거운 원소들만 탐색하도록 하고 싶다면, 반대의 관계인 B < A를 저장하는 연결리스트를 하나 더 만들면 된다. 그리고 이 연결리스트에 대해서도 해당 물건을 시작점으로 그래프 탐색을 하여 탐색하게 되는 원소들의 개수를 카운트하고, 다른 리스트의 결과에 더하면 된다.

 

 

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	static ArrayList<Integer>[] graph1; //인접리스트: 관계 저장(A > B)
    static ArrayList<Integer>[] graph2; //반대로 저장(B < A)
    static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		graph1 = new ArrayList[N + 1];
        for(int i = 1; i < N + 1; i++) {
            graph1[i] = new ArrayList<>();
        }
        
        graph2 = new ArrayList[N + 1];
        for(int i = 1; i < N + 1; i++) {
            graph2[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < M; i++) { //물건 비교 정보 저장
        	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	
        	graph1[a].add(b); //A > B
            graph2[b].add(a); //B < A
        }
        
        //구현
        int[] answer = new int[N + 1];
        
        for(int i = 1; i < N + 1; i++) {
        	visited = new boolean[N + 1];
        	int sum = bfs(graph1, i); //i보다 작은 물건 개수(i포함)
        	
        	visited = new boolean[N + 1];
        	sum += bfs(graph2, i); //i보다 큰 물건 개수(i포함)
        	
        	answer[i] = N - sum - 1; //비교 결과를 알 수 없는 물건의 개수
        }
        
        //출력
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < N + 1; i++) {
        	sb.append(answer[i] + "\n");
        }
        System.out.println(sb);
	}
	
	public static int bfs(ArrayList<Integer>[] graph, int v) {
        Queue<Integer> queue = new LinkedList<>();
         
        queue.add(v);
        visited[v] = true;
         
        int count = 0; //비교 가능 물건 개수
        while(!queue.isEmpty()) {
            int p = queue.poll();
             
            for(int i : graph[p]) {
                if(!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
         
        return count;
    }

}

 

 

 

 

 

결과

 

 

 

 

배운점