글 읽기 - 싸이클일때

johyesong8686 3년 전 1

사이클일때를 bfs로 어떻게 돌아야 할지 몰라서

시작점(start)에서 가장 먼거리 좌표 (max_)

먼거리 좌표(max_)에서 가장 먼거리 좌표(maxx_)

maxx_와 start가 같고, 거리가 3이상 일때 ==>사이클이라고 판단

이런식으로 논리를 세워서 풀었습니다 ㅜㅜ

혹시 논리가 틀렸나요 ?

틀렸다면 사이클을 확인하기 위한 다른 논리를 알수있을까요 ?

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;


int n,m;

int check [52][52];
string pan[52];
int x_p[]={-1,+1,0,0};
int y_p[]={0,0,-1,+1};
int mx_x;
int mx_y;
int le=-1;

void bfs(int startx,int starty){

    queue <pair<int,int > >q;
    q.push(make_pair(startx,starty));
    check[startx][starty]=0;
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int k=0; k<4;k++){
            int nx=x+x_p[k];
            int ny=y+y_p[k];
           
            
            if(nx >=0 && nx <n && ny >=0 && ny<m){
                
                if(pan[nx][ny]==pan[x][y]){
                //cout <<"nx:" <<nx <<"ny:" <<ny <<'\n';
                if(check[nx][ny]==-1||le==-1){
                    
                    check[nx][ny]=check[x][y]+1;
                    if(check[nx][ny] >le){
                        le=check[nx][ny];
                        mx_x=nx;
                        mx_y=ny;
                    }
                    q.push(make_pair(nx,ny));
                }
            }



            }
            
        }

    }
    

    
}
int main(void ){
    
    
    cin >>n >>m;
    for(int i=0;i<n;i++){
      cin >>pan[i];
    }
    bool ok=false;
    
    
    
    for(int i=0;i<n;i++){
        for(int j=0; j<m;j++){
            le=-1;
            memset(check,-1,sizeof(check));
            bfs(i,j);
            le=-1;
            memset(check,-1,sizeof(check));
            bfs(mx_x,mx_y);
            if(mx_y==i&&mx_y==j&&le>=3){
                ok=true;
                break;

            }

           
            
        }
        if(ok){
            break;
        }
       

    }

    if(ok){
        cout <<"Yes";
    }else{
        cout<<"No";
    }

     
    


   


    

    return 0;
}

eve8108 3년 전 3

반례입니다.

4 4

BBBB

AABA

BAAA

BBBB

작성자님의 알고리즘대로 하면 위의 예시에서 cycle이 없지만 cycle이 존재한다고 생각하고 Yes를 출력하게 됩니다.

dfs로 풀어보심이 어떠실지요.

johyesong8686 3년 전 2

감사합니다! 아예 저 논리로는 불가능 하겠군요~

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

문제

문제

출처

ICPC

싸이클일때

johyesong8686 3년 전 1

eve8108 3년 전 3

johyesong8686 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말