백준 1697번: 숨바꼭질

문제

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

1697번: 숨바꼭질

 

---

풀이

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

---

접근

수빈이가 걷는 시간과 순간이동하는 시간이 1초로 동일하기 때문에 이 문제는 간단한 BFS 알고리즘을 이용하여 풀 수 있습니다.

처음에 방문 처리를 위해 visited 배열을 만들까 생각했었지만 dp에서 사용했던 방식과 유사하게 정수 배열 arr 1개로 해결했습니다.

임의의 수 x가 있을 때 arr[x]는 n에서 x까지 이동하는 데 걸린 시간을 의미합니다.

만약 arr[x]가 0이라면 방문한 적이 없는 것이고 0이 아니라면 방문한 적이 있는 것으로 생각할 수 있습니다.

---

코드

자바

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];

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

    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();
    }
}

n과 k를 입력받고 bfs 함수를 실행합니다.

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

 

(1) 큐에서 poll한 값을 x라고 했을 때 x가 k와 같은지 확인합니다.

같다면 arr[k]를 출력한 뒤에 프로그램을 종료합니다. 위에서 설명한 것과 같이 arr[k]는 n번부터 k번까지 이동하는 데 걸린 시간을 의미합니다.

 

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

foreach문을 통해서 다음 위치(nx)가 가능한 위치이며 arr[nx]가 0인지 확인합니다.

위의 조건을 만족하면 큐에 nx를 삽입해준 뒤에 arr[nx]을 arr[x] + 1로 초기화합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
int n, k, arr[100001];
typedef struct node {
	int x;
	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 x) {
	node* now = (node*)malloc(sizeof(node));
	now->x = x;
	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;
	now = queue->front;
	re = now->x;
	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);
		int dx[] = { x - 1, x + 1, x * 2 };
		for (int i = 0; i < 3; i++) {
			if (x == k) {
				printf("%d", arr[k]);
				exit(0);
			}
			int nx = dx[i];
			if (nx >= 0 && nx <= 100000 && arr[nx] == 0) {
				push(&queue, nx);
				arr[nx] = arr[x] + 1;
			}
		}
	}
}
main() {
	scanf("%d %d", &n, &k);
	bfs();
}

자바를 이용한 풀이와 동일합니다.

 

---

결론

매우 쉬운 문제였지만 이 문제를 응용하여 풀어야 할 문제가 많아서 정리하게 되었습니다.

또한 이 코드에는 처음 bfs 함수를 실행했을 때 x + 1을 통해 n + 1로 이동한 후에 arr[n]이 0이기 때문에 x - 1을 통해 다시 n으로 이동하는 문제가 있습니다.