글 읽기 - DFS로 이 문제를 해결할 수 있나요?

akrso06197 4년 전 0

문제의 분류가

로 되어잇어서 DFS로 계속 시도를 하였는데 질문 검색과 구글에서 찾아보아도 코드를 찾아볼 수 없어서 이렇게 질문을 올립니다.

아래는 제 소스코드이고, 어떻게 하면 DFS로 이 문제를 해결할 수 있을지 질문해봅니다!

#include <iostream>
#include <string>
using namespace std;
string map[31][31];
int l,r,c;
int tim[31][31][31];
struct node {
    int x,y,z;
};
node start,en;
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};
void dfs(int x, int y, int z){
    if(map[x][y][z]=='E') {
        return;
    } else {
        for(int i=0; i<6; i++) {
            int curi = x+dx[i];
            int curj = y+dy[i];
            int curk = z+dz[i];
            if(curi>=0 && curi<l && curj>=0 && curj<r && curk>=0 && curk<c && (map[curi][curj][curk]=='E' || map[curi][curj][curk]=='.') && tim[curi][curj][curk]==0) {
                tim[curi][curj][curk]=tim[x][y][z]+1;
                dfs(curi, curj, curk);
            }
        }
    }
}
int main(){
    while(true) {
        cin>>l>>r>>c;
        if(l==0 && r==0 && c==0)
            break;
        for(int i=0; i<l; i++) {
            for(int j=0; j<r; j++) {
                for(int k=0; k<c; k++)
                    tim[i][j][k]=0;
            }
        }
        for(int i=0; i<l; i++) {
            for(int j=0; j<r; j++) {
                cin>>map[i][j];
                for(int k=0; k<map[i][j].size(); k++) {
                    if(map[i][j][k]=='S') {
                        start.x =i; start.y=j; start.z=k;
                    } else if(map[i][j][k]=='E') {
                        en.x =i; en.y=j; en.z=k;
                    }
                }
            }
        }
        dfs(start.x,start.y,start.z);
        if(tim[en.x][en.y][en.z]!=0) {
            cout<<"Escaped in "<<tim[en.x][en.y][en.z]<<" minute(s)."<<endl;
        } else {
            cout<<"Trapped!"<<endl;
        }
    }
}

jh05013 4년 전 1

BOJ에 있는 문제 분류는 별로 믿음직하지 않습니다. 최단거리는 무조건 BFS로 찾아야 합니다.

jh05013 4년 전 0

물론 다익스트라 알고리즘으로 찾을 수도 있지만, 간선마다 가중치가 다른 그래프가 아니니 굳이 쓸 이유는 없습니다.

akrso06197 4년 전 0

답글달아 주셔서 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DFS로 이 문제를 해결할 수 있나요?

akrso06197 4년 전 0

jh05013 4년 전 1

jh05013 4년 전 0

akrso06197 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말