백준 12851번: 숨바꼭질 2

문제

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

---

풀이

수빈이는 현재 점 n(0 ≤ N ≤ 100,000)에 있고, 동생은 점 k(0 ≤ K ≤ 100,000)에 있을 때 수빈이는 걷거나 순간이동할 수 있습니다. 수빈이의 위치가 x일 때 걷는다면 1초 후에 x-1 또는 x+1로 이동하게 되고 순간이동을 하는 경우에는 1초 후에 2x의 위치로 이동하게 될 때 동생을 찾을 수 있는 가장 빠른 시간과 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 문제입니다.

---

접근

수빈이가 걷는 시간과 순간이동하는 시간이 1초로 동일하기 때문에 이 문제는 간단한 BFS 알고리즘을 이용하여 풀 수 있는 것은 숨바꼭질 문제와 동일하지만 이 문제에서는 가장 빠른 시간으로 찾는 방법의 개수까지 구해야 합니다.

그래서 이 글의 풀이처럼 정수 배열 arr가 임의의 수 x가 있을 때 arr[x]는 n에서 x까지 이동하는 데 걸린 시간을 의미하는 것은 동일하지만 n에서 x까지 가장 빠른 시간으로 이동하는 방법의 개수를 의미하는 정수 배열 cnt를 추가했습니다.

---

코드

자바

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

public class Main {

    static int n, k;
    static int[] arr = new int[100001], cnt = new int[100001];

