[백준] 알고리즘 분류(그래프 이론,JAVA)18126번, 너구리 구구

문제 링크

18126번: 너구리 구구

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 너구리 구구는 1번부터 N번까지의 방을 가지고 있습니다.

2. 모든 방은 N-1개의 양방향 길로 연결되었으며 거리가 존재합니다.

3. 너구리 구구가 입구에서 가장 멀리 아이스크림을 두는 거리를 결과로 출력합니다.

4. 입구는 항상 1번으로 설정됩니다.

 

알고리즘 진행 순서.

 

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

 

2. BFS탐색을 통해 가장 멀리 있는 방을 탐색합니다.

 

3. 탐색이 종료되었을 때 가장 멀리 있는 방의 거리를 결과로 출력합니다.

 

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

BFS

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

 

예제입력 1.

 

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

 

N : 4

 

 

 

 

 

 

2. BFS탐색을 통해 가장 멀리 있는 방을 탐색합니다.

 

BFS 탐색 진행!

 

탐색 경로 : 1 ▶ 2  : 3

 

 

탐색 경로 : 1 ▶ 2 ▶ 3 : 5

탐색 경로 : 1 ▶ 2 ▶ 4 : 7

 

3. 탐색이 종료되었을 때 가장 멀리 있는 방의 거리를 결과로 출력합니다.

 

최장 거리의 경로 :  1 ▶ 2 ▶ 4 : 7

7 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 길에 대한 정보들을 띄어쓰기 기준 나누었습니다.
• bfs함수를 이용하여 입구부터 다른 방들을 탐색합니다.
• 탐색이 종료되었을 때 가장 멀리 있는 방의 거리를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수를 이용하여 입구(1)부터 모든 방을 탐색해서 가장 먼 방의 거리를 구합니다.

 

결과코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	//간선에 대한 정보 관련 클래스
    static class Node{
		int idx;
		long value;
		public Node(int idx, long value) {
			this.idx = idx;
			this.value = value;
		}
	}
	//결과값 초기화
    static long answer = Integer.MIN_VALUE;
    //길에 대한 정보 리스트
    static ArrayList<ArrayList<Node>> 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));
        int N = Integer.parseInt(br.readLine());

        for(int i=0;i<=N;i++)
        	graph.add(new ArrayList<>());
        
        StringTokenizer st;
        
        //입력되는 양방향 길에 정보 저장
        for(int i=1;i<N;i++) {
        	st = new StringTokenizer(br.readLine()," ");
        	int A = Integer.parseInt(st.nextToken());
        	int B = Integer.parseInt(st.nextToken());
        	int C = Integer.parseInt(st.nextToken());
        	graph.get(A).add(new Node(B,C));
        	graph.get(B).add(new Node(A,C));
        }
        
        bfs(N);	//BFS탐색 진행
        bw.write(String.valueOf(answer));	//최장 거리 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색을 통해서 입구(1) 기준 모든 방 탐색
    static void bfs(int N) {
    	Queue<Node> queue = new ArrayDeque<>();
    	boolean[] visited = new boolean[N+1];
    	visited[1] = true;
    	queue.offer(new Node(1, 0));
    	//BFS탐색 진행!
        while(!queue.isEmpty()) {
    		boolean flag = false;
    		Node cur = queue.poll();
    		//주변 길 탐색!
            for(Node nxt : graph.get(cur.idx)) {
    			if(!visited[nxt.idx]) {
    				flag = true;
    				visited[nxt.idx] = true;
    				queue.add(new Node(nxt.idx, cur.value + nxt.value));
    			}
    		}
    		if(!flag)	//Leaf노드일 때	최대거리 비교
    			answer = Math.max(answer,  cur.value);
    	}
    }
}