[백준] 단계별로 풀어보기(단계:25, 최단 경로,JAVA)13549번, 숨바꼭질 3

문제 링크

13549번: 숨바꼭질 3

---

주의사항

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

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

---

문제 설명

---

접근 방법

최단경로는 시작 정점에서 목표 정점까지 최소의 비용으로 갈 수 있는 경로를 구하는 것입니다.

최단 경로를 구하는 알고리즘은 대표적으로 3개가 존재합니다.

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

3. 플로이드 워셜 알고리즘

 

3가지 알고리즘은 문제를 해결할 때 사용하는 알고리즘만 설명하도록 하겠습니다.

최단 경로에서 가중치(비용)이 양수이고 단일 - 출발, 단일 - 도착이면 다익스트라 알고리즘으로 구현합니다.

다익스트라 알고리즘이란?

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

1. 출발 정점에서 인접한 정점으로 이동합니다.

2. 인접한 정점에서 가장 적은 가중치(거리)의 정점을 먼저 탐색합니다.

3. 이동을 할 때마다 이동한 거리가 현재 저장된 거리보다 작으면 변경합니다.

4. 위 과정을 반복이 끝나면 출발 정점에서 각 정점에 도착하는 최소 거리을 구할 수 있습니다.

 

글로는 잘 설명하지 못한 것 같아서 아래에 예제 문제를 풀면서 어떻게 진행되는지 자세히 보여드리겠습니다.

 

더 자세한 내용은 아래 링크를 통해 확인해주시기 바랍니다.

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

 

1. 수빈이의 위치에서 +1, -1, *2로 이동할 수 있습니다.

2. +1, -1을 이동할 때에는 1초에 시간이 걸리지만 *2을 이동할 때에는 시간이 소모되지 않습니다.

3. 수빈이가 동생에 위치에 도착하는 최소 시간을 결과로 출력합니다.

 

BFS를 사용하여 문제를 해결해도 되지만 사용되는 메모리양이 생각보다 많다고 느껴서PriorityQueue 및 BFS를 사용하여 구현했을 때 메모리 절약이 많이 되어서 다익스트라 알고리즘 형태로 구현하였습니다.

 

PriorityQueue를 사용한 이유는 *2로 순간이동은 시간이 소모되지 않아서 순간이동으로 이동하는 것이 최소 시간을 구할 때 우선적으로 하기 위함입니다.

 

문제를 접근할 때 처음 동생에 있는 지점에 가장 먼저 도착했을 때 시간을 출력하였는데 *2의 형태에서 시간이 소모되지 않기 때문에 항상 먼저 도착하는 시간이 최소 시간이 아닐 수 있습니다.

 

예를 들어

 

입력값이 4 6일 때에는

4 -> 5 -> 6 

4 -> 3 -> 6

두 경우가 있을 때 BFS연산시 4 -> 5 -> 6이 먼저 도착하게 되면 결과가 2가 출력됩니다.

하지만 4 -> 3 -> 6이 소모되는 시간은 1이기 때문에 결과적으로 답은 1이 되어야 합니다.

 

저는 BFS를 모두 탐색하여 동생에 위치에 도착했을 때 소모되는 시간을 비교하여 최소값을 출력하는 형식으로 하였습니다.

 

입력값 4 6일 때

 

4 -> 8 -> 7 -> 6 = 2초

4 -> 5 -> 6 = 2초

4 -> 3 -> 6 = 1초

.....

BFS를 모두 탐색하여 최소 시간인 1초가 결과로 출력되는 형식입니다.

 

수빈이의 위치가 동생의 위치보다 클 경우에는

 

수빈이는 -1을 반복하는 경우의 수밖에 존재하기 때문에

 

수빈이의 위치 > 동생의 위치

최소 시간 = 수빈이의 위치 - 동생의 위치

 

예를 들어

 

입력값이 8 3일때에는

8 -> 7 -> 6 -> 5 -> 4 -> 3

