✅ BFS ✅ 최단경로

문제

링크

풀이

1. 문제 접근

수빈이가 이동할 수 있는 경우

• -1
• +1
• *2

2. 문제 해결 로직 (풀이법)

동생을 찾는 가장 빠른 시간은 최소경로를 찾는 문제와 같으므로 BFS로 풀었다

의사코드

int map[100001]
queue<int> que
int dist[100001]

dx[3] = {-1, 1, 2}

BFS(){
	while(!que.empty){
    	x = que.front
        que.pop
        
        for(i : 0 ~ 2){
        	if(i == 2) nx = 2*x
            else nx = x + dx[i]
            
            if(nx < 0 || nx > 100000) continue
            
            que.push(nx)
            dist[nx] = dist[x] + 1
            
            if(nx == K){
            	cout << dist[nx]
                return
            }
        }
    }
}

main(){
	cin >> N >> K
    
    map[N] = 1
    que.push(N)
    
    BFS()

}

3. 시간 복잡도 분석

O(N^2)

4. 문제에서 중요한 부분