[다익스트라] 백준 6118번 숨바꼭질 자바(java) 풀이

BOJ 6118번 숨바꼭질 자바(java) 풀이

• 랭크 : 실버1
• 백준 6118번 숨바꼭질
  
  
  

문제 정리

1. 재서기는 헛간에 숨으려 한다. 헛간의 개수(N)는 최대 20,000개 이다.
2. 수혀니는 1번 헛간 부터 찾는다. 모든 헛간은 최대 50,000개의 양방향 길(M)로 이루어져 있다.
3. 재서기의 발냄새는 1번 헛간에서의 거리(지나야 하는 길의 최소 개수)가 멀어질 수록 감소한다.
4. 재서기가 발냄새를 최대한 숨길 수 있는 헛간을 찾아라.
5. 숨어야 하는 헛간 번호(여러개 있다면 가장 작은 번호), 헛간까지의 거리, 그 헛간과 같은 거리를 갖는 헛간의 개수 출력
   
   
   

문제 풀이

그래프 문제로 해석합니다. 그러면 모든 헛간은 이어져 있고 수혀니는 1번 헛간 부터 출발합니다.
재서기가 발냄새를 최대한 숨길 수 있는 헛간이란, 1번 헛간으로 부터 거리가 제일 먼 곳입니다.
1번 점으로 부터 모든 곳까지의 거리를 구해야 하기 때문에 다익스트라 알고리즘을 이용합니다. 거리중에서 최소 거리를 구하기 때문에 이 문제에 딱 맞습니다.

1. 다익스트라 알고리즘을 이용하여 1번 점으로 부터 모든 정점까지의 거리를 구합니다.
2. 거리 중에 최대 거리, 최대 거리 위치, 최대값이 몇번 나오는지 for문을 돌면서 체크합니다.

• 인접행렬 구현시 메모리 초과가 발생하였습니다. 그러므로 인접 리스트로 구현하도록 합니다.
  
  
  

다익스트라 알고리즘

1. 출발점을 정합니다.
2. 이 알고리즘을 위해서는 출발점으로 부터의 거리를 저장할 dist배열과 방문 여불르 저장할 visited 배열이 필요하므로 선언합니다.
visited 배열은 모두 false로, dist 배열은 모두 큰값으로 초기화 합니다.
3. 출발점의 dist와 visited를 0과 true로 초기화 합니다.
4. 출발점과 연결된 점들의 거리를 갱신해줍니다.
5. 출발점을 뺀 모든 점들에 대하여 다음을 반복합니다. (N-1번 반복)
&nbsp&nbsp 5.1 방문하지 않은 점들 중에 dist가 최소인 점을 찾습니다.
&nbsp&nbsp 5.2 찾은 최소인 점을 방문처리 합니다.
&nbsp&nbsp 5.3 최소인 점과 연결되었으면서 방문하지 않은 점들에 대해 다음을 확인합니다.
&nbsp&nbsp&nbsp&nbsp 최소인 점까지의 거리에 1을 더한 값이(최소인 점을 거쳐서 연결된 다른 점으로 감)
&nbsp&nbsp&nbsp&nbsp 그 점으로 바로 가거나 다른 점을 거쳐서 가는 것보다 작다면 거리를 갱신해줍니다.

 

6118번 숨바꼭질 자바(java) 코드

1. 일반 다익스트라

- 메모리: 32196 kb
- 실행시간: 1804 ms

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	import java.util.ArrayList;
	import java.util.Arrays;
	class Main {
	static int N, M;
	static ArrayList<ArrayList<Integer>> adj;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = null;
	st = new StringTokenizer(br.readLine(), " ");
	N = Integer.parseInt(st.nextToken());
	M = Integer.parseInt(st.nextToken());
	// 그래프 연결정보 입력받기
	adj = new ArrayList<>();
	for(int i=0; i<=N; i++)
	adj.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());
	adj.get(a).add(b);
	adj.get(b).add(a);
	}
	dijkstra(1);
	}
	private static void dijkstra(int v){
	boolean[] visited = new boolean[N+1];
	int[] dist = new int[N+1];
	// distance 초기화
	Arrays.fill(dist, Integer.MAX_VALUE);
	// 시작점 방문표시 및 거리 0 초기화
	visited[v] = true;
	dist[v] = 0;
	// 시작점과 연결된 노드의 거리 갱신
	for(int i=0; i<adj.get(v).size(); i++){
	int x = adj.get(v).get(i);
	if(!visited[x])
	dist[x] = 1;
	}
	// 모든 점에 대해서
	for(int a=0; a<N-1; a++){
	int min = Integer.MAX_VALUE;
	int minPos = -1;
	// 방문하지 않은 노드 중 dist 최소 값 찾기
	for(int i=1; i<=N; i++){
	if(!visited[i] && dist[i] != Integer.MAX_VALUE){
	if(dist[i] < min){
	min = dist[i];
	minPos = i;
	}
	}
	}
	// 최소 거리 가지는 점 방문처리
	visited[minPos] = true;
	// minPos와 연결되었으면서 방문하지 않은 점 check
	for(int i=0; i<adj.get(minPos).size(); i++){
	int x = adj.get(minPos).get(i);
	if(!visited[x]){
	if(dist[x] > dist[minPos] + 1)
	dist[x] = dist[minPos] + 1;
	}
	}
	}
	int max = -1;
	int maxPos = -1;
	int maxNum = 1;
	// 최댓값 찾기
	for(int i=1; i<=N; i++){
	if(max < dist[i]){
	max = dist[i];
	maxPos = i;
	maxNum = 1;
	}
	else if(max == dist[i])
	maxNum++;
	}
	System.out.println(maxPos + " " + max + " " + maxNum);
	}
	}

view raw BOJ6118.java hosted with ❤ by GitHub

 

2. bfs를 이용한 다익스트라

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.LinkedList;
	import java.util.Queue;
	class Main {
	static int N, M;
	static ArrayList<Integer>[] adj;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = null;
	st = new StringTokenizer(br.readLine(), " ");
	N = Integer.parseInt(st.nextToken());
	M = Integer.parseInt(st.nextToken());
	// 그래프 연결정보 입력받기
	adj = new ArrayList[N+1];
	for(int i=0; i<=N; i++)
	adj[i] = 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());
	adj[a].add(b);
	adj[b].add(a);
	}
	dijkstra(1);
	}
	private static void dijkstra(int v){
	int[] dist = new int[N+1];
	boolean[] visited = new boolean[N+1];
	Arrays.fill(dist, Integer.MAX_VALUE);
	Queue<Integer> q = new LinkedList<>();
	dist[v] = 0;
	visited[v] = true;
	q.offer(v);
	while(!q.isEmpty()){
	int idx = q.poll();
	for(int i=0; i<adj[idx].size(); i++){
	int next = adj[idx].get(i);
	if(!visited[next] && dist[next] > dist[idx] + 1){
	dist[next] = dist[idx] + 1;
	q.offer(next);
	visited[next] = true;
	}
	}
	}
	int max = -1;
	int maxPos = -1;
	int maxNum = 1;
	// 최댓값 찾기
	for(int i=1; i<=N; i++){
	if(max < dist[i]){
	max = dist[i];
	maxPos = i;
	maxNum = 1;
	}
	else if(max == dist[i])
	maxNum++;
	}
	System.out.println(maxPos + " " + max + " " + maxNum);
	}
	}

view raw BOJ6118_2.java hosted with ❤ by GitHub