본문 바로가기
백준

[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)1697번, 숨바꼭질

by 열정적인 이찬형 2022. 3. 26.

주의사항

  • JAVA를 사용하여 프로그램을 사용하였습니다.
  • 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{ 	
	public static void main(String[] args){
    }
}

문제 설명


접근 방법

DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.

자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

DFS

 

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

깊이 우선 탐색의 애니메이션 예시 깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작

ko.wikipedia.org

BFS

 

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

 

ko.wikipedia.org

이 문제에 핵심은

1. 동생을 찾을 때 이동하는 경우는 +1, -1, *2가 존재합니다.

2. 동생을 찾는 최소 걸리는 초를 구해야 합니다.

 

저는 BFS(너비우선탐색)을 이용하여 문제를 해결하였습니다.

현재 위치를 기준으로 +1, -1, *2로 탐색을 진행하여 처음 목적지에 도착했을 때가 최소 걸리는 초입니다.

 

이 문제에서는 각 지점을 도착하는 최소 걸리는 초를 저장하기 위해 day[100001]를 만들어주었습니다.

check배열을 통해서 창고에 해당 지점을 탐색했는지를 확인하였습니다.

예제 입력1을 BFS로 탐색을 하는 과정을 보여드리겠습니다.

 

시작 지점 = 5, 도착 지점 = 17

 

1. 시작지점을 큐에 저장합니다.

 

Queue = {2}

 

2. 큐에 값을 꺼내서 이동할 수 있는 지점을 확인 및 큐에 저장

 

현재 지난 초 = 1초

 

꺼낸 값 = 5

 

5 + 1 = 6

 

5 - 1 = 4

 

5 * 2 = 10

 

Queue = { 6, 4 ,10}

 

day[6] = 1

 

day[4] = 1

 

day[10] = 1

 

3. 큐에 값을 꺼내서 이동할 수 있는 지점을 확인 및 큐에 저장

 

현재 지난 초 = 2초

 

꺼낸 값 = 6

 

6 + 1 = 7

 

6 - 1 = 5

 

6 * 2 = 12

 

day[7] = 2

 

day[5] = 0, 시작값이기 때문에 0

 

day[12] = 2

 

위와 같은 것을 반복하여 마지막으로 큐에 값을 꺼낼 때

 

현재 지난 초 = 4초

 

꺼낸 값 = 18(5 -> 10 -> 9 -> 18)

 

18 + 1 = 19

 

18 - 1 = 17

 

18 * 2 = 36

 

day[19] = 4

 

day[17] = 4

 

day[36] = 4

 

목적지 도착하였으므로 BFS 탐색을 종료하고 day[17]의 값 4를 출력하였습니다.

 

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

1. 출발 지점과 도착 지점을 저장합니다.

2. BFS(너비 우선 탐색)을 이용하여 +1, -1, *2 순으로 탐색을 진행합니다.

3. BFS종료후 최소 걸리는 초를 결과로 출력하였습니다.

 

  • BufferedReader를 사용하여 입력 값을 받았습니다.
  • StringTokenizer를 통해 시작지점과 도착지점을 저장하였습니다.
  • BFS로 목적 지점 도착하는 최소 걸리는 초를 구하는 bfs 함수를 만들었습니다.
  • BufferedWriter에 출발지점과 도착지점이 같으면 0 아니면 최소 걸리는 초를 저장하였습니다.
  • BufferedWriter에 저장된 결과값을 출력하였습니다.
  • bfs day[] Queue를 통해 지점을 +1, -1, *2를 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N,K;
	public static int[] day = new int[100001];	//지점별 걸리는 최소 초 저장
    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());
    	if(N==K)	//시작 지점과 도착 지점이 같을 경우
    		bw.write("0");
    	else {
        	bfs();		//함수 실행
        	bw.write(day[K] + "\n");	//도착 지점 최소 걸리는 초 BufferedWriter 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //--------BFS으로 최소 걸리는 초를 구하는 함수---------
    public static void bfs() {
    	Queue<Integer> queue = new LinkedList<Integer>();
    	queue.add(N);
    	int count=1;
    	while(!queue.isEmpty()) {
    		int size = queue.size();
    		for(int i=0;i<size;i++) {
        		int start = queue.poll();
        		int tempPlus = start + 1;		// +1일 때
        		int tempMinus = start - 1;		// -1일 때
        		int tempMul = start * 2;		//*2일 때
        		if(tempMinus==K || tempMul==K||tempPlus==K) {	//목적 지점 도착시
        			day[K] = count;
        			return;
        		}
        		if(tempPlus<=100000 && day[tempPlus]==0) {
        			day[tempPlus] = count;
        			queue.add(tempPlus);
        		}
        		if(tempMinus>=0 && day[tempMinus]==0) {
        			day[tempMinus] = count;
        			queue.add(tempMinus);
        		}
        		if(tempMul<=100000 && day[tempMul]==0) {
        			day[tempMul] = count;
        			queue.add(tempMul);
        		}
    		}
    		count++;
    	}
    }
}
 

댓글