티스토리 뷰

12851번: 숨바꼭질 2 (acmicpc.net)

 

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

public class Main12851_숨바꼭질2 {
	static int N, K, minT, cnt, visited[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 현재 위치
		K = sc.nextInt(); // 동생 위치
		cnt = 0;
		minT = Integer.MAX_VALUE;
		visited = new int[100001];

		if (N >= K) {
			System.out.println(N - K);
			System.out.println(1);
			return;
		}

		find();

		System.out.println(minT);
		System.out.println(cnt);

	}

	private static void find() {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(N);
		visited[N] = 1;

		while (!queue.isEmpty()) {
			int cur = queue.poll();

			if (minT < visited[cur])	//이전 방문시간이 현재 방문시간보다 빠름
				return;

			for (int i = 0; i < 3; i++) {
				int nxt;
				if (i == 0)
					nxt = cur + 1;
				else if (i == 1)
					nxt = cur - 1;
				else
					nxt = cur * 2;

				if (nxt < 0 || nxt > 100000)
					continue;
				
				if (nxt == K) {
					minT = visited[cur];
					cnt++;
				}

				if (visited[nxt] == 0 || visited[nxt] == visited[cur] + 1) {
					//이전 방문 시간과 현재 방문 시간이 일치할 때
					queue.add(nxt);
					visited[nxt] = visited[cur] + 1;
				}
			}
		}
	}
}

어렵ㄷr,,, 

아이디어를 잘 생각하는게 중요할 듯

내가 생각한 방법은 가지치기 한다고 했는데 시간 초과 났었다 ㅠㅠ 

 

중복이 되는 경우를 처리하는 법.. 

그리고 visited 배열에 시간을 담기

 

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함