[Java] 백준 10159 : 저울

[문제]

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

10159번: 저울

 

[풀이 과정]

무게가 서로 다른 N개의 물건이 있을 때 물건 i (1<= i <=N) 와 무게 비교를 알 수 없는 물건의 개수를 출력하면 되는 문제이다.

 

무게 비교를 알 수 없는 물건의 개수 =  총 물건의 개수 - 1 (자기 자신은 제외)

                                                         - (물건  i 보다 무게가 작은 물건들의 개수+ 물건 i보다 무게가 큰 물건들의 개수 ) 

 

 

깊이 우선 탐색 과 플로이드- 와샬 알고리즘을 가지고 두 가지 방식으로 풀어보았다.

 

---

[깊이 우선 탐색]

 

먼저 인접리스트를 통해  물건들의 무게에 대한 단방향 관계를 나타내었다.

  for (int i = 0 ; i < M ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list[start].add(end);
        }

 

 

현재 노드 기준으로 다음으로 갈 수 있는 노드가 있다면 그 노드를 차례로 방문한다.

이때 방문하지 않은 노드들에 대해서만 방문해야만 한다.

 

시작점을 기준으로 노드를 계속 방문하기때문에 방문할때마다  count[시작점]의 값을 1 증가시킨다.

시작점 보다 무게가 작은 노드들을 방문하기 때문이다. 그리고 count[다음 노드]의 값도 1 증가 시킨다. 그 이유는 다음 노드로 넘어갈 수 있다는 것은 상위에 자신보다 무게가 큰 물건이 존재하기 때문이다.

for(int i = 1 ; i<=N;i++){
          visited = new boolean[N+1];
            dfs(i,i); //(시작 , 현재)
        }

//count[] = 물건 i에 대하여  i보다 무게가 큰 물건의 개수 + i보다 무게가 작은 물건의 개수
//start = 시작점 curr= 현재 노드
public static void dfs(int start ,int curr){

        visited[curr] = true;

        for(int next : list[curr]){
            if(!visited[next]){
                count[next]++; // next보다 무게가 큰 curr물건이 존재하므로 +1
                count[start]++; //start보다 무게가 작은 물건이 존재하므로 +1
                dfs(start,next);
            }
        }
    }

 

반복문을 통해 모든 물건  i 에 대하여 (i보다 무게가 큰 물건의 개수 + i보다 무게가 작은 물건의 개수)를 구해주고 정답을 출력 해주면 된다.

//sb - StringBuilder
for(int i = 1 ; i<=N; i++){
            sb.append(N - 1 - count[i]).append("\n");
        }

        System.out.println(sb);

---

[플로이드-와샬] 

 

인접행렬을 통해 단방향 관계를 나타내준다.

  for (int i = 0 ; i < M ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
             map[start][end]=true;
        }

 

플로이드 - 와샬 알고리즘을 통해 모든 정점에서 모든정점까지 이동할 수 있는지 여부를 체크한다.

for(int k = 1; k <= N ; k++){ //거처가는 노드
           for(int r =1 ; r <=N;r++){ //시작 노드
               for(int c=1; c<=N;c++){//도착 노드
                   if(map[r][k] && map[k][c]) map[r][c]=true;
               }
           }
       }

 

물건 r를 기준으로 다른 물건들의 무게가(c)  r보다 큰지 혹은 작은지 판별하여 (총물건의 개수 - 1)에서 1만큼 감소 시킨다.

for(int r =1 ; r <= N;r++){ //시작노드

    int count = N-1; //총 물건의 개수 -  1 (자기 자신 제외)
    
    for(int c=1; c <= N;c++){//도착노드
    
    //map[r][c] 시작노드보다 무게가 작은 물건이 존재한다면 -1
    //map[c][r] 시작노드보다 무게가 큰 물건이 존재한다면 -1
        if(map[r][c] || map[c][r]) count --;
    }
  //  System.out.println(count);
}

 

[코드]

 

[깊이 우선 탐색]

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

public class Main {
   static List<Integer>[] list ;
   static boolean  [] visited;
   static int []count ;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        list = new ArrayList[N+1];
        count = new int[N+1];

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


        for (int i = 0 ; i < M ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list[start].add(end);
        }


        for(int i = 1 ; i<=N;i++){
          visited = new boolean[N+1];
            dfs(i,i);
        }

        for(int i = 1 ; i<=N; i++){
            sb.append(N - 1 - count[i]).append("\n");
        }

        System.out.println(sb);
    }
    public static void dfs(int start ,int curr){

        visited[curr] = true;

        for(int next : list[curr]){
            if(!visited[next]){
                count[next]++; // next보다 무게가 큰 curr물건이 존재하므로 +1
                count[start]++; //start보다 무게가 작은 물건이 존재하므로 +1
                dfs(start,next);
            }
        }
    }
}

 

[플로이드 와샬]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

   static boolean[][] map;
   static int []count ;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        count = new int[N+1];
        map = new boolean[N+1][N+1];

        for (int i = 0 ; i < M ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
             map[start][end]=true;
        }


       for(int k = 1; k <= N ; k++){ //거처가는 노드
           for(int r =1 ; r <=N;r++){ //시작
               for(int c=1; c<=N;c++){//도착
                   if(map[r][k] && map[k][c]) map[r][c]=true;
               }
           }
       }


        for(int r =1 ; r <=N;r++){ //시작
            int count = N-1; //자기 자신 제외
            for(int c=1; c<=N;c++){//도착
                if(map[r][c] || map[c][r]) count --;
            }

            sb.append(count).append("\n");
        }

        System.out.println(sb);
    }

}

 

[결과]

깊이우선탐색

플로이드와샬