BOJ_1697_숨바꼭질

1.

구분: 그래프 이론, 그래프 탐색, BFS

언어: Java

전략

• 1. BFS에서 탐색을 하듯 한다 - 큐 사용
• 2. 주로 4방 탐색인데 위치 이동이 3가지 가능함을 생각

 

---

2. 코드

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

public class Main {
	static class Node{
		int pos, time;
		Node(int pos, int time){
			this.pos = pos;
			this.time = time;
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		boolean[] road = new boolean[100001];
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(n,0));
		road[n] = true; 
		
		int[] dx = {1,-1,2};
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			int x = node.pos;
			int t = node.time;
			
			//도착했어
			if(x==k) {
				System.out.println(t);
				return;
				
			}
			int nx = 0;
			for(int d = 0; d<3; d++) {
				if(d==2) {
					nx = x * dx[d];
				}
				else {
					nx = x + dx[d];
				}
				
				if(nx<0 || nx>=100001) continue;
				if(road[nx])continue;
				
				q.offer(new Node(nx, t+1));
				road[nx] = true;
				
			}
			//새로운거 만들기
			//x+1, x-1, 2*x
			//범위 체크
			//방문여부 체크
			//road에 체크하기
			
			
		}
		
	
		
	}//main
	

	
}

 

---

3.

처음에는 방향을 못 잡고, 고민을 많이 했는데 BFS를 그래도 이용하면 매우 간단한 문제이다.