글 읽기 - 2178미로탐색 ㅠㅠ 12%에서 왜 자꾸 틀리죠...?

rlarkdms7081 6년 전 0

ㅠㅠ테케두개는 잘 나오고 다른 반례들도 여러개 해봤느데 왜 틀린지 모르겠습니다ㅠㅠ

#include <iostream>
#include <cstring>
#include <cstdio>
void dfs(int r,int c,int a);
using namespace std;
int n,m,res;
int map[101][101];
int visit[101][101];
int main(){
    ios_base::sync_with_stdio(false);
    cin >>n>>m;
    memset(map,0,sizeof(map));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d",&map[i][j]);
        }
    }
    visit[0][0]=1;
    res = 99999;
    dfs(0,0,1);
    
    cout<<res;
}
void dfs(int r,int c,int a){
    if(r==n-1 && c==m-1){
        res = a<res?a:res;            // 최단인지 확인 후 res에 넣음 
        return;
    }    
    for(int i=-1; i<=1; i++)            //현재 점에서 인접하고, 방문하지 않은 점으로 dfs
        for(int j=-1; j<=1; j++)
            if(i*j==0 && r+i>=0 && r+i<n && c+j>=0 && c+j<m && map[r+i][c+j] == 1 && visit[r+i][c+j] == 0){
                visit[r+i][c+j] = 1;
                dfs(r+i,c+j,a+1);
                visit[r+i][c+j] = 0;
            }
    return;
}

djm03178 6년 전 1

ios_base::sync_with_stdio(false); 를 한 뒤에는 cin과 scanf를 섞어쓰면 안 됩니다.

rlarkdms7081 6년 전 0

아아 감사합니다!!!!

djm03178 6년 전 1

참고로 최단거리 문제는 DFS로 하면 안 됩니다. 간단한 예로,

100 100

111111111111...

...

과 같을 때 모든 경로를 탐색하는 데에 얼마나 걸릴지 생각해보세요.

rlarkdms7081 6년 전 0

헐 마침 ㅠㅠㅠㅠㅠ 그래서 BFS로 새로 짰어여...ㅠㅠㅠ 조언 감사합니당!!

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

문제

문제

출처

ICPC

2178미로탐색 ㅠㅠ 12%에서 왜 자꾸 틀리죠...?

rlarkdms7081 6년 전 0

djm03178 6년 전 1

rlarkdms7081 6년 전 0

djm03178 6년 전 1

rlarkdms7081 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말