Baekjoon 12851 숨바꼭질 2 JAVA

12851번: 숨바꼭질 2

문제

해당 문제는 수빈이와 동생의 위치가 주어졌을 때 수빈이가 몇 초 만에 동생 위치로 갈 수 있는지와 가는 같은 시간 내 갈 수 있는 경우의 수를 구하는 문제다.

조건

수빈이는 1초 후 x-1 또는 x+1로 또는 2*x로 이동 가능하다.

최대 100000까지 이동 가능하다.

풀이

해당 문제는 bfs를 이용해서 해결했다. 예전과 다르다면 이제 큐에 데이터 형식을 class를 하나 두어서 좌표와 이동 횟수를 넣는 식으로 진행했고, bfs를 돌리는 과정에서 조건을 통해서 이동 횟수를 저장하고, 이후 저장된 이동 횟수와 현재 이동 횟수를 비교하는 방법으로 총 이동 횟수를 저장했고, 저장된 이동 횟수와 큐에서 빼낸 이동 횟수가 더 크면 멈추는 식으로 로직을 구현했다.

처음 방문 체크를 하고 문제를 해결하니 테케에서 체크가 되지 않아서 방문 체크를 하지 않고 문제를 해결하고 제출을 했지만 메모리 초과가 발생했고, 이후 생각을 하던 중 큐에 넣을 때마다 방문 체크를 하는 게 아니라 큐에서 빼낼 때 방문 체크하는 방식으로 문제를 해결했다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, K, answer_time, answer_cnt;
	static boolean[] visit;
	static Queue<Node> q = new LinkedList<>();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		visit = new boolean[100001]; // K보다 멀리갔다가 돌아오는 경우도있으므로 100001으로 지정
		q.offer(new Node(N,0)); // 시작 좌표와 이동횟수를 처음 넣어줌.
		bfs();
		System.out.println(answer_time);
		System.out.println(answer_cnt);
	}
	
	private static void bfs() {
		while(!q.isEmpty()) {
			Node n = q.poll();
			if(answer_time == 0 && n.index == K) //이동 횟수 갱신 안됬고, 동생에게 도착했으면 이동 횟수 갱신
				answer_time = n.cnt;
			if(n.index == K && answer_time == n.cnt) // 동생에게 도착했고, 갱신된 이동 횟수와 이동 횟수가 같으면 카운트 증가
				answer_cnt++;
			if(answer_time != 0 && answer_time < n.cnt)// 이동 횟수가 갱신되었고, 현재 큐에서 빼낸 이동횟수가 갱신값보다 크면 종료
				return;
			visit[n.index] = true; // 큐에 넣을때 방문 체크를 하지않고 여기서해줌 => 큐에서 넣으면서 체크하면 다른 경로로 가야하는 값이 이미 방문처리로 못가도록 되므로
			int sub = n.index - 1;
			int add = n.index + 1;
			int mul = n.index * 2;
			if(sub >= 0 && !visit[sub]) {
				q.offer(new Node(sub, n.cnt + 1));
			}
			if(add <= 100000 && !visit[add]) {
				q.offer(new Node(add, n.cnt + 1));
			}
			if(mul <= 100000 && !visit[mul]) {
				q.offer(new Node(mul, n.cnt + 1));
			}
		}
	}
	
	static class Node{
		int index, cnt;
		Node(int index, int cnt){
			this.index = index;
			this.cnt = cnt;
		}
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

참고

해당 문제는 아래의 숨바꼭질 문제와 연관된 문제다.

Baekjoon 1697 숨바꼭질 JAVA

 

Baekjoon 13549 숨바꼭질 3 JAVA