[Baekjoon] 18126_너구리 구구

Silver II

문제(출처: https://www.acmicpc.net/problem/18126)

---

<  너구리 구구>

 

문제 풀이

 

입구에서 먼 방을 찾기 위해 bfs를 활용하여 문제를 해결하였다.

 

 

 - my solution (Java)

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

public class _18126_ {
	static int arr[][], N;
	static long visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N=Integer.parseInt(bf.readLine());
		arr=new int[N][N];
		visited=new long[N];
		
		for(int i=0; i<N-1; i++) {
			st=new StringTokenizer(bf.readLine());
			int x=Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			int value=Integer.parseInt(st.nextToken());
			arr[x-1][y-1]=value;
			arr[y-1][x-1]=value;
		}
		search(0);
		
		long result=0;
		for(int i=0; i<N; i++) {
			if(result<visited[i]) result=visited[i];
		}
		System.out.println(result);
	}

	private static void search(int i) {
		Queue<Integer>queue=new LinkedList<>();
		queue.add(i);
		
		while(!queue.isEmpty()) {
			int num=queue.poll();
			for(int k=0; k<N; k++) {
				if(arr[num][k]>0) {
					if(visited[k]==0 || visited[num]+arr[num][k]>visited[k]) {
						visited[k]=visited[num]+arr[num][k];
						queue.add(k);
						arr[num][k]=0;
						arr[k][num]=0;
					}
				}
			}
		}
	}
}

 

Main

- N개의 방 입력

- 집의 모든 길의 정보 입력 -> 양방향으로 입력

- search 함수 호출

- visited 배열을 탐색하며 가장 큰 값을 찾아 출력

 

search

- 0번 방부터 시작하여 queue가 빌 때까지 반복

- 현재 방에서 갈 수 있는 방을 탐색 ( arr 값이 0보다 크면 갈 수 있음) 하여 visited배열이 0 값이거나 (아직 방문 x) , 이동 후 거리가 더 길다면 값을 업데이트해 준다. 업데이트하면서 방문 여부를 체크해 주기 위해 arr 값을 0으로 바꿔준다.

---

생각🤔

 

bfs를 활용하여 문제는 빨리 풀었지만 답이 long일 줄은 몰랐다... 언제쯤 한 번에 자료형을 판단할 수 있을까 

 

---