문제
- 각 칸은 금으로 채워져있거나 비어있음
- 한번에 한칸 이동할 수 있고 동서남북상하로 움직일 수 있음
- 바깥면은 모두 금이라 탈출할 수 없음
- L: 층수, R: 행 , C: 열
- 1-30까지만 있음
- 막혀있는 칸: #
- 비어있는 칸: .
- 시작지점: S ,탈출 출구: E
- 입력의 끝은 L, R, C가 모두 0
- 시작지점, 출구는 항상 한개
풀이
BFS 정석 풀이대로 풀었다
1. 빌딩의 상태를 입력받을 board와 시작점에서부터 해당 칸까지의 거리를 저장할 dist 배열을 만든다.
2. 빌딩의 상태를 입력받아 board에 저장한다.
3. 각 빌딩의 칸을 0,0,0인 S에서부터 시작하여 각 칸의 상하좌우앞뒤의 상태를 확인한다.
4. 여기에서 상태란 1) 벽 여부 2) 방문여부 두가지가 된다.
5. 1) 벽이 아니고 2) 방문하지 않은 칸이면 큐에 넣고 해당 칸의 방문거리를 현재 칸의 거리 +1 로 변경하여 거리를 저장한다.
6. 모든 칸을 다 돌고 나면, 해당 빌딩을 탈출하는데 걸린 최단 시간을 출력한다.
- 최단 시간은 탈출구 E가 적힌 칸의 dist가 된다. 따라서 dist[i-1][j-1][k-1]의 정수가 최단시간이 된다.
- 만약 dist[i-1][j-1][k-1]안에 적힌 수가 0이면 해당 칸을 방문하지 못했다는 뜻이므로 trapped를 출력한다.
풀이 1 - 33%에서 틀린 코드
#include <bits/stdc++.h>
using namespace std;
int L, R, C;
int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int main (void){
ios::sync_with_stdio(0);
cin.tie(0);
int flag =0; //0: 탈출 불가능, 1: 탈출 가능
while(1){
char board[31][31][31];
int dist[31][31][31];
cin >> L>>R>>C;
if(L==0&&R==0&&C==0) break; //셋다 0이면 테스트케이스 끝
//입력받기
for(int i=0; i<L; i++){
for(int j=0; j<R; j++){
for(int k=0; k<C; k++){
cin >> board[i][j][k];
}
}
cout << "\n";
}
//돌면서 확인
for(int i=0; i<L; i++){
for(int j=0; j<R; j++){
for(int k=0; k<C; k++){
//벽이거나 방문했으면 pass
if(board[i][j][k]=='#'|| dist[i][j][k]>0) continue;
//첫 원소 넣기
queue<tuple<int, int, int>> Q;
Q.push(make_tuple(i,j,k));
dist[i][j][k]=1;//처음 지점 거리를 1로 설정
while(!Q.empty()){
auto current = Q.front();
Q.pop();
//상하좌우위아래 확인
for(int dir=0; dir<6; dir++){
int nx = get<0>(current)+dx[dir];
int ny = get<1>(current)+dy[dir];
int nz = get<2>(current)+dz[dir];
//범위 확인
if(nx<0||ny<0||nz<0||nx>30||ny>30||nz>30) continue;
//방문했거나 벽이면 패스
if(dist[nx][ny][nz]>0||board[nx][ny][nz]=='#') continue;
//둘다 아니면 큐에 푸시해서 방문 리스트에 추가
Q.push(make_tuple(nx, ny, nz));
dist[nx][ny][nz] = dist[get<0>(current)][get<1>(current)][get<2>(current)]+1;
}
}
}
}
}
//돌고나서 확인
if(dist[L-1][R-1][C-1]==0){
cout<< "Trapped!\n";
}
else cout<< "Escaped in "<< dist[L-1][R-1][C-1]-1<<" minute(s).";
//빌딩, 거리 초기화
// fill(board[0], board[0]+29, 0);
// fill(dist[0], dist[0]+29, 0);
}
return 0;
}
왜 33%에서 틀릴까?
1) 출력 오류 -> 아님
- 출력 오류일 줄 알고 board를 입력받는 부분에서 \n를 출력하는 부분을 빼줬다.
- 아니었음
2) 범위 확인 오류 -> 아닌듯
우선 테스트 케이스는 잘 맞는다.. 출력 오류도 아니고..
범위 확인을 할 때 0보다 작거나 30보다 크면 continue를 하게 해뒀다.
그런데 생각해보니 건물은 30칸까지만 사용할 수 있다. 조건에 L, R, C가 1부터 30까지만 가능하다. 즉 배열에서 인덱스 0부터 29까지만 사 용한다는 것이다. 그러면 다음 인덱스가 30에 접근하려고 하면 안된다.
왜냐, 그곳은 없는 인덱스이니깐!!
따라서 nx>30을 nx>=30으로 변경해줬다.
다시 제출하니.. 여전히 33%에서 틀린다.
3) 확인하는 칸의 범위 -> 아님
for문을 3번 돌려서 각 칸에 접근했었는데 모든 칸의 거리를 구하는 것이 아니라 단순히 마지막 칸에 도달하는데 얼마의 시간이 드는지만을 구하는 문제이기 때문에 for문을 3번 돌릴 필요 없이 시작 지점만 큐에 넣고 큐가 빌때까지만 돌려주면 된다.
시간복잡도가 월등히 줄어듦
왜 틀렷을까..................
3)까지 수정한 풀이
#include <bits/stdc++.h>
using namespace std;
int L, R, C;
int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int main (void){
ios::sync_with_stdio(0);
cin.tie(0);
while(1){
//테스트케이스를 돌떄마다 초기화
char board[31][31][31];
int dist[31][31][31] ={0};
cin >> L>>R>>C;
if(L==0&&R==0&&C==0) {
// cout << "is breaked\n";
break; return 0;
} //셋다 0이면 테스트케이스 끝
//입력받기
for(int i=0; i<L; i++){
for(int j=0; j<R; j++){
for(int k=0; k<C; k++){
cin >> board[i][j][k];
}
}
//cin << "\n"; //각층에는 빈줄 존재
}
//첫 원소 넣기
queue<tuple<int, int, int>> Q;
Q.push(make_tuple(0,0,0));
dist[0][0][0]=1;//처음 지점 거리를 1로 설정
while(!Q.empty()){
auto current = Q.front();
Q.pop();
//상하좌우위아래 확인
for(int dir=0; dir<6; dir++){
int nx = get<0>(current)+dx[dir];
int ny = get<1>(current)+dy[dir];
int nz = get<2>(current)+dz[dir];
//범위 확인
if(nx<0||ny<0||nz<0||nx>=L||ny>=R||nz>=C) continue;
//방문했거나 막혀있는 칸이면 패스
if(dist[nx][ny][nz]>0||board[nx][ny][nz]=='#') continue;
//둘다 아니면 큐에 푸시해서 방문 리스트에 추가
Q.push(make_tuple(nx, ny, nz));
dist[nx][ny][nz] = dist[get<0>(current)][get<1>(current)][get<2>(current)]+1;
}
}
//돌고나서 확인
if(dist[L-1][R-1][C-1]==0){
cout<< "Trapped!\n";
}
else cout<< "Escaped in "<< dist[L-1][R-1][C-1]-1<<" minute(s).\n";
}
return 0;
}
33%에서 틀린 이유!
시작지점이 항상 0,0이 아니다!!!
문제에 명시되어있는데 테스트케이스를 보고 간과했다.. 당연히 0,0부터 시작하는줄..