    public static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        while (!queue.isEmpty()) {
            int x = queue.poll();
            int[] dx = { x - 1, x + 1, x * 2 };
            for (int nx : dx) { // (1)
                if (0 <= nx && nx <= 100000) {
                    if (arr[nx] == 0) { // (2)
                        queue.offer(nx);
                        arr[nx] = arr[x] + 1;
                        cnt[nx] = cnt[x];
                    } else if (arr[nx] == arr[x] + 1) { // (3)
                        cnt[nx] += cnt[x];
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(arr[k]).append("\n").append(cnt[k]);
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        if (n == k) {
            System.out.println("0\n1");
        } else {
            cnt[n] = 1;
            bfs();
        }
    }
}

n과 k를 입력받고 cnt[n]을 1로 초기화한 후에 bfs 함수를 실행합니다.

이때 n과 k가 같으면 이동하지 않아도 되고 그 방법은 1개이지만 bfs 함수 안의 조건에 의해 다른 값이 나올 수 있기 때문에 "0\n1"을 출력한 후에 프로그램을 종료합니다.

큐에는 수빈이가 현재 위치하고 있는 점의 번호가 들어가며 처음에 n을 삽입한 후에 큐가 비어있을 때까지 아래 과정을 반복합니다.

 

(1) 큐에서 poll한 값을 x라고 했을 때 수빈이가 1초 후에 있을 수 있는 위치는 x - 1, x + 1, 2 * x입니다.

foreach문을 통해서 다음 위치(nx)가 가능한 위치인지 확인합니다.

 

(2) arr[nx]가 0인지 확인합니다.

0이라면 방문한 적이 없다는 뜻이므로 arr[nx]는 arr[x] + 1로 x에서 nx로 이동하는데 걸린 가장 빠른 시간으로 초기화합니다. 또한 cnt[nx]는 cnt[x]로 초기화하는데 이렇게 되는 이유는 간단합니다. 방문한적이 없는 위치에 가장 먼저 방문한 것이므로 n에서 nx로 가장 빠른 시간으로 이동하는 방법의 개수는 n에서 x까지 가장 빠른 시간으로 이동하는 방법의 개수와 동일합니다.

여기서 위에서 적은 n과 k가 같은 경우에 문제가 생깁니다.

n에서 k까지 가장 빠른 시간으로 이동하는 방법의 개수를 구해야 하는 문제 조건 때문에 x가 k와 같은 경우에 함수를 종료할 수 없습니다. 그래서 x는 이미 k이지만 x + 1이 큐에 삽입된 후에 (x + 1) - 1이 삽입되는 등의 오류가 발생하게 됩니다.

그렇기 때문에 n과 k가 같으면 bfs 함수를 실행하지 않고 "0\n1"을 출력한 후에 프로그램을 종료하는 것입니다.

 

(3) arr[nx]가 arr[x] + 1와 같은지 확인합니다.

같다면 n에서 x을 거치지 않고 nx까지 걸린 최소 시간과 x을 거친 후에 nx까지 걸린 최소 시간이 같다는 뜻입니다.

따라서 cnt[nx]에 cnt[x]를 더해줍니다.

 

while문이 종료되면 Stringbuilder sb에 arr[k]와 cnt[k]의 값을 넣었다가 한꺼번에 출력합니다.

자바(Priority Queue)

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class point implements Comparable<point> {
    int x, cnt;

    public point(int x, int cnt) {
        this.x = x;
        this.cnt = cnt;
    }

    @Override
    public int compareTo(point o) {
        return cnt - o.cnt;
    }
}

public class Main {

    static int n, k, cnt = 0, min = Integer.MAX_VALUE;
    static boolean[] visited = new boolean[100001];

    public static void bfs() {
        PriorityQueue<point> queue = new PriorityQueue<>();
        queue.offer(new point(n, 0));
        while (!queue.isEmpty()) {
            point p = queue.poll();
            visited[p.x] = true;
            if (p.x == k) { // (1)
                if (min >= p.cnt) { // (2)
                    min = p.cnt;
                    cnt++;
                    continue;
                } else break;
            }
            int[] dx = { p.x - 1, p.x + 1, p.x * 2 };
            for (int nx : dx) { // (3)
                if (0 <= nx && nx <= 100000 && !visited[nx]) {
                    queue.offer(new point(nx, p.cnt + 1));
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(min).append("\n").append(cnt);
        System.out.print(sb);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        bfs();
    }
}

이 코드는 우선순위큐와 bfs를 이용한 풀이입니다. 위의 코드에서 n과 k가 같은 경우에 오류가 나는 것을 해결할 수 있습니다.

정수 배열 arr와 cnt를 만들지 않고 방문 여부를 확인하기 위한 visited 배열과 동생을 찾을 수 있는 가장 빠른 시간을 의미하는 정수 min, 가장 빠른 시간으로 찾는 방법의 개수 cnt를 추가했습니다.

또한 현재 수빈이의 위치 x와 n에서 x까지 가장 빠르게 이동한 시간 cnt를 포함하는 point 클래스를 만들고 우선순위큐의 우선순위를 위해 Comparable 인터페이스의 compareTo 메서드를 수정(Override)하여 포함시켰습니다.

n과 k를 입력받고 bfs 함수를 실행하며 다른 코드와 다르게 큐에는 point가 들어가며 처음에 n을 삽입한 후에 큐가 비어있을 때까지 아래 과정을 반복합니다.

 

(1) 큐에서 poll한 값을 p라고 했을 때 visited[p.x]를 true로 초기화한 후에 p.x가 k와 같은지 확인합니다.

같다면 (2)번 과정을 실행하고 같지 않다면 (3)번 과정을 실행합니다.

 

(2) min이 p.cnt보다 크거나 같은지 확인합니다.

min이 p.cnt보다 크다면 최초로 k에 도착했다는 뜻이므로 min을 p.cnt로 바꾸는 것이고 같다면 k까지 가장 빠른 시간으로 이동하는 방법의 개수 cnt에 1을 더해준 후에 아래 연산은 필요 없기 때문에 continue 해줍니다.

만약 min이 p.cnt보다 작다면 k에 가장 빠르게 이동할 수 있는 경우가 남아있지 않다는 뜻이므로 break 해줍니다.

 

(3) 수빈이가 1초 후에 있을 수 있는 위치는 p.x - 1, p.x + 1, 2 * p.x입니다.

foreach문을 통해서 다음 위치(nx)가 가능한 위치이며 nx에 방문한 적이 있다면 p.cnt 이하의 시간으로 nx에 도착할 수 있다는 뜻이기 때문에 visited[nx]가 false인지 확인합니다.

위의 조건을 만족하면 큐에 point(nx, p.cnt + 1)를 삽입해줍니다.

 

while문이 종료되면 Stringbuilder sb에 min와 cnt의 값을 넣었다가 한꺼번에 출력합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int n, k, arr[100001], cnt = 0, min = INT_MAX;
typedef struct node {
	int data;
	struct node* next;
} node;
typedef struct Queue {
	node* front;
	node* rear;
	int count;
} Queue;
void initQueue(Queue* queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
}
void push(Queue* queue, int data) {
	node* now = (node*)malloc(sizeof(node));
	now->data = data;
	now->next = NULL;
	if (queue->count == 0) {
		queue->front = now;
	}
	else {
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}
int pop(Queue* queue) {
	int re;
	node* now;
	if (queue->count == 0) {
		return -1;
	}
	now = queue->front;
	re = now->data;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int empty(Queue* queue) {
	if (queue->count == 0) return 1;
	else return 0;
}
void bfs() {
	Queue queue;
	initQueue(&queue);
	push(&queue, n);
	while (!empty(&queue)) {
		int x = pop(&queue);
		if (x == k && min >= arr[k]) { // (1)
			min = arr[k];
			cnt++;
			continue;
		}
		int dx[] = { x - 1, x + 1, x * 2 };
		for (int i = 0; i < 3; i++) {
			int nx = dx[i];
			if (0 <= nx && nx <= 100000 && (arr[nx] == 0 || arr[nx] == arr[x] + 1)) { // (2)
				push(&queue, nx);
				arr[nx] = arr[x] + 1;
			}
		}
	}
	printf("%d\n%d", min, cnt);
}
main() {
	scanf("%d %d", &n, &k);
	bfs();
}

자바를 이용한 풀이 2개를 합친 느낌이라고 생각하면 편할 것 같습니다.

Priority Queue를 구현하진 않았으며 첫 번째 풀이에서의 arr 배열을, 2번째 풀이에서의 min과 cnt를 사용했습니다.

큐에는 수빈이가 현재 위치하고 있는 점의 번호가 들어가며 처음에 n을 삽입한 후에 큐가 비어있을 때까지 아래 과정을 반복합니다.

 

(1) 큐에서 poll한 값을 x라고 했을 때 x가 k와 같고 min이 arr[k]보다 크거나 같은지 확인합니다.

min이 arr[k]보다 크다면 최초로 k에 도착했다는 뜻이므로 min을 arr[k]로 바꾸는 것이고 같다면 k까지 가장 빠른 시간으로 이동하는 방법의 개수 cnt에 1을 더해준 후에 아래 연산은 필요 없기 때문에 continue 해줍니다.

 

(2) 수빈이가 1초 뒤에 이동할 위치 nx가 가능한 위치인지 확인하고 arr[nx]가 0이거나 arr[x] + 1와 같은지 확인합니다.

arr[nx]가 0이면 방문한 적이 없다는 뜻이기 때문에 arr[nx]에 arr[x] + 1를 넣어주고 큐에 삽입해줍니다.

arr[nx]가 0이 아니고 arr[x] + 1과 같다면 n에서 x을 거치지 않고 nx까지 걸린 최소 시간과 x을 거친 후에 nx까지 걸린 최소 시간이 같다는 뜻이므로 큐에 삽입해줍니다.

 

while문이 종료되면 min와 cnt의 값을 출력합니다.

---

결론

지난 숨바꼭질 문제를 응용했다고 볼 수 있는 문제였습니다. 위에 풀이를 3개 적어놨는데 같은 문제라도 다양한 방법으로 해결할 수 있다는 사실을 다시 느낄 수 있는 시간이었던 것 같습니다.