[BOJ] 1697 숨바꼭질.java
1. 문제
2. 코드
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 Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//수빈이와 동생의 위치
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
boolean[] visited = new boolean[100001];
//bfs위한 큐 생성
Queue<Integer> queue = new LinkedList<Integer>();
//첫 원소 입력 및 방문 처리
queue.add(N);
visited[N] = true;
int count = 0; //이동횟수
while(!queue.isEmpty()){
int size = queue.size();
//해당 이동횟수의 갯수만큼
while(size!=0){
int curr = queue.poll();
size--;
//위치와 동생의 위치가 같아지면 출력하고 정지
if(curr == M){
System.out.println(count);
return;
}
//위치는 -1,+1,*2가 있다.
int temp1 = curr-1;
int temp2 = curr+1;
int temp3 = curr*2;
//범위 벗어나지 않고 방문 안했을경우에만 큐에 넣어준다.
if(temp1>=0 && !visited[temp1]){
queue.add(temp1);
visited[temp1] = true;
}
if(temp2<=100000 && !visited[temp2]){
queue.add(temp2);
visited[temp2] = true;
}
if(temp3<=100000 && !visited[temp3]){
queue.add(temp3);
visited[temp3] = true;
}
}
//한 사이클 끝나면 다음 횟수로
count++;
}
br.close();
}
}
3.Review
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 Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//수빈이와 동생의 위치
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
boolean[] visited = new boolean[100001];
//bfs위한 큐 생성
Queue<Integer> queue = new LinkedList<Integer>();
//첫 원소 입력 및 방문 처리
queue.add(N);
visited[N] = true;
int count = 0; //이동횟수
while(!queue.isEmpty()){
int size = queue.size();
//해당 이동횟수의 갯수만큼
while(size!=0){
int curr = queue.poll();
size--;
//위치와 동생의 위치가 같아지면 출력하고 정지
if(curr == M){
System.out.println(count);
return;
}
//위치는 -1,+1,*2가 있다.
int temp1 = curr-1;
int temp2 = curr+1;
int temp3 = curr*2;
//범위 벗어나지 않고 방문 안했을경우에만 큐에 넣어준다.
if(temp1>=0 && !visited[temp1]){
queue.add(temp1);
visited[temp1] = true;
}
if(temp2<=100000 && !visited[temp2]){
queue.add(temp2);
visited[temp2] = true;
}
if(temp3<=100000 && !visited[temp3]){
queue.add(temp3);
visited[temp3] = true;
}
}
//한 사이클 끝나면 다음 횟수로
count++;
}
br.close();
}
}
BFS와 메모이제이션을 사용하여서 풀었다. 전형적이었다.
Author And Source
이 문제에 관하여([BOJ] 1697 숨바꼭질.java), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hakka_ame/BOJ저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)