백준 1987 알파벳

DFS로 탐색하는 문제이다. 일단 쭈우욱 탐색을 하는 중에는, 이미 지나온 알파벳이 중복으로 나타날 수 없다. 가장 길게 이을 수 있는 칸 수를 구하면 된다.

 

DFS함수는 상하좌우 픽셀의 탐색가능여부를 확인 후, 다른 픽셀로 넘어가기 전에 현재 알파벳 방문을 표시한다. 이 과정이 없으면, 다음 픽셀을 탐색할때 중복되는 알파벳을 포함하므로 끝도없이 이어지게 된다.("ABBDSAAAAADDAAAAA..." 같이)

 

원래 Visit 배열이 아닌, 상태를 나타내는 구조체에 string으로 지금까지 방문한 문자열을 저장하고, 마지막 탐색이 막히면 그 때 string의 길이를 리턴하는 방식으로 작성했는데, 매 번 string에서 find를 해야 하고 어차피 알파벳은 개수가 정해져 있으니 배열을 만들어 인덱스로 접근하는게 가독성에도 좋고 연산시간도 단축 할 수 있어 구현을 변경했다.

 

DFS 함수만 만들어지면 main에서 해줄건, (0,0) 에서 실행만 해주면 된다.

DFS의 구현을 머리속에 담아두고, 키포인트(visit 배열, 탐색 방향/조건)들을 수정하는 방향으로 문제에 접근해나가는게 좋을 것 같다. 괜히 상태 저장을 따로 빼두다가 엄하게 삽질을 했다...

---

#include <iostream>
#include <vector>
#include <string>

int H, W;
struct pos{
    int y;
    int x;
    int cnt;
};
bool alpha[27];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};

int dfs(pos cur, std::string map[])
{
    int maxLen = 0;
    for (int i = 0; i < 4; i++)
    {
        int ny = cur.y + dy[i];
        int nx = cur.x + dx[i];
        if (nx < 0 || nx > W - 1 || ny < 0 || ny > H - 1)
            continue;
        if (alpha[map[ny][nx] - 'A'])
            continue;
        pos next;
        next.x = nx;
        next.y = ny;
        next.cnt  = cur.cnt+1;
        alpha[map[ny][nx] - 'A'] = 1;
        maxLen = std::max(dfs(next, map), maxLen);
        alpha[map[ny][nx] - 'A'] = 0;
    }
    if (maxLen == 0)
        return cur.cnt;
    return maxLen;

}

int main()
{
    std::cin >> H >> W;
    std::string map[H];
    for (int i = 0; i < H; i++)
    {
        std::string tmp;
        std::cin >> tmp;
        map[i] += tmp;
    }
    pos init;
    init.x = 0;
    init.y = 0;
    init.cnt = 1;
    alpha[map[0][0] - 'A'] = 1;
    std::cout << dfs(init, map);
}

/*
회고
원래 매 상태마다 string 만들어서 거기에 지금 방문하는 문자 있으면 삐려고 함.
해보다가 안되서 visit 쓰는 풀이 보고 재접근.
한번 말리니까 쭉 말린다. 인덱스 접근할때 대문자 빼줘야되는데 그거도 계속 소문자 적어두고 그려러니 했음.
심호흡하고. 차분히 풀기.
*/

 

한번 말리니까 더 털려 visit[]에 접근할 때, 대문자 'A'를 빼줬어야 하는데 그냥 소문자 'a'를 빼줘 인덱스를 계속 이상한 곳을 참조하고 있었다...

역시 오늘도 차분히 풀어야 한다는 결론으로 귀결. 이것도 참 꾸준하네.

 

오늘도 평온한 하루 되길. 슨민.