✅ BFS ✅ 최단경로

문제

링크

풀이

1. 문제 접근

• F : 총 층수
• G : 스타트링크가 있는 곳의 위치
• S : 강호가 지금 있는 곳
• U : 위로 U층을 가는 버튼
• D : 아래로 D층을 가는 버튼

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

최단 경로를 구하는 문제이므로 BFS 사용

보통 문제들와 다르게 일차원 map (-> array)이라 생각하고 풀 수 있다.

의사코드

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

BFS(){
	while(!que.empty){
    	x = que.front
        que.pop
        
        for(i : 0 ~ 1){
        	nx = x + dx[i]
            
            if(nx < 1 || nx > F) continue
            if(map[nx] == 1) continue
            
         	dist[nx] = dist[x] + 1
            que.push(nx)
            map[nx] = 1
            
            if(nx == G){
            	cout << dist[nx]
                flag = true
                return
            }
        }
    }
}

main(){
	cin >> F >> S >> G >> U >> D
    dx = {U, -D}
    
    map[S] = 1
    que.push(S)
    
    BFS()
    
    if(flag == false) cout << "use the stairs"
}

3. 시간 복잡도 분석

O(N^2)

4. 문제에서 중요한 부분

map이 일차원이라는 것 말고는 특별한게 없었음 (이차원보다 간단한데 왜 골드인지 모르겠..)