글 읽기 - dfs 질문 드립니다

rlathdwls2 4년 전 0

안녕하세요?

깊이우선 탐색 알고리즘을 활용하여 문제에 접근했습니다.

탐색 과정에서 방문한 character를 set에 저장해나갔습니다.

만약 set에 이미 추가된 알파벳이라면 탐색을 더이상 진행 하지 않도록 했습니다.

탐색 과정에서 재귀 트리가 생겨납니다.

재귀 트리 구간 마다 set은 고정되어 있기 때문에

방문 표시를 하지 않고 문제를 풀어볼 수 있을거라 생각했지만

바로 틀렸습니다를 맞았습니다.

c++ 에선 set이 call by reference로 넘어 가는 것인지,

제가 작성한 코드에 있는 결함은 어떤것이 있는지 조언을 구하고 싶습니다.

감사합니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <set>

#define MAX 21

using namespace std;

int dy[4] {-1, 1, 0, 0};
int dx[4] {0, 0, -1, 1};

char table[MAX][MAX];
int r, c;
int ret;

void dfs(int y, int x, int cnt, set<char> s){
    int ny, nx;
    
    ret= max(ret, cnt);
    
    for(int i = 0 ; i < 4; i++){
        ny = y + dy[i];
        nx = x + dx[i];
        
        if(nx<0 || nx >= c)
            continue;
        if(ny<0 || ny >= r)
            continue;
        if(s.count(table[ny][nx])>0)
            continue;
        
        s.insert(table[ny][nx]);
        dfs(ny, nx, cnt+1, s);
        
    }
}


void build(){
    ret = 0;
    cin>>r>>c;
    for(int y = 0 ; y < r ; y++){
        for(int x = 0 ; x < c ; x++){
            cin>>table[y][x];
        }
    }

}

int main(int argc, const char * argv[]) {
    build();
    set<char> s;
    s.insert(table[0][0]);
    dfs(0, 0, 1, s);
    cout<<ret<<endl;
    return 0;
}

hunni10 4년 전 0

줄 33번에서 s.insert()를 하고 재귀호출을 한 뒤 다음 반복에서 s는 그 호출에서 입력으로 들어온 s가 아니라 직전 반복에 의하여 변화된 s값입니다.

다음과 같이 해보거나, 다른 좋은 방법이 있을 것 같습니다.

        set<char> ns = s;
		ns.insert(table[ny][nx]);

hunni10 4년 전 0

*수정

        set<char> ns = s;
		ns.insert(table[ny][nx]);
		dfs(ny, nx, cnt + 1, ns);    //s -> ns

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

문제

문제

출처

ICPC

dfs 질문 드립니다

rlathdwls2 4년 전 0

hunni10 4년 전 0

hunni10 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말