[BFS] 백준 1349번 숨바꼭질3 - JAVA

내 기분을 색깔로 표현하는 편 ^^

 

이제 곧 싸피데이!!!

 

싸피데이를 즐기기 전 숨바꼭질3 문제를 풀고 공부 기록 시작한다 ㅠ

 

---

1. 출처

---

13549번: 숨바꼭질 3

 

왜이리 어려운 것이냐?... 처음 이 문제를 보고, 어떻게 문제를 풀어야할지 감이 잡히지 않았다...

그래서 결국 구글링을 통해 다른 사람들의 코드를 보며 어떻게 문제를 짜야할지 봤던 문제..

 

https://www.acmicpc.net/board/view/115423

글 읽기 - dp 문제가 아닌지, 다익스트라 문제인지 어떻게 판단하셨나요?

 

질문 게시판을 보니 이런 질문도 있었는데 dp로 푸려고 했던 나는 엄청 공감이 되었다...

 

 

 

 

---

2. 설계

---

https://moonsbeen.tistory.com/97

[백준]13549: 숨바꼭질 3 - JAVA

 

내가 참고한 코드는 BFS로 푸신 이 분의 코드이다. 처음 코드를 봤을 때는 잘 이해가 안되었는데, 그림을 그리면서 이해하니 바로 이해가 되었다.

 

 

BFS로 풀면서 가장 궁금한 것은 큐에 넣는 대상이다. 큐에 넣는 대상은 현재 위치에서 X2, +1, -1했을 때의 위치이다. 그리고 그 곳을 갔을 때 걸리는 시간도 Node 클래스를 선언하여 넣어주었다.

 

public Node(int num, int time) {
	super();
	this.num = num;
	this.time = time;
}

 

그리고 큐에서 하나씩 빼내주면서 위 그림처럼 동생이 있는 위치가 나오면 거리 최소값 min값을 갱신해주면 된다. 때문에 visited로 방문 체크는 필수다. 이미 방문한 위치는 더이상 방문하지 않는다.

 

 

 

---

3. 전체 코드

---

package BJ13549;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 숨바꼭질3 {

	static boolean[] visited;
	static final int max = 100000;
	static int min_result = Integer.MAX_VALUE;
	static int N,K;
	
	static class Node{
		int num;
		int time;//0, 1
		public Node(int num, int time) {
			super();
			this.num = num;
			this.time = time;
		}
	}
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		
		N = sc.nextInt();//수빈 위치
		K = sc.nextInt();//동생 위치
		//입력 받기 끝
		
		
		visited = new boolean[max+1];
		
		bfs();
		
		System.out.println(min_result);
		
	}
	
	public static void bfs() {
		Queue<Node> p = new LinkedList<>();
		
		//첫 노드 넣기 수빈이가 있는 위치임
		p.add(new Node(N,0));
		visited[N] = true;
		
		while(!p.isEmpty()) {
			Node cur = p.poll();//현재 위치 및 시간
			visited[cur.num] = true;
			
			//어떤 경로로 가던 동생이 있는 위치로 오면 걸린 가장 적은 시간, min값을 체크해준다.
			if(cur.num==K) {
				min_result=Math.min(min_result, cur.time);
			}
			
			//하나 위치에 대해 순간이동, +1 , -1 했을 경우 만족하는지 확인한다.
			//갔던 위치는 다시 가지 않게 한다.
			//순간이동
			if(cur.num*2<=max && !visited[cur.num*2]) {
				p.add(new Node(cur.num*2,cur.time));//시간은 0이 지남 순간이동한 것임
			}
			
			//+1
			if((cur.num+1)<=max && !visited[cur.num+1]) {
				p.add(new Node(cur.num+1,cur.time+1));//1초걸림
			}
			
			//-1
			if((cur.num-1) >= 0 && !visited[cur.num-1]) {
				p.add(new Node(cur.num-1,cur.time+1));//1초걸림
			}
		}
	}
}