글 읽기 - DFS로 풀었는데 어디가 틀렸을까요?ㅜ

cho31250 6년 전 0

고수님들 부탁드립니다ㅠ

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

typedef struct MAZE{
    char val;
}Maze;

int dir[4][2] = {
    {0,1}, {1,0}, {-1,0},{0,-1}
};

Maze maze[25][25];
int visited[25][25];

int ans = 0;
int n,m;

void DFS(int x, int y, vector<char> &v,int cnt){
    
    for(int k=0;k<4;k++){
        int tempX = x + dir[k][0];
        int tempY = y + dir[k][1];
        
        if(tempX<0||tempX>=n||tempY<0 || tempY>=m) continue;
        if(visited[tempX][tempY]==1) continue;
        
        int len = (int)v.size();
        int chk = 0;
        for(int i=0;i<len;i++){
            if(v[i] == maze[tempX][tempY].val){
                chk = 1;
                break;
            }
        }
        if(chk ==1) continue;
        cnt++;
        visited[tempX][tempY] = 1;
        if(ans<cnt) ans = cnt;
        v.push_back(maze[tempX][tempY].val);
        DFS(tempX,tempY,v,cnt);
        cnt--;
        //visited[tempX][tempY] = 0;
        v.pop_back();
    }
}

int main(void) {
    
    cin>>n>>m;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>maze[i][j].val;
        }
    }
    
    vector<char> v;
    v.push_back(maze[0][0].val);
    visited[0][0] = 1;
    DFS(0,0,v,1);
    cout<<ans<<endl;
}

sgchoi5 6년 전 1

보통 DFS 는 진입했을 때에 visited 가 체크가 되고, 그 자리를 기준으로 네 방향 호출한 다음에는

return 이 되는데, 이 때에 visited 가 다시 꺼져야 다음에 해당 알파벳이 또 사용이 됩니다.

CHCI 문제는 참고자료가 많으니 TC 받아서 해보셔요..

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

DFS로 풀었는데 어디가 틀렸을까요?ㅜ

cho31250 6년 전 0

sgchoi5 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말