[백준/BOJ] 16929번 Two Dots

www.acmicpc.net/problem/16929

16929번: Two Dots

브루트 포스(완전 탐색) + DFS 유형의 문제였습니다. (다시 풀기)

문제의 조건에서 싸이클의 의미가 무엇인지 아는게 중요한데, DFS 탐색을 진행하면서 처음 탐색을 시작했던 좌표로 다시 돌아오는 것을 의미합니다. 따라서 시작 좌표로 다시 돌아오기 위해서 종료 조건 체크를 방문 체크 전에 해주어야 합니다. 이때 종료 조건에서 cnt >= 3 이 의미하는 것은 지나온 경로가 최소 3개 이상이여야 한다는 것을 의미합니다.

 

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

위에 그림처럼 사이클을 이루기 위해서 최소한 노드 4개가 필요합니다. 즉 최소 3개 이상의 경로를 지나야 다음 원래 노드로 돌아온다고 가정했을 때, 사이클을 이룰 수 있기 때문입니다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, sx, sy;
string map[52];
bool visit[52][52], flag;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void DFS(int x, int y, int val, int cnt) {
   for(int i = 0; i < 4; i++) {
       int nx = x + dx[i];
       int ny = y + dy[i];
       
       if(nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == val) {
           if(cnt >= 3 && nx == sx && ny == sy) {
               flag = true;
               return;
           }
           
           if(visit[nx][ny]) continue;
           visit[nx][ny] = true;
           DFS(nx, ny, map[nx][ny], cnt + 1);
       }
   }
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> map[i];
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            sx = i, sy = j;
            visit[sx][sy] = true;
            DFS(sx, sy, map[sx][sy], 0); // 시작 좌표, 시작 좌표의 값, 지나온 경로의 수
        
            if(flag) {
                cout << "Yes";
                return 0;
            }
            
            memset(visit, false, sizeof(visit));
            flag = false;
        }
    }
    
    cout << "No";
}