백준 16929 Two Dots C++

https://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"를 출력한다.

---

같은 색으로 이루어진 공을 찾는데, 사이클이 이루어져야 한다.

점은 4개 보다 크거나 같아야 한다. 즉, 다음과 같은 경우를 판별해야 한다.

 

위의 경우는 인접한 4개의 점이 인접하고, 모든 칸의 색이 노란색이다.

이와 같은 경우를 판별하는 것이 목적이다.

 

먼저 입력을 받고 방문 배열을 초기화를 해주었다!.

void input(){
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin >> map[i][j];
        }
    }
}
 
void init(){
 
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            visited[i][j] = false;
        }
    }
}

사이클이 존재한다는 것을 백트래킹으로 판별하는데,

DFS를 (x,y)에 대해서 돌리고 만약 상하좌우로 시작점과 같은 색을 가진 공이라면, 백트래킹을 거쳤고,

깊이가 4가 이상이 되고(공이 4개이상) 좌표가 시작점과 같은 좌표라면 사이클이 존재한다고 생각했다.

 

void dfs(int x,int y,int depth){
    //깊이가 4 이상이고 (공이 4개이상이고) 시작점과 같은 좌표일 경우 사이클 존재
    if(depth >= 4 && x == start_x && y == start_y){
        is_find = true;
        return;
    }
 
    for(int i = 0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= m){
            continue;
        }
        //시작좌표의 색깔과 같은 색깔의 공이면 백트래킹
        if(map[nx][ny] == map[x][y] && visited[nx][ny] == false){
            visited[nx][ny] = true;
            dfs(nx,ny,depth+1);
            visited[nx][ny] = false;
        }
    }
}

 

전체 소스코드

#include <iostream>
#include <string>
using namespace std;
 
bool visited[51][51];
char map[51][51];
int n,m;
bool is_find = false;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
 int start_x = 0;
 int start_y = 0;
 
void input(){
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin >> map[i][j];
        }
    }
}
 
void init(){
 
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            visited[i][j] = false;
        }
    }
}
 
void dfs(int x,int y,int depth){
    //깊이가 4 이상이고 (공이 4개이상이고) 시작점과 같은 좌표일 경우 사이클 존재
    if(depth >= 4 && x == start_x && y == start_y){
        is_find = true;
        return;
    }
 
    for(int i = 0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= m){
            continue;
        }
        //시작좌표의 색깔과 같은 색깔의 공이면 백트래킹
        if(map[nx][ny] == map[x][y] && visited[nx][ny] == false){
            visited[nx][ny] = true;
            dfs(nx,ny,depth+1);
            visited[nx][ny] = false;
        }
    }
}
 
int main(void){
    input();
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            init(); //모든 방문 배열 초기화
            start_x = i; //시작점의 좌표 
            start_y = j;
 
            dfs(i,j,1); 
            //DFS를 돌려서 사이클 존재하는 경우
            if(is_find == true){
                cout << "Yes";
                return 0;
            }
        }
    }
 
    cout << "No";
 
}