[백준 16929 - C++] Two Dots : DFS

www.acmicpc.net/problem/16929

16929번: Two Dots

문제

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

 

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다. 
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

 

입력

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

 

출력

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

 

제한

• 2 ≤ N, M ≤ 50

 

풀이

이문제가 시간제한이 빡세고 데이터 크기도 더 크게 들어올 수 있었다면 정말 어려웠을 것을 것이다. 그러나 그렇지 않아서 쉽게 풀 수 있었다.

사이클을 찾기 위해서 시작점을 저장하고 dfs 탐색을 하면서 그 시작점을 다시 도착하게 되는 경우 Yes를 출력하고 프로그램을 종료시켰다.

이때 가장 적게 이동하는 사이클의 경우는

AA

AA        이렇게 생긴 경우인데 이때 이동 횟수는 4회이다. 따라서 사이클이 생기기 위해서는 적어도 4회이상 이동하여 시작점으로 돌아온 것이다. 그 조건도 추가하여 확인해주면 제대로 사이클이 생기는 경우를 확인할 수 있다.

 

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

char map[50][50];
int visited[50][50];
int X[4] = {1, -1, 0, 0};
int Y[4] = {0, 0, 1, -1};
int s_x, s_y;
int cnt;

void dfs(int x, int y, int n, int m);

int main(void){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
         scanf("%s", map[i]);
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            
            cnt = 0;
            s_x = i;
            s_y = j;
            dfs(i, j, n, m);
        }
    }
    printf("No\n");
}

void dfs(int x, int y, int n, int m){
    int next_x, next_y;
    
    visited[x][y] = 1;
    
    cnt++;
    
    for(int i=0; i<4 ;i++){
        next_x = x+X[i];
        next_y = y+Y[i];
        if(next_x < 0 || next_x >= n || next_y < 0 || next_y >=m)
            continue;
        if(map[next_x][next_y] != map[x][y])
            continue;
        if(visited[next_x][next_y] == 1  && next_x==s_x && next_y==s_y && cnt > 3){
            printf("Yes\n");
            exit(0);
        }
        if(visited[next_x][next_y] == 1)
            continue;
        
        dfs(next_x, next_y, n,m);
    }
    visited[x][y] = 0;
    cnt --;
}