[BFS / DFS] [백준 / 1697 ] 실버1 - 숨바꼭질 (java/자바)
2차원 배열만 풀다가 이런 문제를 처음 푼다면?
비슷한 2차원 배열 문제:
[BFS / DFS] [백준 / 2178 ] 실버1 - 미로 탐색 (java/자바)
이제 막 DFS / BFS 알고리즘을 접했다면,
"이 문제가 왜 DFS/BFS 알고리즘으로 풀리는 걸까?" 감을 못잡을 것 같기도 하다.
지금까지 N*M 2차원 배열로 해당 알고리즘 풀이에 익숙해져서 그렇다.
2차원배열과 비슷한 이동 가능한 경우의 수
이전 2차원 배열에서 이동 경로 제약을 복기해보자.
다음 좌표로 이동할때마다. 위,아래,왼쪽,오른쪽으로만 갈 수 있다.
이번 문제도 똑같이 이동 경로 제약이 있다.
X는 X-1, X+1, 그리고 2*X으로만 갈 수 있다.
이동경로가 4개에서 -> 3개로 줄은 것 뿐이다.
2차원배열과 비슷한 이동 제약 조건
그렇다면 이 문제가 왜 DFS/BFS 알고리즘인지 어떻게 알 수 있을까?
2차원 배열에서 DFS/BFS 알고리즘에서 다음 좌표로 넘어갈 수있는 조건을 떠올려보자.
1. 좌표가 2차원 배열 내부여야한다.
2. 처음 방문인 좌표로만 넘어갈 수 있다.
3. 해당 좌표의 값이 1인 경우만 넘어갈 수 있다.
이 3가지 조건을 동시에 만족 시켜야 다음 좌표로 넘어갈 수 있다.
이번 문제에서 다음 좌표로 넘어갈 수 있는 조건을 위에서 힌트를 얻어보자.
1. 좌표가 1차원 배열 내부여야한다.
2. 처음 방문인 좌표로만 넘어 갈 수 있다.
3. --
이 2가지 조건을 동시에 만족 시켜야 다음 좌표로 넘어갈 수 있다.
2차원배열과 비슷한 탈출 조건
문제
성공 코드
package newboj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class boj_1697 {
static int N;
static int K;
static int [] timeToReach = new int[100001];
static boolean isVisited[] = new boolean[100001];
public static void main(String[] args) throws IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(r.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
BFS(N);
}
static void BFS(int firstStart){
isVisited[firstStart] =true;
Queue<Integer> q= new LinkedList<>();
q.add(firstStart);
timeToReach[firstStart] = 0; // 시작점의 시간을 0으로 초기화
while (!q.isEmpty()){
Integer currentX = q.poll();
if (currentX == K) {
System.out.println(timeToReach[currentX]); // 도달 시간 출력
return; // 프로그램 종료
}
int nextX1 = currentX - 1;
int nextX2= currentX + 1;
int nextX3 = currentX * 2;
if((0<=nextX1&& nextX1<100001) && !isVisited[nextX1]){
q.add(nextX1);
isVisited[nextX1] =true;
timeToReach[nextX1] = timeToReach[currentX] +1; // 다음 위치까지의 시간은 현재 위치의 시간 + 1
}
if((0<=nextX2&& nextX2<100001) &&!isVisited[nextX2]){
q.add(nextX2);
isVisited[nextX2] =true;
timeToReach[nextX2] = timeToReach[currentX] +1; // 다음 위치까지의 시간은 현재 위치의 시간 + 1
}
if((0<=nextX3& nextX3<100001) &&!isVisited[nextX3] ){
q.add(nextX3);
isVisited[nextX3] =true;
timeToReach[nextX3] = timeToReach[currentX] +1; // 다음 위치까지의 시간은 현재 위치의 시간 + 1
}
}
}
}왜 BFS로 풀었나요?
이 문제는 BFS가 적합합니다.
최단 시간 탐색: BFS는 시작 노드로부터 가까운 노드부터 차례대로 탐색하는 특성을 가지고 있습니다. 이 문제에서 요구하는 것은 수빈이가 동생을 찾을 수 있는 "가장 빠른 시간"입니다.
BFS를 사용하면, 가장 먼저 동생의 위치에 도달했을 때의 경로가 바로 최단 시간 경로임을 보장받을 수 있습니다.
반면, DFS(깊이 우선 탐색)는 최단 경로를 보장하지 않습니다.
레벨 별 탐색:BFS는 각 레벨(거리)에 따라 노드를 탐색하기 때문에, 현재 위치에서 동생의 위치까지의 최소 거리를 정확히 계산할 수 있습니다. 이는 순간이동과 걷기 등의 이동 방식을 고려할 때, 각 이동 수단을 통해 도달할 수 있는 모든 위치를 균등하게 탐색하며 최적의 해를 찾는 데 유리합니다.
