[백준, Java] 10159번, 저울 알고리즘 분류(그래프 탐색, DFS)

문제 링크

10159번: 저울

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 물건들의 무게가 더 무거운지 입력값으로 들어옵니다.

2. 각 물건을 다른 물건과 비교할 때 어느 것이 더 무거운지 확인할 수 없는 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 입력된 무게 기준 그래프를 만들어서 DFS탐색으로 연결된 물건의 개수를 구합니다.

 

3. 각 물건들에 연결되지 않은 물건의 개수를 결과로 출력합니다.

 

그래프 만들기.

 

[1] > [2]일 때

 

[1]물건은 [2]물건에 비해 무거움과 동시에 [2]보다 가벼운 물견을 모두 탐색할 수 있습니다.

 

[1] → [2] 단방향 간선으로 표현이 가능하다!

 

위와 같이 물건에 대한 입력이 주어졌을 때 간선으로 그래프를 만들 수 있습니다.

 

※ 그래프를 만드는 과정은 예제입력 과정을 보여드리며 확인하실 수 있습니다.

 

 

DFS 탐색하기.

 

하위 물건들을 방문할 때

 

 

시작되는 물건 : +1

 

→ 해당 물건들보다 무거움으로 비교가 가능하다!!

 

 

각 하위 물건 : + 1

 

→ 해당 물건보다 무거운 물건이 1개가 존재하므로 비교가 가능하다!!

 

 

예제입력 3.

1. 입력된 정보를 저장합니다.

 

N : 6
M : 5
1 2
2 3
3 4
5 4
6 5

 

2. DFS탐색으로 물건 비교 가능한 개수를 구합니다.

 

물건 1 기준으로 탐색!

1	2	3	4	5	6
4	1	1	1	0	0

 

물건 2 기준으로 탐색!

1	2	3	4	5	6
4	4	2	2	0	0

 

물건 3 기준으로 탐색!

1	2	3	4	5	6
4	4	4	3	0	0

 

물건 4 기준으로 탐색!

1	2	3	4	5	6
4	4	4	4	0	0

 

물건 5 기준으로 탐색! 

1	2	3	4	5	6
4	4	4	5	2	0

 

물건 6 기준으로 탐색! 

1	2	3	4	5	6
4	4	4	6	3	3

 

3. 각 물건마다 비교 불가능한 물건의 개수를 결과로 출력합니다.

 

1	2	3	4	5	6
4	4	4	6	3	3

위 표는 비교 가능한 물건의 개수를 나타내고 있습니다.

 

불가능한 물건의 개수 : (모든 물건의 개수) - (비교 가능한 물건의 개수)

 

1	2	3	4	5	6
(6 - 4) = 2	(6 - 4) = 2	(6 - 4) = 2	(6 - 6) = 0	(6 - 3) = 3	(6 - 3) = 3

 

2 2 2 0 3 3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 무게에 비교 값을 저장합니다.
• dfs 함수를 이용하여 각 물건을 기준으로 DFS탐색을 진행합니다.
• 탐색이 종료되었을 때 각 물건이 비교 불가능한 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• dfs함수는 DFS탐색으로 자신보다 가벼운 물건들을 탐색하며 방문 확인을 진행합니다.

 

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int[] count;	//비교 가능한 물건 저장 배열
    static boolean[] visited;	//물건 방문 배열
    static List<List<Integer>> graph = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        count = new int[N+1];
        //입력값 그래프 형태로 변환
        for(int i=0;i<=N;i++)
            graph.add(new ArrayList<>());
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
        }
        //각 물건 기준으로 DFS 탐색 진행
        for(int i=1;i<=N;i++) {
            visited = new boolean[N+1];
            visited[i] = true;	//기준이 되는 물건 방문 확인
            dfs(i, i, 0);
        }
        //비교 불가능한 물건 개수 구해서 저장
        //점화식 : (전체 물건의 개수) - (비교 가능한 물건의 개수)
        for(int i=1;i<=N;i++)
            sb.append(N - count[i]).append("\n");
        bw.write(sb.toString());	//결과 BufferedWriter 저장
        bw.flush();			//결과 출력
        bw.close();
        br.close();
    }
    //DFS탐색 진행하는 함수
    private static void dfs(int idx,int root, int val) {
        count[idx]++;	//현재 기준이 되는 물건 +1
        //DFS탐색으로 하위 물건들 방문
        for(int nxt : graph.get(idx)) {
            if(visited[nxt])
                continue;
            visited[nxt] = true;
            count[root]++;	//방문한 물건 + 1
            dfs(nxt, root, val);
        }
    }
}