[JAVA] 백준 1697번 - 숨바꼭질

문제

1697번: 숨바꼭질

[ 해결순서 ]

1. 문제의 조건을 파악한 후 이동을 할 때 3가지 경우에 따라 조건문을 작성하면 되겠다고 파악했다.
2. 큐를 이용하여 시작 값을 먼저 큐에 넣고
3. 큐가 비어있을 때까지 반복해서 큐의 값을 꺼내어 3가지 조건을 너비우선탐색을 이용한다.
4. 값이 조건에 벗어나지 않고, 방문을 하지 않았으면 그 값을 큐에 넣어 재귀호출을 통해 그 값을 기준으로 또 너비우선탐색을 한다.
5. 결과의 위치를 찾으면 그 위치가 몇 초후에 찾았는지 visited 배열의 값에 넣어 출력한다.

✏️ 한줄 평

이런 종류의 문제를 너비우선탐색을 이용하여 풀 수 있구나를 제대로 알게 된 문제였다.

---

코드

	package July_3;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Scanner;
	public class Main1697 {
	static int[] visited = new int[100001]; //몇 초 후에 방문했는지를 위한 배열
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n=sc.nextInt();
	int k=sc.nextInt();
	move(n,k);
	}
	public static void move(int n, int k) {
	Queue<Integer> q = new LinkedList<>();
	q.offer(n); //처음 값 n을 넣음 !
	while (!q.isEmpty()) {
	int value = q.poll();//큐에 있는 제일 첫번째 값을 꺼냄
	if(value==k) {
	System.out.println(visited[k]);
	break;
	}
	// 꺼낸 값을 기준으로 너비우선탐색
	if(value-1>=0 && visited[value-1]==0){ //x-1로 이동
	q.offer(value-1);
	visited[value-1]=visited[value]+1;
	}if(value+1<=100000 && visited[value+1]==0){ //x+1로 이동
	q.offer(value+1);
	visited[value+1]=visited[value]+1;
	}if(value*2<=100000 && visited[value*2]==0){ //x*2로 이동
	q.offer(value*2);
	visited[value*2]=visited[value]+1;
	}
	}
	}
	}

view raw BOJ1697.java hosted with ❤ by GitHub