[ 백준 16929 ] Two Dots (C++)

백준의 Two Dots(16929) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 싸이클을 찾는 문제였다. 본인은 깊이 우선 탐색법을 통해서 구현해 보았다. 재귀를 호출 할 때의 매개변수는

   다음과 같이 설정하고 구현하였다.

   DFS(int x, int y, int dir, int line_Cnt, int Sx, int Sy)

   각 매개변수의 의미는 다음과 같다.(x좌표, y좌표, 현재 방향, 그은 선분의 갯수, 시작x좌표, 시작y좌표)

   Visit[][]배열을 통해서 일반적으로 방문표시를 한다면 문제를 해결하기 어렵다. 왜냐하면 첫 시작점으로 탐색을

   시작하게 된다면 Visit배열에 시작점은 이미 방문했다고 표시가 되어있는데, 이미 방문한 지점이라고 탐색을 안해버리면

   결국 시작점으로 돌아올 수 없다는 문제점이 발생하게 된다.

   그렇다고 시작점을 체크를 안해버리면 ?? 문제에서 요구하는 싸이클을 찾지 않았음에도 시작점으로 도착할 수가 있다.

   이런 경우이다.

   (x, y)에서 탐색을 통해서 (x+1, y)로 갔다고 가정해보자. 그럼 (x+1, y)에서는 ? (x,y)가 체크가 안되있기 때문에

   다시 (x, y)를 탐색할 것이고 이는 싸이클이 이루어지지 않았음에도 싸이클로 판단하는 문제가 발생할 수도 있다.

   따라서 본인은 Visit배열을 통해서 탐색한 지점을 체크를 해두고, 다른 매개변수들을 통해서 싸이클인지를 확인했다.

   일단, 문제를 보면 알 수 있는 내용이지만 싸이클을 이루기 위해서는 최소한 사각형을 만들어 주어야 한다.

   즉, 선분의 갯수가 4개 이상이어야 한다는 것이다. 그렇다면 선분의 갯수를 어떻게 4개 이상인지 아닌지 판단할까??

   바로, 방향을 관리해주는 dir변수이다. 현재 진행방향과 똑같은 방향으로 탐색을 할 때에는 선분의 갯수에 ++를 시키지

   않는다. 하지만 현재 진행방향과 다른 방향이라면 선분의 갯수를 ++해서 관리해 주었다.

   글을 적다보니 든 생각인데, 정확하게 표현하자면, 선분의 갯수보다는 '선분이 꺽인 횟수' 라고 생각하면 더 이해하기

   쉬울 것 같다.

   즉, 탐색하는 과정에서 이미 방문하지 않은 좌표라면 계속 탐색을 진행하면 되지만, 이미 방문한 좌표라면

   그 때는 탐색하려는 좌표가 시작점과 똑같으면서 선분이 꺽인 횟수가 4회 이상이라면 이는 정확하게 사각형을 만들고

   싸이클을 찾은 것이기 때문에 탐색을 종료하는 식으로 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool Flag = false;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 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 DFS(int x, int y, int dir, int line_Cnt, int Sx, int Sy)
{
    if (Flag == 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)
        {
            if (Visit[nx][ny] == false)
            {
                if (MAP[nx][ny] == MAP[x][y])
                {
                    Visit[nx][ny] = true;
                    if (i == dir) DFS(nx, ny, dir, line_Cnt, Sx, Sy);
                    else DFS(nx, ny, i, line_Cnt + 1, Sx, Sy);
                }
            }
            else
            {
                if (nx == Sx && ny == Sy && line_Cnt >= 4)
                {
                    Flag = true;
                    return;
                }
            }
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            memset(Visit, false, sizeof(Visit));
            int Start_X = i;
            int Start_Y = j;
            
            for (int k = 0; k < 4; k++)
            {
                memset(Visit, false, sizeof(Visit));
                Visit[i][j] = true;
                DFS(i, j, k, 1, Start_X, Start_Y);
                if (Flag == true)
                {
                    cout << "Yes" << endl;
                    return;
                }
            }
        }
    }
    cout << "No" << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}