[BOJ/백준][Gold4] 16929 : Two dots (C++)

https://www.acmicpc.net/problem/16929

16929번: Two Dots

 

[난이도] Gold4
[유형] DFS

[풀이]
무방향 그래프의 cycle을 찾는 문제이다.
next node가 이미 방문한 node이면서 부모가 아니면 cycle이다.
부모를 체크하기 위해 visit 배열에 방문한 순서를 저장해놓고
현재 노드의 visit, 다음 노드의 visit 차가 1이면 부모 노드이므로 무시한다.

#include <cstdio>
int N,M,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
char map[50][50];
int visit[50][50];
bool dfs(int y,int x,int k){
    visit[y][x]=k;
    for(int i=0;i<4;i++){
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(ny < 0 || nx < 0|| ny >=N || nx >= M || map[ny][nx]!=map[y][x]) continue; 
        if(visit[ny][nx]){
            if(k-visit[ny][nx]>1) return 1;
        } else if(dfs(ny,nx,k+1)) return 1;
    }
    return 0;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf(" %c",&map[i][j]);  
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!visit[i][j]){
                if(dfs(i,j,0)){
                    puts("Yes");
                    return 0;
                }
            }
        }
    }
    puts("No");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16929.cpp