백준_1697 숨바꼭질(자바) / BFS & DFS

시간 & 메모리 제한

문제

입력 & 출력

BFS를 이용한 문제풀이

package com.Back;

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 Back_1697 {
	
	static int N,K,ans;
	static int[] visited = new int[100001];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		if(N==K) {
			System.out.println(0);
			System.exit(0);
		}
		
		bfs();
		System.out.println(visited[K]);
	}

	private static void bfs() {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(N);
		while(!q.isEmpty()) {
			int n = q.poll();
			if(n==K)break;
			if(n>0 && visited[n-1]==0) {
				q.add(n-1);
				visited[n-1]=visited[n]+1;
			}
			if(n<100000 && visited[n+1]==0) {
				q.add(n+1);
				visited[n+1] = visited[n]+1;
			}
			if(n*2<=100000 && visited[n*2]==0) {
				q.add(n*2);
				visited[n*2] = visited[n]+1;
			}
		}
	}

}

- 이 문제는 처음에 DP로 시도를 했습니다. 하지만 진행할 때마다 늘어나는 경우의 수를 감당하기 힘들었

고, BFS를 선택했습니다.

 

- n의 범위가 0부터 10만 사이이므로 이 범위 안에서 BFS를 진행하게 코드를 짯습니다.

 

- if문의 첫번째의 경우는 -1을 하는경우

 

- if문의 두번째의 경우는 +1을 하는 경우

 

- if문의 세번째의 경우는 *2를 하는 경우

 

- 이렇게 3가지에 대한 경우를 내가 방문하지 않은 경우 및 범위에서 벗어나지 않는다면 추가하여 진행을

했습니다..

 

- DFS로 풀진 않았지만 시간 복잡도를 보면 시간이 넉넉하기 때문에 DFS로 풀어도 시간이 충분히 남을거라고 생각합니다.