✅ BFS ✅ 최단거리

문제

링크

풀이

1. 문제 접근

상근이가 한칸 이동할 때마다 불도 한칸씩 이동하여 번지므로 상근이가 갈 수 있는 길이 매번 바뀌는 문제이다.

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

BFS를 사용할건데 상근이가 이동하는 것처럼 불도 이동하므로 queue를 두개 사용하여 각각이 이동하는 하게 풀었다.

의사코드

// 아래 코드를 데스트 케이스만큼 반복

string map[1001]
queue<pair<int, int>> fire_que, people_que
int dist[1001][1001]

dx[4] = {1, 0, -1, 0}
dy[4] = {0, 1, 0, -1}

BFS(Y, X){
	visited[Y][X] = true
    people_que.push({Y, X})
    dist[Y][X] = 1
    
    while(!people_que.emtpy){
    	// 1. 불 이동
        while(fire_que.size --){ // 불은 동서남북으로 한번씩 모두 이동해줘야 함
        	x = fire_que.front.second
            y = fire_que.front.first
            fire_que.pop
            
            for(i : 0 ~ 3){
            	nx = x + dx[i]
                ny = y + dy[i]
                
                if(nx < 0 || ny < 0 || nx >= w || ny >= h) {
                    flag = true
                    return
                }
                if(map[ny][nx] == '#' || map[ny][nx] == '*') continue
                
                map[ny][nx] = '*'
                fire_que.push({ny, nx})
            }
        }
        
        // 2. 사람 이동
        x = people_que.front.second
        y = people_que.front.first
        people_que.pop
            
        for(i : 0 ~ 3){
            nx = x + dx[i]
            ny = y + dy[i]
                
            if(nx < 0 || ny < 0 || nx >= w || ny >= h) continue
            if(map[ny][nx] == '#' || map[ny][nx] == '*') continue
            
            map[ny][nx] = '#' // 이동한 위치는 벽으로 바꾸어 이동할 수 없게 만듦
            people_que.push({ny, nx})
            dist[ny][nx]  = dist[y][x] + 1
    }
}

main(){
	cin >> w >> h
    for(i : 0 ~ h-1){
    	cin >> map[i]
    }
    
    for(i : 0 ~ h-1){
    	for(j : 0 ~ w-1){
        	if(map[i][j] == '@') si = i, sj = j
            if(map[i][j] == '*') fire_que.push({i,j})
        }
    }
    
    BFS(si, sj)
    
    if(flag == false) cout << "IMPOSSIBLE" 
    else cout << dist[ny][nx]
}

3. 시간 복잡도 분석

O(N^2)

4. 문제에서 중요한 부분

일반적인 문제와 다르게 이동하는 주체가 2개이므로 queue를 2개 사용해야 하는 특이한 문제였고
2개의 주체가 서로의 경로에 영향을 미치므로 이동할 때 분기처리를 또 해줘야 했다.

또한 맨끝 벽에 도달하면 탈출한 것이므로 반복문을 더 돌 필요없이 거리를 출력하고 종료.