최소 시간 = 수빈이의 위치(8) - 동생의 위치(3) = 5

 

결과로 5가 출력됩니다.

 

 

문제를 해결한 알고리즘의 과정

 

1. 수빈이의 위치와 동생의 위치를 입력받습니다.

2. 수빈이의 위치가 동생의 위치보다 클 경우 수빈이의 위치 - 동생의 위치를 결과로 출력합니다.

3. 수빈이의 위치가 동생의 위치보다 작을 경우 BFS 탐색을 통해 최소 시간을 구합니다.

4. BFS탐색시 동생의 위치에 도착했을 때 최소 시간을 비교하여 최소 시간을 반환합니다.

5. 반환된 최소 시간을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 수빈이의 위치와 동생의 위치를 분리하였습니다.
• BFS으로 최소 시간(다익스트라 알고리즘)을 구하는 cal함수를 만들었습니다.
• BufferedWriter에 수빈이의 위치가 동생의 위치보다 클 경우 수빈이의 위치 - 동생의 위치 값이 저장하였습니다.
• BufferedWriter에 cal함수를 통해 받은 최소 시간를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal은 목적지에 도착했을 때 최소 시간을 비교하여 최소 시간을 구하였습니다.
• cal은 다익스트라 알고리즘과 BFS을 이용하여 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//큐에 사용할 현재 지점, 시간을 저장하는 생성자
	static class move{
		int point, time;

		public move(int point, int time) {
			this.point = point;
			this.time = time;
		}
		public int getPoint() {
			return point;
		}

		public int getTime() {
			return time;
		}
	}
	static int N,K;
	static boolean[] check;	//해당 위치 탐색하였는지 확인하는 배열
    public static 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());
    	K = Integer.parseInt(st.nextToken());
    	int size = Math.max(N, K);
    	if(size == N)	//수빈이의 위치가 동생의 위치보다 클 경우
    		bw.write(N-K + "\n");	//수빈이의 위치 - 동생의 위치 BufferedWriter 저장
    	else {		//수빈이의 위치가 동생의 위치보다 작을 경우
        	check = new boolean[size*2+1];
        	int result = bfs(N,K);		//BFS 탐색 및 최소 시간 반환하는 함수 실행
        	bw.write(result + "\n");	//최소 길이 BufferedWriter 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //BFS 형태의 다익스트라 알고리즘으로 최소 시간 구하는 함수
    static int bfs(int start, int end) {
         /*
        우선순위 큐를 사용해서 현재 정점들에서 거리가 가장 적은 정점을
        바로 poll()을 할 수 있도록 시간이 작은 순으로 Queue에 저장되도록
        Comparator를 설정해주었습니다.
        */
    	PriorityQueue<move> queue = new PriorityQueue<move>(new Comparator<move>() {	
			@Override
			public int compare(move o1, move o2) {
				return o1.time - o2.time;
			}
		});
    	queue.add(new move(start,0));	//수빈이의 위치 큐에 저장
    	check[start] = true;		//수빈이의 위치 탐색 완료
    	int result = Integer.MAX_VALUE;	//최소 시간 값 초기화
    	while(!queue.isEmpty()) {
    		move temp = queue.poll();
    		int point = temp.getPoint();
    		int time = temp.getTime();
    		if(point==end) {	//동생 위치 도착할 때 시간 비교하여 최소 시간 구하기
    			result = Math.min(time, result);
    			continue;
    		}
    		else
    			check[point] = true;
    		if(point*2 <= end*2 && !check[point*2]) {	//*2
    			queue.add(new move(point*2, time));
    		}  
        	if(point < end && !check[point+1]) {	// +1
        		queue.add(new move(point+1, time +1));
        	}
        	if(point > 0 && !check[point-1]) {		//-1
         		queue.add(new move(point-1, time + 1));
        	}   
   	
    	}
    	return result;		//최소 시간 반환
    }
}