백준 16929번. Two Dots(c++) / DFS

문제 자체는 매우 복잡하고 어려워보이지만, 결국은 처음 시작점으로 돌아올 수 있는 사이클이 있는 지를 판단하는 문제이다.

DFS로 처음 시작점에서 사이클을 그려 시작점으로 돌아올 수 있는 지를 판단해주었다.

 

// Two Dots
#include <cstring>
#include <iostream>
 
using namespace std;
 
int n, m;
string s;
char game[51][51];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int visited[51][51] = {0, };
bool tmp = false;
 
void check(int x, int y, int startX, int startY, int cnt)
{
    if(tmp==true){
        return;
    }
 
    if(cnt>=4 && x==startX && y==startY){
        tmp = true;
        return;
    }
 
    if(!visited[x][y]){
        visited[x][y] = true;
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<m){
                if(game[x][y]!=game[nx][ny]) continue;
                check(nx, ny, startX, startY, cnt+1);
            }
        }        
    }
}
 
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>s;
        for(int j=0; j<s.size(); j++){
            game[i][j] = s[j];
        }
    }
 
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            memset(visited, 0, sizeof(visited));
            tmp = false;
            check(i, j, i, j, 1);
            if(tmp==true){
                cout<<"Yes"<<"\n";
                return 0;
            }
        }
    }
 
    cout<<"No"<<"\n";
    return 0;
}