[BOJ][C#] 2210 숫자판 점프

LimJaeJun·2023년 8월 28일

algorithm boj

PS/BOJ

목록 보기

19/108

📕 문제

📌 링크

📗 접근 방식

모든 좌표마다 DFS 진입
만든 string의 중복처리를 위해 HashSet 자료구조 사용
종료 조건
- 만든 string의 길이가 6이 되면 종료
DFS 진입한 좌표 기준으로 상하좌우 이동한 좌표로 DFS 진입
(조건 : 숫자판 크기의 밖으로 벗어나는지 확인)

📘 코드

namespace BOJ
{
    class No_2210
    {
        const int MAX = 5;

        static int[,] board = new int[MAX, MAX];
        static HashSet<string> words = new HashSet<string>();
        static int[] dx = new int[] { 1, 0, -1, 0 };
        static int[] dy = new int[] { 0, 1, 0, -1 };

        static void Main()
        {
            for(int i=0 ;i< MAX;i++)
            {
                int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                for(int j=0 ;j< MAX;j++)
                {
                    board[i, j] = inputs[j];
                }
            }

            for(int i = 0 ; i < MAX ; i++)
                for(int j = 0 ; j < MAX ; j++)
                    DFS(i, j, board[i,j].ToString());

            Console.WriteLine(words.Count);
        }

        static void DFS(int x, int y, string word)
        {
            if(word.Length == 6)
            {
                words.Add(word);
                return;
            }

            for(int dir = 0 ; dir < 4 ; dir++)
            {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if(nx < 0 || nx >= MAX || ny < 0 || ny >= MAX) continue;

                DFS(nx, ny, word + board[nx, ny].ToString());
            }
        }
    }
}