[Baekjoon] 13549_숨바꼭질 3

Gold V

문제(출처: https://www.acmicpc.net/problem/13549)

---

< 숨바꼭질 3>

 

문제 풀이

 

bfs를 활용하여 가장 빠른 시간을 구하였다.

 

 

 - my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _13549_ { // 숨바꼭질 3

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		int n=Integer.parseInt(st.nextToken());
		int k=Integer.parseInt(st.nextToken());
		
		int result=0;
		
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int[] {n, 0});
		HashSet<Integer> set=new HashSet<>();
		set.add(n);
		
		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			if(temp[0]*2<=100000 && !set.contains(temp[0]*2)) {
				if(temp[0]*2 == k) {
					result=temp[1];
					break;
				}
				set.add(temp[0]*2);
				queue.add(new int[] {temp[0]*2, temp[1]});
			}
			if(temp[0]-1>=0 && !set.contains(temp[0]-1)) {
				if(temp[0]-1 == k) {
					result=temp[1]+1;
					break;
				}
				set.add(temp[0]-1);
				queue.add(new int[] {temp[0]-1, temp[1]+1});
			}
			if(temp[0]+1<=100000 && !set.contains(temp[0]+1)) {
				if(temp[0]+1 == k) {
					result=temp[1]+1;
					break;
				}
				set.add(temp[0]+1);
				queue.add(new int[] {temp[0]+1, temp[1]+1});
			}
		}
		System.out.println(result);
	}
}

 

Main

- n과 k 입력

- queue와 HashSet에 초기 위치 저장

- queue가 빌 때까지 반복 : 값을 뽑은 후 0초 후, 1초 후 각 위치를 계산하여 범위 안이며 아직 방문하지 않은 곳이면 각 queue와 HashSet에 추가

- result 출력

---

생각🤔

 

예전에 틀린 후에 다시 도전한 문제! 저번에 마지막 코드가 메모리 초과가 발생하여 이번에는 바로 HashSet을 활용하는 방식으로 코드를 구현하였다. 그럼에도 몇 번이나 틀려 확인해 보니 다 풀어두고 답을 잘못 적어서 틀리고,,, n과 k 값이 같은 경우를 고려하지 않아서 틀렸던 것이었다. 

 

---