𕼧BFSͿ最短経路

質問する

リンク

に答える

1.質問へのアクセス

隣接する4つのセルのうち1つが空の場合は、そのセル

に数値を移動します.
クリーンアップ状態

を作成するには、

の移動が必要である.

最小移動回数

を求めます

2.トラブルシューティングロジック（解法）

つまり.

固定経路のみ、

最低移動速度

は、特定の状態を満たさなければならない.
指定された経路のみで移動して目的地に到達する最短経路の問題であるといえる.
従って、BFSを用いる

注意しなければならないのは

一般的な最短経路の問題とは異なり、移動するたびに地図が変わります.
そのため、移動するたびに地図を更新する必要があります.

ぎじふごう

int ans[3][3] = {{1,2,3},{4,5,6},{7,8,0}} // 정리된 상태 (도착지)
int dist[3][3] // 이동거리
int map[3][3]
queue<pair<int, int>> que
bool success
bool

dx = {0, 1, 0, -1}
dy = {1, 0, -1, 0}

BFS(){
	while(!que.empty){
    	y = que.front.first
        x = que.front.second
        que.pop
        
        // 정리된 상태인지 확인
        success = true
        for(i : 0 ~ 3){
    		for(j : 0 ~ 3){
        		if(ans[i][j] != map[i][j]){
                	success = false
                }
            }
        }
        if(success == true){
        	cout << dist[y][x]
            return
        }
        
        // 이동할 수 없는 상태인지 확인
        status = false
        for(i : 0 ~ 3){
        	nx = x + dx[i]
            ny = y + dy[i]
        	if(map[ny][nx] == 0) status = true
        }
        if(status == false){ // 이동할 수 없는 상태
        	cout << "-1"
            return
        }
        
        // 이동
        for(i : 0 ~ 3){
        	nx = x + dx[i]
            ny = y + dy[i]
        	if(map[ny][nx] != 0) continue // 0이 아닌 곳으로는 이동 불가능
            if(nx < 0 || ny < 0 || nx >= 3 || ny >= 3) continue // map을 벗어날 경우
            if(dist[ny][nx] != 0) continue // 이전에 이동했던 위치로는 이동 불가능
            
            que.push({ny, nx})
            dist[ny][nx] = dist[y][x] + 1
            
            // map 최신화
            tmp = map[y][x]
            map[y][x] = map[ny][nx]
            map[ny][nx] = tmp
        }
        
        
    }
        
    }
}

main(){
	for(i : 0 ~ 3){
    	for(j : 0 ~ 3){
        	cin >> map[i][j]
            if(map[i][j] == 1){
            	que.push({i,j})
            }
        }
    }
    
    BFS()
}

3.時間複雑度分析

O(N^2)

4.問題の重要な部分

これは最も短い経路を探すことに気づきにくい問題である.
移動不可能な状態にあるかどうか、移動するたびに地図の変更が反映されるかどうかを確認する必要があります.