[Java] 1697번 : 숨바꼭질
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
BFS로 푸는건 알았는데, 어떻게 풀어야할지를 몰라가지고, 사실 답을 보고 이해하는 방식으로 풀었다! 누군진 몰라도 고마워요
https://velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%801697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88
[Algorithm] 백준_1697 숨바꼭질 JAVA
수빈이의 위치가 N(0 ≤ N ≤ 100,000), 동생은 K(0 ≤ K ≤ 100,000)에 위치하고 있다. 수빈이는 자신의 위치에서 N+1, N-1, N\*2 만큼 이동할 수 있는데, 이때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간
velog.io
주요 코드는 이 부분이다!!
public static void bfs(int n) {
q = new LinkedList<>();
q.add(n);
visited[n]=1;
while(!q.isEmpty()) {
int x = q.poll();
for(int i=0;i<3;i++) {
int next;
if(i==0) {
next = x-1;
}else if(i==1) {
next = x+1;
}else {
next = 2*x;
}
if(next==k) {
System.out.println(visited[x]);
return;
}
if(next>=0 && next<100004 && visited[next]==0) { // 방문 하지 않았 다면
q.add(next); // next 를 큐에 넣고
visited[next] = visited[x]+1;
}
}
}
}
처음에 큐에 넣고, next 를 통해 양옆, 그리고 2배를 뛰는거까진 할 수 있었지만, 아래 부분에 대해서 고민했었다!
if(next==k) {
System.out.println(visited[x]);
return;
}
if(next>=0 && next<100004 && visited[next]==0) { // 방문 하지 않았 다면
q.add(next); // next 를 큐에 넣고
visited[next] = visited[x]+1;
}
그래서 직접 그려봤다,,,! 엉망진창 쓰레기같이 그리긴 했어도 나는 이해했다,,,
visited[x]는 현재 내 위치에서의 시간을 담는 것이고, visited[next] 는 다음 시간이다.
그리고 next 는 이동한 거리이며, x는 현재 위치이다!
하나 더 주의해야할 점은 이 부분이다. 해당 범위를 문제에서 제시한 것 처럼 딱 맞게 100000을 한다면 인덱스 문제가 생긴다.
static int visited[] = new int[100004];
저번 알고리즘 강의를 볼때, 4정도 더 넓게 해주는 것이 좋다고 해서 늘려주니까 해결됐다!
그리고 메인에서 이런식으로 n이랑 k랑 같을 때 0을 출력해줘야 통과된다!
if(n==k) {
System.out.println(0);
}else {
bfs(n);
}
[전체코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, k;
static Queue<Integer> q;
static int visited[] = new int[100004];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
if(n==k) {
System.out.println(0);
}else {
bfs(n);
}
}
public static void bfs(int n) {
q = new LinkedList<>();
q.add(n);
visited[n]=1;
while(!q.isEmpty()) {
int x = q.poll();
for(int i=0;i<3;i++) {
int next;
if(i==0) {
next = x-1;
}else if(i==1) {
next = x+1;
}else {
next = 2*x;
}
if(next==k) {
System.out.println(visited[x]);
return;
}
if(next>=0 && next<100004 && visited[next]==0) { // 방문 하지 않았 다면
q.add(next); // next 를 큐에 넣고
visited[next] = visited[x]+1;
}
}
}
}
}