티스토리 뷰
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 배열에 시간을 담기
'알고리즘 기록' 카테고리의 다른 글
BR vs Scanner (0) | 2024.09.15 |
---|---|
(Java) Baekjoon 평범한 배낭, 1로 만들기, 2xn 타일링 - DP (0) | 2024.09.12 |
Binary search VS Parametric Search (0) | 2024.09.09 |
(Java) Baekjoon 14500 테트로미노 - dfs, 구현 (0) | 2024.09.05 |
(Java) SWEA 1952 수영장 - dfs / dp (1) | 2024.09.03 |