[java]숨바꼭질 3 - 백준13549
문제
풀이
문제 해석을 하자면,
- 숨바꼭질 문제는 시리즈로 여러개 존재한다.
- 특히 이 문제에서는 다양한 풀이방법이 존재해서 따로 정리하려고 한다.
풀이
- 풀이코드 총 4개를 소개한다.
- BFS + dist 배열 -> dist 배열 사용이 핵심
- BFS + Pair 객체 -> 2*X 는 0초 이므로 해당 시점에 while로 가능한 2*X 를 모두 큐에 추가 + visited 시점
- 다익스트라 -> 가중치가 0과 1이므로 가중치가 다른 최단거리는 해당 알고리즘이 적합
-
0-1 BFS -> 가중치가 0과 1일 때 사용할 수 있는 알고리즘이다.
- 가능한 최대 이동시간이 10만이므로 큐배열을 크기 10만으로 잡는다.
- 그럼 t = 0 일때, N에 있으므로 queue[0] 에 N을 넣어준다.
- 이제 큐에서 원소를 빼면서 2배 증가하는 위치는 시간이 증가하지 않으므로 같은 큐에 삽입하고, 시간이 소모되는 +1, -1 이동 작업은 다음 인덱스 큐에 넣어준다.
- 차례대로 t번 큐라고 불렀을 때, t번 큐가 모두 소모되면 더 이상 t 시간에 돌아갈 원소가 없다는 의미이므로 t + 1 큐를 그 다음으로 호출한다. 이를 반복문을 통해 돌리자.
-
덱 자료구조를 활용해서 더 쉽게 구현할 수 있다.
- 항상 앞에서 원소를 꺼낸다
- 방금 꺼낸 원소와 다음 상태로 전달되는 시간이 같으면 (2배 하는 경우) 원소를 앞에 push
- 시간이 증가하면 원소를 뒤에 push
코드
BFS + dist 배열
/**
* 2*X일땐 배열에 +1을 하지 않았다
*/
static int N, K;
static int[] dist = new int[200005];
static void bfs() {
// init
Arrays.fill(dist,-1); // 방문기록 확인 위해
Queue<Integer> qu = new LinkedList<>();
qu.add(N);
dist[N] = 0;
while(!qu.isEmpty()) {
int cur = qu.peek(); qu.remove();
if(cur < 0 || cur > 200000) continue; // 범위체크
for(int i=0; i<3; i++) {
if(i==0) { // 2*X => 0초
int nxt = cur*2;
// 범위체크, 방문확인
if(nxt < 0 || nxt > 200000 || dist[nxt]!=-1) continue;
dist[nxt] = dist[cur]; // 0초라서 +1 하지말것.
qu.add(nxt);
}
else if(i==1) { // X-1
int nxt = cur-1;
// 범위체크, 방문확인
if(nxt < 0 || nxt > 200000 || dist[nxt]!=-1) continue;
dist[nxt] = dist[cur] + 1;
qu.add(nxt);
}
else { // X+1
int nxt = cur+1;
// 범위체크, 방문확인
if(nxt < 0 || nxt > 200000 || dist[nxt]!=-1) continue;
dist[nxt] = dist[cur] + 1;
qu.add(nxt);
}
}
}
}
public static void main(String[] args) throws IOException {
// input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(stk.nextToken());
K = Integer.parseInt(stk.nextToken());
// run
bfs();
// output
System.out.println(dist[K]);
}
BFS + Pair 객체
static int N, K;
static int result; // 동생 찾는 시간
static boolean[] visited;
static void check(Pair cur, Deque<Pair> qu) {
// 2가지 연산 경우로 가지치기
int x = cur.x;
int time = cur.time;
if(x+1 <= K+1 && !visited[x+1]) { // x+1 범위 방지 필수
qu.offer(new Pair(x + 1, time+1));
}
if(x-1 >= 0 && !visited[x-1]) { // x-1 음수 방지 필수
qu.offer(new Pair(x - 1, time+1));
}
}
static void bfs(){
Deque<Pair> qu = new ArrayDeque<>();
qu.offer(new Pair(N, 0));
visited[N] = true;
while(!qu.isEmpty()) {
int size = qu.size();
for (int s = 0; s < size; s++) {
Pair cur = qu.poll();
if(cur.x==K) {
result = cur.time;
return;
}
visited[cur.x] = true;
check(cur, qu);
while(true) {
cur.x*=2; // 2배 해서 check 함수 재사용 목적
if(cur.x > K*2 || visited[cur.x]) break;
if(cur.x==K) { // 반복코드
result = cur.time;
return;
}
visited[cur.x] = true; // 여기까지 동일
check(cur, qu);
}
}
}
}
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(stk.nextToken());
K = Integer.parseInt(stk.nextToken());
visited = new boolean[300005]; // 2X 연산 때문에 크기 넉넉히 잡았음
//run
bfs();
//output
System.out.println(result);
}
static class Pair {
int x; int time;
public Pair(int x, int time) {
this.x=x; this.time=time;
}
}
다익스트라
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(stk.nextToken());
int K = Integer.parseInt(stk.nextToken());
int[] dist = new int[100001];
Arrays.fill(dist, 0, 100001, Integer.MAX_VALUE/3);
Queue<Pair> pq = new PriorityQueue<Pair>();
dist[N]=0;
pq.offer(new Pair(N, dist[N]));
while (!pq.isEmpty()) {
Pair cur = pq.poll();
if(cur.val != dist[cur.dst]) continue; // 예외처리
int nxt = cur.dst-1;
if(isValid(nxt)) {
if(dist[nxt] > dist[cur.dst]+1) {
dist[nxt] = dist[cur.dst]+1;
pq.offer(new Pair(nxt, dist[nxt]));
}// 가중치는 +1 or 0
}
nxt = cur.dst+1;
if (isValid(nxt)) {
if(dist[nxt] > dist[cur.dst]+1) {
dist[nxt] = dist[cur.dst]+1;
pq.offer(new Pair(nxt, dist[nxt]));
}
}
nxt = cur.dst*2;
if (isValid(nxt)) {
if(dist[nxt] > dist[cur.dst]) {
dist[nxt] = dist[cur.dst];
pq.offer(new Pair(nxt, dist[nxt]));
}
}
}
//debug
// System.out.println(Arrays.toString(Arrays.copyOfRange(dist, 0, K+1)));
System.out.println(dist[K]);
}
static boolean isValid(int pos) {
return 0 <= pos && pos <= 100000;
}
static class Pair implements Comparable<Pair> {
int dst; int val;
public Pair(int dst, int val) {
this.dst = dst; this.val = val;
}
@Override
public int compareTo(Pair o) {
return this.val-o.val; //asc
}
}
0-1 BFS
/**
* 가중치가 0, 1 이라면 0-1 BFS 방법을 사용할 수 있다.
* 덱 사용시 가중치가 0인걸 우선순위로 앞에 넣고,
* 가중치가 1인걸 우선순위가 낮으므로 뒤에 넣는다. -> 우선순위 큐처럼 가능한것. 속도는 이게 더 빠름.
* visited true 시점 중요 -> 큐 삽입시점에 하게되면 우선순위 때문에 문제가 발생하므로 주의.
*/
static boolean visited[] = new boolean[100001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(stk.nextToken());
int K = Integer.parseInt(stk.nextToken());
Deque<Pair> dq = new ArrayDeque<>();
visited[N] = true;
dq.offer(new Pair(N, 0)); //init
int result = 0;
while (!dq.isEmpty()) {
Pair cur = dq.removeFirst();
visited[cur.dst] = true;
if (cur.dst == K) {
result = cur.val;
break;
}
int nxt = cur.dst-1;
if(isValid(nxt) && !visited[nxt]) {
dq.addLast(new Pair(nxt, cur.val + 1));
// 가중치는 +1 or 0
}
nxt = cur.dst+1;
if (isValid(nxt) && !visited[nxt]) {
dq.addLast(new Pair(nxt, cur.val+1));
}
nxt = cur.dst*2;
if (isValid(nxt) && !visited[nxt]) {
dq.addFirst(new Pair(nxt, cur.val)); //우선순위
}
}
System.out.println(result);
}
static boolean isValid(int pos) {
return 0 <= pos && pos <= 100000;
}
static class Pair {
int dst; int val;
public Pair(int dst, int val) {
this.dst = dst; this.val = val;
}
}
느낀점
생략
댓글남기기