[BOJ] 1697 - 숨바꼭질 (Java)

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

1. 문제

• 수빈이가 동생을 찾을 수 있는 최소 시간을 구하는 문제

• 수빈이는 현재 위치에서 X-1, X+1, 또는 2*X로 이동할 수 있으며, 각 이동은 1초의 시간이 소요
  

2. Idea

• 너비 우선 탐색(BFS) 알고리즘 사용이 알고리즘은
  • 시작점에서 목표 지점까지의 최단 경로를 찾는 데 유용

3. 풀이

3.1. 변수 입력

• 수빈이의 현재 위치: N에
• 동생의 위치: K

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
		String[] inputs = input.split(" ");
		
		N = Integer.valueOf(inputs[0]);
		K = Integer.valueOf(inputs[1]);

3.2. bfs 함수 구현

• 너비 우선 탐색(BFS)을 사용하여 수빈이가 동생을 찾는 최소 시간을 계산
• visited 배열을 사용하여 이미 방문한 위치를 추적하고, 해당 위치에 도달하는 데 걸린 시간을 저장
• 초기에 수빈이의 위치를 큐에 넣고, 해당 위치를 방문한 것으로 표시
• while 큐가 빌 때까지
  • 큐에서 노드를 하나 꺼내어 현재 위치를 나타내는 변수인 n에 저장
  • 만약 n이 동생의 위치인 K와 같다면, 현재까지 걸린 시간인 visited[n]-1을 반환
  • 그렇지 않으면, n에서 갈 수 있는 모든 위치를 확인하고 방문하지 않은 위치는 큐에 추가
    -이때, 각 위치에 도달하는 데 걸리는 시간을 visited 배열에 저장

	private static int  bfs(int node)
	{
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.add(node);
		int index = node;
		int n = 0;
		visited[index] = 1;
		while (queue.isEmpty() == false)
		{
			n = queue.remove();
			
			if (n == K)
			{
				return visited[n]-1;
			}
			
			if (n-1>=0 && visited[n-1] == 0)
			{
				visited[n-1] = visited[n]+1;
				queue.add(n-1);
			}
			if (n+1 <= 100000 && visited[n+1] == 0)
			{
				visited[n+1] = visited[n]+1;
				queue.add(n+1);
			}
			if (2*n <= 100000 && visited[2*n] == 0)
			{
				visited[2*n] = visited[n] + 1;
				queue.add(2*n);
			}
		}
		return -1;
	}

3.3. 함수 호출 및 결과 출력

int result = bfs(N);
System.out.println(result);

4. 전체코드

import java.io.*;
import java.util.*;

public class Main
{
	static int N;
	static int K;
	
	static int visited[] = new int[100001];
	
	// X-1, X+1
	// 2*X
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
		String[] inputs = input.split(" ");
		
		N = Integer.valueOf(inputs[0]);
		K = Integer.valueOf(inputs[1]);
		
		int result = bfs(N);
		System.out.println(result);
	}

	private static int  bfs(int node)
	{
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.add(node);
		int index = node;
		int n = 0;
		visited[index] = 1;
		while (queue.isEmpty() == false)
		{
			n = queue.remove();
			
			if (n == K)
			{
				return visited[n]-1;
			}
			
			if (n-1>=0 && visited[n-1] == 0)
			{
				visited[n-1] = visited[n]+1;
				queue.add(n-1);
			}
			if (n+1 <= 100000 && visited[n+1] == 0)
			{
				visited[n+1] = visited[n]+1;
				queue.add(n+1);
			}
			if (2*n <= 100000 && visited[2*n] == 0)
			{
				visited[2*n] = visited[n] + 1;
				queue.add(2*n);
			}
		}
		return -1;
	}
}