[알고리즘 문제 풀기] 숫자판 점프(2210)

1. 문제 풀이 아이디어

• HashSet을 사용해 중복을 방지하고, DFS로 모든 경우를 탐색하여 가능한 서로 다른 숫자의 개수를 구한다.

2. 나의 정답 코드

using System.Text;
using System.Collections.Generic;
using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    StringBuilder sb = new StringBuilder();
    HashSet<string> set = new HashSet<string>();
    int[][] arr = new int[5][];
    for (int i = 0; i < 5; i++)
    {
        arr[i] = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    }
    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            solve(i, j);
        }
    }
    sw.WriteLine(set.Count);

    void solve(int x, int y)
    {
        if (sb.Length == 6)
        {
            set.Add(sb.ToString());
            return;
        }
        int[,] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dir[i, 0];
            int ny = y + dir[i, 1];
            if (nx < 0 || 4 < nx || ny < 0 || 4 < ny) continue;
            sb.Append(arr[nx][ny]);
            solve(nx, ny);
            sb.Remove(sb.Length - 1, 1);
        }
    }
}

3. 정리

• arr 배열을 5×5 크기로 선언하고, 입력값을 저장한다.

• solve(x, y) 함수를 이용해 DFS 탐색을 수행한다.

• 현재 숫자가 6자리가 되면 set에 추가하여 중복을 방지한다.

• 네 방향(상, 하, 좌, 우)으로 이동하며 백트래킹을 통해 모든 경우를 탐색한다.

• StringBuilder를 활용해 숫자를 이어붙이고, 탐색 후에는 제거하여 원래 상태로 복구한다.

• 모든 시작점을 기준으로 탐색을 진행한 후, set.Count를 출력한다.