문제 링크
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.
자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.
출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.
시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.
출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.
DFS
BFS
이 문제에 핵심은
1. 동생을 찾을 때 이동하는 경우는 +1, -1, *2가 존재합니다.
2. 동생을 찾는 최소 걸리는 초를 구해야 합니다.
저는 BFS(너비우선탐색)을 이용하여 문제를 해결하였습니다.
현재 위치를 기준으로 +1, -1, *2로 탐색을 진행하여 처음 목적지에 도착했을 때가 최소 걸리는 초입니다.
이 문제에서는 각 지점을 도착하는 최소 걸리는 초를 저장하기 위해 day[100001]를 만들어주었습니다.
check배열을 통해서 창고에 해당 지점을 탐색했는지를 확인하였습니다.
예제 입력1을 BFS로 탐색을 하는 과정을 보여드리겠습니다.
시작 지점 = 5, 도착 지점 = 17
1. 시작지점을 큐에 저장합니다.
Queue = {2}
2. 큐에 값을 꺼내서 이동할 수 있는 지점을 확인 및 큐에 저장
현재 지난 초 = 1초
꺼낸 값 = 5
5 + 1 = 6
5 - 1 = 4
5 * 2 = 10
Queue = { 6, 4 ,10}
day[6] = 1
day[4] = 1
day[10] = 1
3. 큐에 값을 꺼내서 이동할 수 있는 지점을 확인 및 큐에 저장
현재 지난 초 = 2초
꺼낸 값 = 6
6 + 1 = 7
6 - 1 = 5
6 * 2 = 12
day[7] = 2
day[5] = 0, 시작값이기 때문에 0
day[12] = 2
위와 같은 것을 반복하여 마지막으로 큐에 값을 꺼낼 때
현재 지난 초 = 4초
꺼낸 값 = 18(5 -> 10 -> 9 -> 18)
18 + 1 = 19
18 - 1 = 17
18 * 2 = 36
day[19] = 4
day[17] = 4
day[36] = 4
목적지 도착하였으므로 BFS 탐색을 종료하고 day[17]의 값 4를 출력하였습니다.
문제를 해결한 알고리즘의 과정입니다.
1. 출발 지점과 도착 지점을 저장합니다.
2. BFS(너비 우선 탐색)을 이용하여 +1, -1, *2 순으로 탐색을 진행합니다.
3. BFS종료후 최소 걸리는 초를 결과로 출력하였습니다.
- BufferedReader를 사용하여 입력 값을 받았습니다.
- StringTokenizer를 통해 시작지점과 도착지점을 저장하였습니다.
- BFS로 목적 지점 도착하는 최소 걸리는 초를 구하는 bfs 함수를 만들었습니다.
- BufferedWriter에 출발지점과 도착지점이 같으면 0 아니면 최소 걸리는 초를 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
- bfs은 day[]와 Queue를 통해 지점을 +1, -1, *2를 탐색하였습니다.
결과 코드
import java.io.*;
import java.util.*;
public class Main{
public static int N,K;
public static int[] day = new int[100001]; //지점별 걸리는 최소 초 저장
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력값 처리하는 BufferedReader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//결과값 출력하는 BufferedWriter
//-------입력값 저장 및 배열 초기화--------
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
if(N==K) //시작 지점과 도착 지점이 같을 경우
bw.write("0");
else {
bfs(); //함수 실행
bw.write(day[K] + "\n"); //도착 지점 최소 걸리는 초 BufferedWriter 저장
}
bw.flush(); //결과 출력
bw.close();
br.close();
}
//--------BFS으로 최소 걸리는 초를 구하는 함수---------
public static void bfs() {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(N);
int count=1;
while(!queue.isEmpty()) {
int size = queue.size();
for(int i=0;i<size;i++) {
int start = queue.poll();
int tempPlus = start + 1; // +1일 때
int tempMinus = start - 1; // -1일 때
int tempMul = start * 2; //*2일 때
if(tempMinus==K || tempMul==K||tempPlus==K) { //목적 지점 도착시
day[K] = count;
return;
}
if(tempPlus<=100000 && day[tempPlus]==0) {
day[tempPlus] = count;
queue.add(tempPlus);
}
if(tempMinus>=0 && day[tempMinus]==0) {
day[tempMinus] = count;
queue.add(tempMinus);
}
if(tempMul<=100000 && day[tempMul]==0) {
day[tempMul] = count;
queue.add(tempMul);
}
}
count++;
}
}
}
'백준' 카테고리의 다른 글
[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)2206번, 벽 부수고 이동하기 (0) | 2022.03.27 |
---|---|
[백준] code.plus(브루트포스-순열,JAVA)6603번, 로또 (0) | 2022.03.27 |
[백준] code.plus(브루트포스-순열,JAVA)10971번, 외판원 순회 2 (0) | 2022.03.26 |
[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)7569번, 토마토 (0) | 2022.03.25 |
[백준] code.plus(브루트포스-순열,JAVA)10819번, 차이를 최대로 (0) | 2022.03.25 |
댓글