[알고리즘][X] 숨바꼭질 2
2024. 2. 19. 17:40ㆍ알고리즘 풀이/Java
https://www.acmicpc.net/problem/12851
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static int N;
static int K;
static int[] map;
static boolean[] visited;
static int count;
static int number;
static boolean flag;
static StringBuilder sb = new StringBuilder();
static class Node {
int start;
int depth;
public Node(int start, int depth) {
super();
this.start = start;
this.depth = depth;
}
}
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());
visited = new boolean[100001];
if (N == K) {
sb.append(0).append("\n").append(1);
System.out.println(sb);
return;
}
count = 0;
number = 0;
flag = false;
bfs(new Node(N, 0));
sb.append(count).append("\n").append(number);
System.out.println(sb);
}
private static void bfs(Node start) {
Deque<Node> deque = new ArrayDeque<>();
deque.add(start);
visited[start.start] = true;
while (!deque.isEmpty()) {
Node curs = deque.poll();
int cur = curs.start;
int depth = curs.depth;
visited[cur] = true;
if (cur == K) {
if (!flag) {
flag = true;
count = depth;
number++;
} else {
if (depth == count) {
number++;
} else if (depth > count) {
return;
}
}
visited[cur] = false;
}
if (0 <= cur - 1 && cur - 1 <= 100000 && visited[cur - 1] != true) {
deque.add(new Node(cur - 1, depth+1));
}
if (0 <= cur + 1 && cur + 1 <= 100000 && visited[cur + 1] != true) {
deque.add(new Node(cur + 1, depth+1));
}
if (0 <= cur * 2 && cur * 2 <= 100000 && visited[cur * 2] != true) {
deque.add(new Node(cur * 2, depth+1));
}
}
}
}
나의 풀이
- 같은 위치일 때 예외처리를 했는데 출력을 안해줘서 틀렸다.
- 또한 sb를 bfs 안에 넣어서 틀렸다.
- 또한 이 문제는 1이 2가 될 때 1 + 1, 1 * 2가 될 수 있기 때문에 방문 처리는 나중에 해주어야 한다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘][X] 숨바꼭질 3 (0) | 2024.02.20 |
---|---|
[알고리즘][X] 숨바꼭질 4 (0) | 2024.02.20 |
[알고리즘] 캐슬 디펜스 (1) | 2024.02.16 |
[알고리즘] DFS와 BFS (1) | 2024.02.16 |
[알고리즘][X] 알파벳 (0) | 2024.02.16 |