반응형
이제 곧 싸피데이!!!
싸피데이를 즐기기 전 숨바꼭질3 문제를 풀고 공부 기록 시작한다 ㅠ
1. 출처
왜이리 어려운 것이냐?... 처음 이 문제를 보고, 어떻게 문제를 풀어야할지 감이 잡히지 않았다...
그래서 결국 구글링을 통해 다른 사람들의 코드를 보며 어떻게 문제를 짜야할지 봤던 문제..
https://www.acmicpc.net/board/view/115423
질문 게시판을 보니 이런 질문도 있었는데 dp로 푸려고 했던 나는 엄청 공감이 되었다...
2. 설계
https://moonsbeen.tistory.com/97
내가 참고한 코드는 BFS로 푸신 이 분의 코드이다. 처음 코드를 봤을 때는 잘 이해가 안되었는데, 그림을 그리면서 이해하니 바로 이해가 되었다.
BFS로 풀면서 가장 궁금한 것은 큐에 넣는 대상이다. 큐에 넣는 대상은 현재 위치에서 X2, +1, -1했을 때의 위치이다. 그리고 그 곳을 갔을 때 걸리는 시간도 Node 클래스를 선언하여 넣어주었다.
public Node(int num, int time) {
super();
this.num = num;
this.time = time;
}
그리고 큐에서 하나씩 빼내주면서 위 그림처럼 동생이 있는 위치가 나오면 거리 최소값 min값을 갱신해주면 된다. 때문에 visited로 방문 체크는 필수다. 이미 방문한 위치는 더이상 방문하지 않는다.
3. 전체 코드
package BJ13549;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class 숨바꼭질3 {
static boolean[] visited;
static final int max = 100000;
static int min_result = Integer.MAX_VALUE;
static int N,K;
static class Node{
int num;
int time;//0, 1
public Node(int num, int time) {
super();
this.num = num;
this.time = time;
}
}
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
N = sc.nextInt();//수빈 위치
K = sc.nextInt();//동생 위치
//입력 받기 끝
visited = new boolean[max+1];
bfs();
System.out.println(min_result);
}
public static void bfs() {
Queue<Node> p = new LinkedList<>();
//첫 노드 넣기 수빈이가 있는 위치임
p.add(new Node(N,0));
visited[N] = true;
while(!p.isEmpty()) {
Node cur = p.poll();//현재 위치 및 시간
visited[cur.num] = true;
//어떤 경로로 가던 동생이 있는 위치로 오면 걸린 가장 적은 시간, min값을 체크해준다.
if(cur.num==K) {
min_result=Math.min(min_result, cur.time);
}
//하나 위치에 대해 순간이동, +1 , -1 했을 경우 만족하는지 확인한다.
//갔던 위치는 다시 가지 않게 한다.
//순간이동
if(cur.num*2<=max && !visited[cur.num*2]) {
p.add(new Node(cur.num*2,cur.time));//시간은 0이 지남 순간이동한 것임
}
//+1
if((cur.num+1)<=max && !visited[cur.num+1]) {
p.add(new Node(cur.num+1,cur.time+1));//1초걸림
}
//-1
if((cur.num-1) >= 0 && !visited[cur.num-1]) {
p.add(new Node(cur.num-1,cur.time+1));//1초걸림
}
}
}
}
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[BFS] 백준 2638번 치즈 - JAVA (0) | 2023.05.03 |
---|---|
[그래프] 백준 1068번 트리 - JAVA (0) | 2023.04.26 |
[자료구조] 백준 1620번 나는야 포켓몬 마스터 이다솜 - JAVA (0) | 2023.04.15 |
[Queue/구현] 백준 11866번 요세푸스 문제 0 - JAVA (반복문/큐 2가지 풀이) (0) | 2023.04.15 |
[BFS] 백준 7569번 토마토 - JAVA (3차원을 곁들인 토마토) (2) | 2023.04.14 |