✅ BFS ✅ 최단거리

문제

링크

풀이

1. 문제 접근

• 최소거리 문제

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

최소거리 문제이므로 BFS 사용

• 시작점이 여러개일 수도 있으므로 처음에 1인 지점을 queue에 모두 넣어놓고 BFS 시작
• 인접한 토마토로 이동하면서 체크(1) 해주고 queue가 끝난뒤 아직 0인 곳이 있으면 -1 출력
• 처음 저장될 때부터 모든 토마토가 있어 있는 상태이면 0 출력
• 끝나는 지점이 하나로 정해져 있지 않기 때문에 거리를 저장하면서 최종 출력값 day도 최신화 해줘야 한다.

의사코드

int map[1001][1001]
int dist[1001][1001]
queue<pair<int, int>> que

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

BFS(){

    while(!que.empty){
    	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 >= M || ny >= N) continue
            if(map[ny][nx] == 1 || map[ny][nx] == -1) continue // 이미 방문했거나 토마토가 없는 지점은 이동 불가
            
            map[ny][nx] = 1
            dist[ny][nx] = dist[Y][X] + 1
            day = dist[ny][nx] // 끝나는 지점이 하나로 정해져 있지 않기 때문에 최종값 day도 최신화 해줘야 한다.
        }
    }
}

main(){
	cin >> M >> N
    for(i : 0 ~ N-1){
    	for(j : 0 ~ M-1){
        	cin >> map[i][j]
            if(map[i][j] == 1) que.push({i,j})
        }
    }
    
    BFS()
    
    for(i : 0 ~ N-1){
    	for(j : 0 ~ M-1){
        	if(map[i][j] == 0){
            	cout << -1
                return
            }
        }
    }
    
    cout << day
}

3. 시간 복잡도 분석

O(N^2)

4. 문제에서 중요한 부분

시작점이 여러개라는 것과 끝나는 지점이 정해져 있지 않다는 것이 특이했던 문제