[백준/1697/Java] 숨바꼭질 - BFS 풀이

BFS (너비 우선 탐색, Breadth-First Search) 알고리즘에서 기본적인 문제 하나를 풀어보도록 하겠습니다.

 

문제

1697번: 숨바꼭질 (acmicpc.net)

1697번: 숨바꼭질

 

문제를 먼저 풀고 오신 다음에 풀이를 보시는 것을 추천드립니다.

이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다.

이 글은 BFS 알고리즘으로 1차원 배열을 사용해서 푸는 것을 알아보는 글이라서 BFS로 풀어보겠습니다.

 

풀이

먼저 문제에서 제시한 룰을 정리해보겠습니다.

수빈이가 동생을 찾는 가장 빠른 시간이 몇 초인지 구하는 문제입니다.

수빈이의 위치가 x일 때 1초 후에 x-1, x+1, x*2 위치로 이동 또는 순간이동을 하게 됩니다.

- 0초 : x 위치

- 1초 : x-1, x+1, x*2 위치

 

수빈이의 위치를 배열의 인덱스로 정하고 시간을 이동할 때마다 적어보겠습니다.

0초일 때 0을 넣어야 맞지만 배열의 특성상 기본값이 0이기 때문에 0초를 1로 표시하겠습니다.

마지막에 시간을 구할 때는 값에서 -1을 하여 정확한 시간을 구하겠습니다. 

위치를 이동하다가 이미 방문한 적이 있는 위치는 값 변경을 하지 않습니다.

가장 빠른 시간을 구하는 것이 목적이기 때문입니다. 만약 1초 후, 3초 후에 같은 곳을 들렀다면 그 위치는 1이라는 값만 저장하면 그 값이 가장 빠른 시간이 됩니다.

- 현재시간 : n

- 1초 이동 후 : n+1

 

수빈이 위치가 처음에 2라고 가정하겠습니다.

시간별로 어떻게 되는지 알아보겠습니다.

0초

0초일 때 인덱스 2에 1을 저장하겠습니다.

그리고 1초가 지날 때마다 값에 1을 더 하겠습니다.

0초일 때

 

1초

수빈이는 1초 후 이동가능한 x-1, x+1, x*2 위치에 값 1에 1을 더해서 2를 저장합니다.

현재 위치 x는 2입니다.  x = 2 

x-1 위치는 인덱스 1이 됩니다. 인덱스 1에 값 2를 저장합니다.

x+1 위치는 인덱스 3이 됩니다. 인덱스 3에 값 2를 저장합니다.

x*2 위치는 인덱스 4가 됩니다. 인덱스 4에 값 2를 저장합니다.

즉, 1초 후에 수빈이가 위치할 수 있는 곳은 1, 3, 4가 됩니다.

1초일 때

2초

이제 2초일 때를 생각해야 하는데 x가 나올 수 있는 경우의 수가 3개입니다.

값이 2로 되어 있는 1, 3, 4입니다.

 

먼저 인덱스 1부터 보겠습니다.

x-1 위치는 인덱스 0이 됩니다. 인덱스 1에 값 3를 저장합니다.

x+1 위치는 인덱스 2가 됩니다.  인덱스 2에 값 1이 존재합니다. 이미 가본 적이 있는 위치이므로 값 변경을 하지 않습니다.

x*2 위치는 인덱스 2가 됩니다. 인덱스 2에 값 1이 존재합니다. 이미 가본 적이 있는 위치이므로 값 변경을 하지 않습니다.

2초일 때 인덱스 1

 

그 다음 인덱스 3을 보겠습니다.

x-1 위치는 인덱스 2가 됩니다. 인덱스 2에 값 1이 존재합니다. 이미 가본 적이 있는 위치이므로 값 변경을 하지 않습니다.

x+1 위치는 인덱스 4가 됩니다.  인덱스 4에 값 2가 존재합니다. 이미 가본 적이 있는 위치이므로 값 변경을 하지 않습니다.

x*2 위치는 인덱스 6이 됩니다. 인덱스 6에 값 3을 저장합니다.

2초일 때 인덱스 3

마지막으로 인덱스 4를 보겠습니다.

