C# 백준 1987 알파벳 (깊이우선탐색)

1987번: 알파벳

IDEA

모든 가능성을 탐색하고 최적의 결과를 얻어내는 문제다. 처음에는 아무 생각 없이 BFS를 시도했다. 이 문제는 탐색 과정에 문자를 계속 붙여나가고 이걸 String으로 관리한다면 쓸모없는 메모리가 엄청 늘어날 것이다. 그래서 나는 StringBuilder로 경로를 저장하고 이걸 큐에 돌려 BFS를 실행하기로 했다. 너무 짧은 생각이었다. 문자 형식 데이터는 16바이트를 차지한다. 만약 한 지점에서 모든 방향이 가능했고 1회 탐색을 시도했다면 32바이트 데이터가 큐에 4개 들어가게 된다. 그 다음은 각각 왔던 곳으로 돌아가는 경우를 제외한 3개 방향으로 탐색을 시도할 수 있다. 이렇게 되면 48바이트 데이터가 12개 들어간다. 만약 9회차의 탐색을 시도했다고 해보자. 큐에 있는 데이터는 160바이트이고 몇개가 있을지는 가늠이 안된다. 한 100개쯤? 그렇다면 16Kb를 먹는다. 그리고 내 코드의 치명적인 문제는 다음 알파벳이 이전 경로에 포함되었는지 여부를 판단하는 과정에 있었다. StringBuilder 데이터를 ToString( )메소드로 String형식으로 바꾼 다음 모든 인덱스의 문자를 하나하나 확인했다. 이렇게 되면 String을 StringBuilder로 대체한 이유가 없어진다. 매 확인마다 String이 생성되고 그대로 버려지기 때문이다.

 

BFS는 한번에 감당해야할 데이터가 너무 많다. 어차피 완전 탐색이니 DFS로 가기로 했다. 그리고 StringBuilder를 포기하고 그냥 char 배열을 사용하기로 했다. 이러면 쓸데없는 변환으로 메모리를 두배로 쓰는 일은 없다. 성공했지만 여전히 느리다. 다른 사람의 코드를 참고해 더 빠른 방법을 찾아봤다. 어차피 알파벳 대문자만 사용하기 때문에 26크기의 bool 배열을 사용하면 매 탐색에 시간낭비하며 배열을 훑어볼 필요 없이 알파벳 자체를 인덱스로 bool 값을 확인해주면 된다.

 

CODE

using System;
using System.Linq;
class Program
{
    static int R, C, x, y, max, index;
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    static char[,] map;
    static char[] path;
    static bool[] check = new bool[26];
    static void Main()
    {
        var rc = Console.ReadLine().Split().Select(int.Parse).ToArray();
        R = rc[0]; C = rc[1]; index = 0;
        map = new char[R, C];
        path = new char[R * C + 1];
        // IndexOutOfRange 예외를 피하기 위해 최대 길이에서 1칸을 더 늘려줬다.
        for (int i = 0; i < R; i++)
        {
            var row = Console.ReadLine();
            for (int j = 0; j < C; j++)
                map[i, j] = row[j];
        }
        dfs(0, 0);
        Console.WriteLine(max);
    }
    static void dfs(int a, int b)
    {
        path[index] = map[a, b]; index++;
        // path 배열에 현재 위치의 알파벳을 더해주고 index를 증가시킨다.
        check[map[a, b] - 65] = true;   // 알파벳이 더해졌으니 bool 값을 true로 변경
        max = max > index ? max : index;// 배열 길이를 확인한다.
        if (max == 26) return;          // 최대값이 26이 되었다면 더 늘어날 수 없다.
        for (int i = 0; i < 4; i++)
        {
            x = a + dx[i]; y = b + dy[i];
            if (x < 0 || y < 0 || x >= R || y >= C) continue;
            if (check[map[x, y] - 65]) continue;    // 이미 들어있는 알파벳이면 패스
            else dfs(x, y);
        }
        check[map[a, b] - 65] = false;
        index--;
        // 탐색이 끝났다.
        // 알파벳을 다시 탐색하지 않음으로 되돌리고
        // 배열 길이도 하나 줄인다.
    }
}