백준 16929번

DFS를 이용해 한줄긋기를 하듯이 탐색해 나가다가 탐색했던 위치에 도달하면 한 사이클이 이뤄지는 것으로 보았다.

 

고민했던 부분은 다음 탐색으로 나아간 뒤 직전에 탐색했던 위치를 방문하지 않게 하는 방법과

사이클이 이뤄질 때 조건체크를 어떻게 해야 좋을까 였다.

 

사이클의 도달조건과 탐색한 위치의 재방문을 막는 조건이 같기에 새로운 조건을 찾아내야 했다.

 

문제의 게임 특성상 점 4개 이상을 이어야만 사이클이 완성된다는 특징을 이용해서 방문한 노드가 4개 이상이면서 방문기록이 있는 노드에 도달했을 때 사이클이 완성되었다고 보는 첫번째 방법과

 

직전에 방문한 노드를 제외한 3방향만 방문하도록 하는 두번째 방법을 생각했다. 

 

DFS를 하면서 이전에 탐색했던 위치는 체크해놓아 재탐색을 하지 않기.

 

나의 제출

public class CodingTest
{
    class Node
    {
        public char alphabet;
        public bool ischecked = false;
       
        public Node(char alphabet)
        {
            this.alphabet = alphabet;
        }
    }
    public static void Main(string[] args)
    {
        string firstStr = Console.ReadLine();
        string[] firstStrs = SplitString(firstStr);
        int[] ints = StringToNum(firstStrs);
        // N x M
        int N = ints[0];
        int M = ints[1];

        //checked
        int checkCount = 0;

        // 다음 검색위치 미리 지정
        int[] dN = { 0, 0, 1, -1 };
        int[] dM = { 1, -1, 0, 0 };

        // 게임판 만들기
        Node[,] gameBoard = new Node[N,M];

        bool result = false;

        // 게임판 입력
        for (int i = 0; i < N; ++i)
        {
            string inputBoard = Console.ReadLine();
            char[] chars = inputBoard.ToCharArray();
            for (int j = 0; j < M; ++j)
            {
                gameBoard[i, j] = new Node(chars[j]);
            }
        }

        // DFS 실행
        for (int i = 0; i < N; ++i)
        {
            if (result)  break;
            checkCount = 0;
            for (int j = 0; j < M; ++j)
            {
                gameBoard[i, j].ischecked = true;

                result = DFS(i, j, i, j);
                if (result) break;
            }
        }

        if (result)
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");        
        }

        // 직전의 위치는 방문제외
        bool DFS(int N, int M, int beforeN, int beforeM)
        {
            gameBoard[N, M].ischecked = true;
         
            // 상하좌우 탐색
            for ( int i = 0; i < 4; ++i)
            {
                int nN = N + dN[i];
                int nM = M + dM[i];

                // 직전 위치와 같으면 건너뜀
                if (beforeM == nM && beforeN == nN)
                {
                    continue;
                }

                // 유효한지 확인
                if(( nN >= 0 && nN < gameBoard.GetLength(0))  &&  (nM >= 0 && nM < gameBoard.GetLength(1))  && gameBoard[nN,nM].alphabet == gameBoard[N, M].alphabet)
                {
                    if (gameBoard[nN, nM].ischecked)
                    {
                        return true;
                    }
                    else
                    {
                        DFS(nN, nM, N, M);
                    }
                }
            }

            gameBoard[N, M].ischecked = false;
            return false;
        }
    }



    // 한 줄에 여러개를 입력
    public static string[] SplitString(string input)
    {
        if (input.Contains(" "))
        {
            string[] _words = input.Split(' ');
            return _words;
        }
        else
        {
            string[] _words = new string[1];
            _words[0]= input;
            return _words;
        }
    }

    // str을 int등의 자료형으로 바꾸는 메서드
    public static int[] StringToNum(string[] words)
    {
        int[] result = new int[words.Length];
        for(int i= 0; i < words.Length; i++)
        {
            result[i] = int.Parse(words[i]);
        }

        return result;
    }

    // 나눌 필요 없는 숫자를 int로 바꾸는 메서드
    public static int OneStringToNum(string words)
    {        
        int result = int.Parse(words);        

        return result;
    }
}