[백준] 13549번 숨바꼭질 3 JAVA (자바) 풀이
문제 13549(BFS)
: 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다
현 위치가 X일 때
걷기 = 1초 후에 X-1 또는 X+1로 이동
순간이동 = 0초 후에 2*X의 위치로 이동
수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구해라
[입력]
: 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K
[출력]
: 동생을 찾는 가장 빠른 시간을 출력
[문제접근]
1. 기존 숨바꼭질 1697번과 차이점!
- 기존 문제에서는 모든 이동이 동일한 1초를 소요
- 현 문제에서는 순간 이동은 0초 / 걷기 이동만 1초 소요
2. 출력 배열 사용하지 말고 큐에다 넣어버리기
- count[] 배열보다 큐 자체에 넣는 것이 더 간단하다 q.add(new int{start,0}) 추천
3. for문 상하좌우 이동을 떠올릴 것
- 보통 상하좌우 해서 내가 갈 수 있는 방향만큼 for문을 돌려 다음 위치를 큐에 넣어준다
- next 지점만 더해줄게 아니라 time 도 각각 계산한다
- 지금은 갈 수 있는 위치가 3가지이다
- 첫번째 X * 2 / 현시간 + 0
- 두번째 X - 1 / 현시간 + 1
- 세번째 X + 1 / 현시간 + 1
4. 이동 명령의 순서는 매우 중요하다!!
- 큐에 넣는 순서대로 계산하기 때문에 우선순위에 맞게 넣는 것이 중요
- 최적의 경로를 찾기 위해선 무조건 최단시간이여야 맞다
- 고로 0초가 걸리는 순간이동이 1순위므로 제일 첫번째에 둔다
- 그 다음 바로 전진하기 보단 목적지를 벗어났을 경우 뒤로 가는 것이 더 우선일 수 있기 때문에
뒤로 한칸 이동하는게 두번째 - 세번째가 앞으로 전진
5. visit 크기와 next 범위
- arr배열이 없어서 범위 파악하기가 명확하지 않다
가령 K가 17이라고 하더라도 수빈이가 18을 거쳐서 17로 갈 수 있기 때문에
대략 visit 크기는 K의 최대 입력인 100000만큼만 담아줬다 - next 범위도 마찬가지 100000까지 해줬는데 안돌아갈 경우 범위를 좀 더 크게 잡아야한다
6. bfs를 for문이나 재귀에 사용하지 말 것
- for(){ bfs } 하지말 것 (bfs 메서드 내에서 큐에 계속 추가하면서 반복하면 된다)
- bfs메서드 내에서 다시 bfs를 호출하지 말 것 (백트래킹이나 dfs와는 다르다)
[코드]
import java.io.*;
import java.util.*;
public class Main{
static int N,K;
static boolean visit[];
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());
visit = new boolean[100001];
bfs(N);
}
static void bfs(int start){
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{start, 0});
visit[start]=true;
while(!q.isEmpty()){
int p[] = q.poll();
if(p[0]==K){
System.out.println(p[1]);
return;
}
for(int i=0;i<3;i++){
int next;
int time;
if(i==0){
next = p[0]*2;
time = p[1];
}
else if(i==1){
next = p[0]-1;
time = p[1]+1;
}
else{
next = p[0]+1;
time = p[1]+1;
}
if(0<=next && next<=100000 && !visit[next]){
q.add(new int[]{next,time});
visit[next]=true;
}
}
}
}
}
[해설]
: static int N,K;
static boolean visit[];
: BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken()); 수빈 위치
K=Integer.parseInt(st.nextToken()); 동생 위치
visit=new boolean[100001]; 방문기록 체크
: bfs(N); bfs 실행
: static void bfs(int start){
Queue<int[]> q = new LinkedList<>(); 큐 선언
q.add(new int[] {start,0}); 큐 추가
visit[start]=true; 방문처리
while(!q.isEmpty()){
int p[] = q.poll(); 큐에서 뽑기
if(p[0]==K){ 현위치 K일 경우 종료
System.out.println(p[1]); 카운트 출력
return;
}
for(int i=0;i<3;i++){ 3가지 위치로 이동가능
int next;
if(i==0) 우선순위 1
next = p[0]*2; 0초 걸리는 순간이동이 젤 최적
time = p[1]; 0초를 더하므로 원래 타임유지
else if(i==1) 우선순위 2
next = p[0]-1; 한칸 더 뒤로가는 걷기이동이 2순위
time = p[1]+1; 1초를 더한다
else 우선순위 3
next = p[0]+1; 앞으로 전진이 3순위
time = p[1]+1; 1초를 더한다
if(0<=next && next<=100000 &&!visit[next]){ 갈 수 있는 위치라면
q.add(new int[] {next,time}); 큐에 추가
visit[next]=true; 방문처리
}
}
}
}
이제 풀어보러 갈께요 :)
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *