글 읽기 - 16929 dfs) 제 로직에 해결방법이 없을까요 도와주세요 ㅜㅜ (설명있음)

qotmd01 2년 전 0

1. 인접한 같은문자끼리 dfs의 경우의 수를 구합니다.

2. 그 경우의 수 중 길이가 4이상인 것들중에 마지막으로 방문한 값에서 dfs를 시작한 값으로 갈수있는지 구합니다 (사이클이 되는지)

3 . 경우의 수를 찾았으면 Yes를 출력하고 함수를 종료합니다.

4. 모든 시작점 경우의 수를 dfs로 탐색해서 찾지못하면 No를 출력하고 종료합니다.

예제와 질문글의 테스트 케이스

2 2

3 3

AAA

AAB

BBB

와 같은 것들도 통과합니다.

무엇이 문제일까요 도와주세요 ㅜㅜ

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int found = 0;

int I[4] = {0,1,0,-1};
int J[4] = {1,0,-1,0};

std::vector<std::vector<char>> input(51,std::vector<char>(51,0));
std::vector<std::vector<int>> visit(51,std::vector<int>(51,0));
void dfs(int start_i, int start_j, int x_i,int x_j, int depth,int n,int m){
    if (found == 1) {
        return;
    }
    
    // 길이가 3이상인경우, 그 점에서 시작점으로 갈수있는지 확인한다.
    if (depth >= 3) {
        for (int i = 0; i <= 4; i++) {
            if (start_i == (x_i + I[i]) && start_j == (x_j + J[i])) {
                std::cout << "Yes" << std::endl;
                found = 1;
                return;
            }
        }
    }
    
    visit[x_i][x_j] = 1;
    for (int i = 0; i < 4; i++) {
        int new_i = x_i + I[i];
        int new_j = x_j + J[i];
            
        if (new_i < 0 || new_i >= n || new_j < 0 || new_j >= m) {
            continue;
        }
            
        if (visit[new_i][new_j] == 0 && input[new_i][new_j] == input[x_i][x_j]) {
            dfs(start_i, start_j, new_i, new_j, depth + 1, n, m);
        }
    }
    visit[x_i][x_j] = 0;
    return;
        
    
}

int main(void){
    int n, m;
    std::cin >> n >> m;
    for (int i = 0; i < n; i++) {
        std::string temp;
        std::cin >> temp;
        for (int j = 0; j < m; j++) {
            input[i][j] = temp[j];
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (found == 1) {
            break;
        }
        for (int j = 0; j < m; j++) {
            if (found == 1) {
                break;
            }
            std::fill(visit.begin(),visit.end(),std::vector<int>(m,0));
            dfs(i, j, i, j, 0, n, m);
        }
    }
    
    if (found == 0) {
        std::cout << "No" << std::endl;
    }

    
}

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

문제

문제

출처

ICPC

16929 dfs) 제 로직에 해결방법이 없을까요 도와주세요 ㅜㅜ (설명있음)

qotmd01 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말