✅ BFS ✅ 최단거리 ✅ queue에 struct 넣기

문제

링크

풀이

1. 문제 접근

2차원에서 탐색을 했던 이전 문제들과 다르게 이번 문제는 3차원에서 탐색을 진행한다.

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

+자료구조 or 알고리즘 선택과 그 이유

이문제는 최단거리를 찾는 문제와 같다. 따라서 BFS를 사용했다.

의사코드

char map[31][31][31]
bool visited[31][31][31]
queue<Pos> que

struct Pos{
	int x, y, z
}

dx[6] = {0, 1, 0, -1, 0, 0}
dy[6] = {1, 0, -1, 0, 0, 0}
dz[6] = {0, 0, 0, 0, 1, -1}

BFS(x, y, z){
	que.push({x, y, z})
    visited[x][y][z] = 0
    
    while(!que.empty){
    	x2 = que.front.x
        y2 = que.front.y
        z2 = que.front.z
        que.pop
        
        if(map[x2][y2][z2] == 'E'){
        	flag = true
        	cout << "Escaped in " << visited[x2][y2][z2] << " minute(s)."
            break;
        }
        
        for(i : 0 ~ 3){
    		nx = x2 + dx[i]
            ny = y2 + dy[i]
            nz = z2 + dz[i]
            
            if(nx < 0 || ny < 0 || nz < 0 || nx >= N || ny >= N || nz >= N) continue
            
            if(map[nx][ny][nz] == '#') continue
            
            que.push({nx,ny,nx})
            visited[nx][ny][nz] = visited[x2][y2][z2] + 1
    	}
    }
    
}

main(){
	cin >> L >> R >> C
    
    for(x : 0 ~ R-1){
    	for(y : 0 ~ C-1){
    		for(z : 0 ~ L-1){
    			cin >> map[x][y][z]
                if(map[x][y][z] == 'S'){
                	sx = x;
                    sy = y;
                    sz = z;
                }
    		}
    	}
    }
    
    BFS(sx, sy, sz)
    
	if(flag == false) cout << "Trapped!"
}

BFS 함수 인자 (x, y, z) 순서를 그대로 넣어도 될지 모르겠음.. 직접 디버깅 해봐야할듯

3. 시간 복잡도 분석

O(N^3)

4. 문제에서 중요한 부분

3차원도 2차원과 동일하게 풀이가 가능하다는거