[백준, JAVA]15591번, MooTube(Sliver)

문제 링크

15591번: MooTube (Silver)

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 그래프에 대한 정보를 입력받습니다.

2. k와 v에 대한 동영상 추천 개수를 Q번의 질문에 대하여 결과로 출력합니다.

3. 선분의 가중치가 k이상인 값만 이동이 가능합니다.

 

그래프에서 k와 v에 따른 BFS탐색하여 선분을 지나는 횟수를 각각 출력하도록 구현하였습니다.

 

 

예제입력 1.

 

Q1 : k=1, v=2해석 : 동영상 2번부터 탐색을 시작하고 가중치가 1이상인 선분만 탐색이 가능하다.

 

결과

 

선분을 지난 횟수 : 3

결과 : 3 출력

 

Q2 : k=4, v=1

해석 : 동영상 1번부터 탐색을 시작하고 가중치가 4이상인 선분만 탐색이 가능하다.

 

결과

선분을 지난 횟수 : 0

결과 : 0 출력

 

Q3 : k=3, v=1

해석 : 동영상 1번부터 탐색을 시작하고 가중치가 3이상인 선분만 탐색이 가능하다.

 

결과

선분을 지난 횟수 : 2

결과 : 2 출력

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 그래프 및 N, Q, k, v을 저장하였습니다.
• k, v에 따른 BFS탐색으로 지나는 선분의 개수를 구하는 bfs함수를 실행하였습니다.
• 질문 Q개에 대한 선분의 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 k와 v에 따른 BFS 탐색을 진행합니다.
• bfs함수는 BFS탐색으로 지나간 선분의 개수를 반환합니다.

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

public class Main {
    static int N,Q;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();	//그래프 정보 저장
    static int[][] nodeValue;		//선분 가중치 저장 배열
    static public void  main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        nodeValue = new int[N+1][N+1];
        //리스트 초기화
        for(int i=0;i<=N;i++){
            graph.add(new ArrayList<>());
        }
        //그래프 및 선분 가중치 저장
        for(int i=0;i<N-1;i++){
            st = new StringTokenizer(br.readLine()," ");
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            if(nodeValue[p][q] < r){
                graph.get(p).add(q);
                graph.get(q).add(p);
                nodeValue[p][q] = r;
                nodeValue[q][p] = r;
            }

        }
        //Q개의 k, v을 받아 탐색하여 BufferedWriter 저장
        for(int i=0;i<Q;i++){
            st = new StringTokenizer(br.readLine()," ");
            int k = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            bw.write(bfs(k,v) + "\n");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();

    }
    //k와 v에 따른 BFS 탐색
    static int bfs(int k, int v){
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N+1];
        visited[v] = true;
        queue.add(v);
        while(!queue.isEmpty()){
            int cur = queue.poll();
            for(Integer next : graph.get(cur)){
            	//인접한 동영상의 선분 가중치가 K보다 작을 때
                if(nodeValue[cur][next] >= k && !visited[next]){
                    queue.add(next);
                    visited[next] = true;
                    count++;
                }
            }
        }
        return count;
    }
}