✅ BFS ✅ 최단거리

문제

링크

풀이

1. 문제 접근

방금 전에 풀었던 5427 불 과 동일한 문제이다.

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

고슴도치 뿐만 아니라 물도 이동하므로 queue를 두개 사용하여 BFS로 풀었다.

의사코드

string map[51]
queue<pair<int, int>> que
queue<pair<int, int>> que_water
dist[51][51]

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

BFS(Y, X){
	dist[Y][X] = 1
    que.push({Y,X})
    	
    while(!que.empty){
    	// 1. 물 먼저 이동
        while(que_water--){ // 고슴도치가 한번 이동할때 물은 동서남북 한번만 이동 가능하므로 que_water에 있는 만큼만 수행
        	x = que_water.front.second()
            y = que_water.front.first()
            que_water.pop
            
            for(i : 0 ~ 3){
            	nx = x + dx[i]
                ny = y + dy[i]
                
                if(nx < 0 || ny < 0 || nx >= C || ny >= R) continue
                if(map[ny][nx] != '.') continue
                
                map[ny][nx] = '*'
                que_water.push({ny, nx})
            }
        }
        
        // 2. 고슴도치 이동
        x = que.front.second()
        y = que.front.first()
        que.pop

        for(i : 0 ~ 3){
            nx = x + dx[i]
            ny = y + dy[i]

            if(nx < 0 || ny < 0 || nx >= C || ny >= R) continue
            if(map[ny][nx] != '.') continue
            if(map[ny][nx] != 'D'){
                flag = true
                return
            }
            
            map[ny][nx] = 'X'
            que_water.push({ny, nx})
            dist[ny][nx] = dist[y][x] + 1
    }
}

main(){
	cin >> R >> C
    for(i : 0 ~ R) cin >> map[i]
    
    for(i : 0 ~ R){
    	for(j : 0 ~ C){
    		if(map[i][j] == 'S'){
            	si = i
                sj = j
            }
            if(map[i][j] == '*'){
            	que_water({i,j})
            }
    	}
    }
    
    BFS(si, sj)
    
    if(flag == true) cout << dist[ny][nx]
    else cout << KAKTUS
}

3. 시간 복잡도 분석

O(N^2)

4. 문제에서 중요한 부분

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

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