[백준 1697번] 숨바꼭질

난이도: 실버 I

문제 링크: https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

백준 1697번 문제 숨바꼭질

한동안 면접 준비하고 교육 받느라 알고리즘에 뜸했던 탓인지 좀 어려운 문제를 못 풀겠어서 (ㅠㅠ)

비교적 간단한 실버1 문제를 풀어 봤습니다.

 

출발점 n에서 도착점 k까지의 도달 최단 시간을 구하는 문제입니다.

n에서 이동은 [n - 1, n + 1, n * 2] 세 가지만 가능하며, 각 이동은 1초가 소요됩니다.

따라서 탐색 알고리즘을 이용하면 쉽게 풀 수 있으며, 저는 BFS를 이용하였습니다.

 

visited 배열에 아직 방문하지 않은 위치의 도착 시간은 무한 (INF)으로 설정하고, 시작점은 0으로 설정합니다.

이동하려는 곳의 도착 시간이 현재 위치의 도착시간 + 1보다 크면, 이동하려는 곳의 도착 시간을 현재 위치의 도착시간 + 1으로 갱신하고, 이동하려는 곳을 queue에 넣습니다.

편의성을 위해 이동하는 위치가 범위 내에 있는지 검사하는 in_boundary 함수, n에서 이동하는 경우를 return하는 move 함수 등을 별도로 작성하여 사용하였습니다.

 

코드 (C++, Java):

	#include <iostream>
	#include <queue>
	using namespace std;
	#define MAX_N 100001
	#define INF 1e9
	int n, k;
	int visited[MAX_N];
	void init() {
	for (int i = 0; i < MAX_N; i++) {
	visited[i] = INF;
	}
	visited[n] = 0;
	}
	bool in_boundary (int input) {
	if (input < 0 || input >= MAX_N) return false;
	else return true;
	}
	int move (int input, int mode) {
	if (mode == 0) return input - 1;
	else if (mode == 1) return input + 1;
	else if (mode == 2) return input * 2;
	else return -1;
	}
	int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k;
	init();
	queue<int> q;
	q.push(n);
	while(!q.empty()) {
	int now = q.front();
	q.pop();
	for (int i = 0; i < 3; i++) {
	int next = move(now, i);
	if (!in_boundary(next)) continue;
	if (visited[now] + 1 < visited[next]) {
	visited[next] = visited[now] + 1;
	q.push(next);
	}
	}
	}
	cout << visited[k];
	return 0;
	}

view raw 1697_숨바꼭질.cpp hosted with ❤ by GitHub

	import java.util.*;
	public class Main {
	static int n, k;
	static int MAX_N = 100001;
	static int INF = 100000000;
	static int visited[] = new int[MAX_N];
	static void init() {
	for (int i = 0; i < MAX_N; i++) {
	visited[i] = INF;
	}
	visited[n] = 0;
	}
	static boolean in_boundary(int input) {
	if (input < 0 || input >= MAX_N) return false;
	else return true;
	}
	static int move(int input, int mode) {
	if (mode == 0) return input - 1;
	else if (mode == 1) return input + 1;
	else if (mode == 2) return input * 2;
	else return -1;
	}
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	k = sc.nextInt();
	init();
	Queue<Integer> q = new LinkedList<>();
	q.add(n);
	while(!q.isEmpty()) {
	int now = q.poll();
	for (int i = 0; i < 3; i++) {
	int next = move(now, i);
	if (!in_boundary(next)) continue;
	if (visited[now] + 1 < visited[next]) {
	visited[next] = visited[now] + 1;
	q.add(next);
	}
	}
	}
	System.out.println(visited[k]);
	}
	}

view raw 1697_숨바꼭질.java hosted with ❤ by GitHub

 

채점 결과