x-1 위치는 인덱스 3이 됩니다. 인덱스 3에 값 2가 존재합니다. 이미 가본 적이 있는 위치이므로 값 변경을 하지 않습니다.

x+1 위치는 인덱스 5가 됩니다.  인덱스 5에 값 3이 존재합니다. 이미 가본 적이 있는 위치이므로 값 변경을 하지 않습니다.

x*2 위치는 인덱스 8이 됩니다. 인덱스 8에 값 3을 저장합니다.

 

2초일 때 인덱스4

3초는 인덱스 중 값이 3인 것만 모아서 각각 x-1, x+1, x*2 위치로 이동하면서 값을 변경하면 됩니다.

인덱스 값이 3인 것들은 인덱스 0, 5, 6, 8입니다.

이동하다가 동생이 있는 위치에 도달하면 그 시간이 가장 빠른 시간이 됩니다.

예제 풀이

문제에서 제시한 예제로 제가 한 풀이를 설명드리겠습니다.

- 수빈이의 위치 : 5

- 동생의 위치 : 17

 

0초

0초일 때 인덱스 2에 1을 저장하겠습니다.

배열은 공간의 문제로 인덱스 20까지만 표시하겠습니다.

0초

1초

1초일 때 인덱스 5에서 이동을 시작합니다.

1초

2초

2초일 때 인덱스 4, 6, 10에서 이동을 시작합니다.

이미 방문한 곳이 있어서 제가 x-1, x+1, x*2는 처음 방문하는 곳만 적었습니다.

2초

3초

3초일 때 인덱스 3, 7, 8, 9, 11, 12, 20에서 이동을 시작합니다.

아직 동생 위치인 17에 도착하지 못 했습니다.

3초

4초

4초일 때 인덱스 2, 13, 14, 16, 18, 19에서 이동을 시작합니다.

대부분 방문한 곳이라서 이번에 이동할 수 있는 곳이 그리 많지 않습니다.

(배열 인덱스 20 이상을 생략했기 때문에 그렇게 보입니다.)

드디어 동생 위치인 17에 도착했습니다.

4초

동생 위치에 5가 저장되어 있습니다.

값을 0이 아닌 1부터 시작했기 때문에 5에서 1을 빼주고 4를 출력하면 됩니다.

 

제일 빠른 시간을 출력하는 문제라서 경로얘기가 없는데요.

경로는 여러 개 가능합니다.

현재 예제는 이런 경로가 가능합니다.

5 -> 10 -> 9 -> 18 -> 17

5 -> 4 -> 8 -> 16 -> 17

 

 

소스

배열을 선언하고 이동은 BFS 알고리즘에서 사용하는 Queue를 사용합니다.

즉, 다음에 이동을 할 인덱스를 큐에 넣고 큐에서 꺼내면서 이동을 하면 제가 위에서 그린 그림과 비슷하게 이동하게 됩니다.

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

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

 

테스트

알고리즘 문제를 풀 때 테스트 값으로 다양하게 넣어서 검증하는 것이 좋습니다.

나중에 시간이 되면 동등분할, 경계값분석 등의 테스트기법에 대해서 얘기를 할 예정인데요.

일단 간단하게 생각할 수 있는 테스트값을 적어보겠습니다.

 

0 0

- 수빈이와 동생의 위치가 동일한 경우

 

0 100000

- 수빈이는 왼쪽 끝, 동생은 오른쪽 끝에 있는 경우

 

100000 0

- 수빈이는 오른쪽 끝, 동생은 왼쪽 끝

- 제가 예전에 다른 사람에게 문제를 풀어보라고 했을 때 이렇게 값을 넣으면 틀리는 경우가 많았습니다.

- 수빈이가 -1로만 움직일 수 있고 문제에 있는 조건을 보시면 1이 아닌 0부터 시작입니다. 주의하셔야 합니다.

 

관련글:

2020/12/10 - [Algorithm] - [알고리즘] 백준 온라인 저지 사이트 소개

[알고리즘] 백준 온라인 저지 사이트 소개

 

2020/12/11 - [Algorithm] - [알고리즘] 백준 온라인 저지 사이트 - 문제 채점

[알고리즘] 백준 온라인 저지 사이트 - 문제 채점