[백준] code.plus(BFS,JAVA)13913번, 숨바꼭질 4

문제 링크

13913번: 숨바꼭질 4

---

주의사항

• 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. 수빈이는 +1, -1, *2로 이동할 수 있습니다.

2. 이동할 때마다 1초의 시간이 걸립니다.

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

 

알고리즘을 구현하기 위해 저는 BFS(너비 우선 탐색)을 통해 구현하였습니다.

 

BFS 탐색을 통해 가장 먼저 동생의 위치에 도착했을 때가 최소 시간입니다.

 

예제입력1으로 BFS가 진행되는 과정을 보여드리겠습니다.

N = 5, K = 17

 

5 + 1 -> 6

5 - 1 -> 4

5 * 2 -> 10

 

6 + 1 -> 7

6 - 1 -> 5(탐색 완료)

6 * 2 -> 12

 

4 + 1 -> 5(탐색완료)

4 - 1 -> 3

4 * 2 -> 8

 

10 + 1 -> 11

10 - 1 -> 9

10 * 2 -> 20

 

7 + 1 -> 8(탐색완료)

7 - 1 -> 6(탐색완료)

7 * 2 -> 14

 

12 + 1 -> 13

12 - 1 -> 11

12 * 2 -> 24

 

3 + 1 -> 4(탐색완료)

3 - 1 -> 2

3 * 2 -> 6(탐색완료)

 

8 + 1 -> 9(탐색완료)

8 - 1 -> 7(탐색완료)

8 * 2 -> 16

 

11 + 1 -> 12(탐색 완료)

11 - 1 -> 10(탐색완료)

11 * 2 -> 22

 

9 + 1 -> 10(탐색완료)

9 - 1 -> 8(탐색 완료)

9 * 2 -> 18

 

20은 K보다 크기 때문에 탐색 X

 

14 + 1 -> 15

14 - 1 -> 13(탐색 완료)

14 * 2 -> 28

 

13 + 1 -> 14(탐색 완료)

13 - 1 -> 12(탐색 완료)

13 * 2 -> 26

 

11 + 1 -> 12(탐색 완료)

11 - 1 -> 10(탐색 완료)

11 * 2 -> 22(탐색 완료)

 

24는 K보다 크기 때문에 탐색 X

 

2 + 1 -> 3(탐색 완료)

2 - 1 -> 1

2 * 2 -> 4(탐색 완료)

 

16 + 1 -> 17

 

목적지 도착

순서 : 5 > 4 > 8 > 16 > 17

소요 시간 : 4

 

결과로 순서(5 4 8 16 17)과 소요 시간(4)를 출력합니다.

 

K <= N일 때 이동하는 방향은 -1로만 이동하기 때문에 K-N번 이동합니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 N, K를 저장합니다.

2. BFS(너비 우선 탐색)을 이용하여 +1, -1, *2로 동생의 위치를 도착할 때까지 탐색합니다.

3. 동생의 위치를 도착했을 때 지금까지 들린 위치와 이동 횟수를 결과로 출력합니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 N, K을 나누었습니다.
• BFS탐색으로 동생에 위치까지 최단 시간을 구하는 bfs함수를 사용하였습니다.
• BufferedWriter에 BFS를 통해 얻은 최단 시간을 저장하였습니다.
• BufferedWriter에 저장된 값을 결과로 출력하였습니다.

• bfs 함수는 너비 우선 탐색을 이용하여 +1, -1, *2로 이동하며 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//BFS에 사용할 생성자
	static class move{
		int point,count;		//위치, 소요 시간
		String process;		//이동 과정
		
		public String getProcess() {
			return process;
		}

		public int getPoint() {
			return point;
		}

		public int getCount() {
			return count;
		}

		public move(int point, int count,String process) {
			this.point = point;
			this.count = count;
			this.process = process;
		}		
	}
	static int N,K;
	static boolean visited[];	//해당 위치 방문 확인 배열
	public static void main(String[] arg) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		br.close();
		if(K<=N) {		//K<=N일 때
			System.out.println(N-K);
			for(int i=N;i>=K;i--)
				System.out.print(i + " ");
		}else {		//K > N일 때
			visited = new boolean[K*2 +1];
			bfs();		//BFS 탐색 수행하는 함수 실행
		}
	}
    	//BFS탐색을 통해 동생 위치에 가장 빨리 도착하는 시간과 과정 출력하는 함수
	static void bfs() {
		Queue<move> queue = new LinkedList<move>();	//BFS에 사용할 큐
		visited[N] = true;		//수빈이의 위치 방문 완료
		queue.add(new move(N,0,String.valueOf(N)));	
		while(!queue.isEmpty()) {
			move temp = queue.poll();
			int point = temp.getPoint();
			int count = temp.count;
			String process = temp.getProcess();
			if(point == K) {		//동생의 위치 도착했을 때
				System.out.print(count + "\n" + process);	//결과 출력
				System.exit(0);		//시스템 종료
			}
			if(point>0 && !visited[point-1]) {		//+1로 이동할 때
				queue.add(new move(point-1, count+1, process + " " + String.valueOf(point-1)));
				visited[point-1] = true;
			}
			if(point<K && !visited[point+1]) {	//-1로 이동할 때
				queue.add(new move(point+1, count+1, process + " " + String.valueOf(point+1)));
				visited[point+1] = true;
			}
			if(point<K && !visited[point*2]) {	//*2로 이동할 때
				queue.add(new move(point*2, count+1, process + " " + String.valueOf(point*2)));
				visited[point*2] = true;
			}
		}
	}
}