글 읽기 - 고수님들 버스 배달점..

camille 7년 전 0

다들 dp나 bfs를 쓰셨는데..

저는 dfs로도 충분히 가능 할 거 같아서 dfs로 짰습니다....

drt라는 변수로 현재 왔던 방향 정보를 전달하고,

sum이라는 변수로 현재까지 찾은 'C'의 갯수를 파라미터로 넘기면서

csum과 sum이 같으면 c를 모두 다 찾은거라고 생각하고

그때부터 리턴해주었어요..

제가 만든 예제는 다 됐지만 안되는 이유를 모르겠습니다..

고수님들 알려주세요..

#include <iostream>

using namespace std;

int n,m,sy,sx,csum;
char adj[51][51];
int dy[]={0,0,1,-1}, dx[]={1,-1,0,0};
int visited[51][51];

int foo(int y, int x, int drt, int sum){
    if(sum==csum) return 0;
    visited[y][x]=true;
    
    int ret=1e9;
    for(int i=0; i<4; i++){
        int ky=dy[i]+y, kx=dx[i]+x;
        if(i==drt || visited[ky][kx] || ky<0 || kx<0 || ky>n-1 || kx>m-1 || adj[ky][kx]=='#') continue;
        if(adj[ky][kx]=='C') ret=min(ret, foo(ky, kx, i, sum+1));
        else ret=min(ret, foo(ky, kx, i, sum));
    }
    visited[y][x]=false;
    return ++ret;
}

int main(){
    cin>>n>>m;
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) {
        cin>>adj[i][j];
        if(adj[i][j]=='S') sy=i, sx=j;
        if(adj[i][j]=='C') ++csum;
    }

    int ret = foo(sy, sx, -1, 0);
    if(ret==1e9+1) cout<<-1;
    else cout<<ret;
}

algoshipda 7년 전 2

2 2
SC
C#

3을 출력해야 합니다

camille 7년 전 2

왔던 곳을 다시 갈 수 있었네요..

갖고싶습니다 그 실력

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

문제

문제

출처

ICPC

고수님들 버스 배달점..

camille 7년 전 0

algoshipda 7년 전 2

camille 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말