백준_숨바꼭질_1697

//알고리즘

1. bfs 탐색

 -> 1차원 배열을 만들고 시작점에서 도착점까지 탐색

 -> 방문배열을 사용하여 한번 갔던곳은 다시 못가게 만듦

 

매일 2차원 배열에서의 bfs만 풀다가 1차원 배열로 bfs탐색을 풀어보니까 새로웠다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 숨바꼭질_1697 {
	static int T, K, arr[];
	static boolean v[];
	static int[] dr = { -1, 1, 2 };

	static class Point {

		int r, cnt;

		public Point(int r, int cnt) {
			super();
			this.r = r;
			this.cnt = cnt;
		}

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		T = sc.nextInt();
		K = sc.nextInt();

		arr = new int[100001];
		v = new boolean[100001];

		bfs(T);
	}

	private static void bfs(int t) {
		Queue<Point> q = new LinkedList<Point>();
		v[t] = true;
		q.add(new Point(t, 0));
		
		Point p = null;
		while(!q.isEmpty()) {
			p  = q.poll();
			
			if(p.r == K) {
				System.out.println(p.cnt);
				return;
			}
			
			int nr;
			for (int d = 0; d < 3; d++) {
				if(d==2) {
					nr = p.r* dr[d];
				}else {
					nr = p.r + dr[d];
				}
				
				if(nr< 0  || nr >= 100001 || v[nr]) continue;
				
				v[nr] = true;
				q.add(new Point(nr, p.cnt+1));
				
			}
			
		}
		
	}

}