BOJ_1987

처음은 BFS로 풀다가 내 풀이의 한계점을 느꼈다. 어떻게 할지 고민을 하다가 DFS로 풀어야 한다는 것을 깨달았당.
하지만 DFS는 아직 서투른 나는 (순열, 조합 부분만 많이 풀어봄) 얍문님의 사이트에서 배우면서 풀어냈다.

접근 방법(처음)

• 필자는 이런 맵 순회 문제는 BFS로 풀어내는 편이다.
• 위의 문제도 BFS로 풀어내려했는데 논리적 오류에 도달했다.
• BFS는 일단 여러 방향으로 발을 뻗어나가기에 각 칸마다의 check기록이 필요하다. 그럼 21 * 21 * 26 이 된다는 점에서의 첫 번째 오류
• 전 칸에서의 값을 비교하고 갱신시켜줘야하는데, 지금은 갱신시키는게 유리할 수 있어도 더 넓게 멀리 나갔을 때는 불리하게 작용할 수 있다. 미래를 알지 못하기에 이는 두 번째 오류를 발생시킨다.
• 이러한 이유로 BFS로 풀지 못한다는 것을 느꼈다.

접근 방법(다음)

• DFS로 접근했다. DFS는 일단 한 방향으로 끝까지 뻗어나가기에 위의 오류를 벗어날 수 있다.
• 칸도 세로 21 가로 21이기에 오버헤드와 같은 큰 문제점은 생각하지 않아도 된다.
• 그렇게 check[26]을 가지고 나온 알파벳을 정의해주며 나아갈 수 있는 끝까지 나아갔다. (안되는 지점에서 백트래킹)
• 물론 첫 시작 부분은 무조건 check = true

💻 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <string.h>

using namespace std;

#define endl "\n"

int R, C;
char maps[21][21];
bool check[26];
int answer = 0;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};

void dfs(int y, int x, int cnt)
{
    answer = max(answer, cnt);

    for (int i = 0; i < 4;i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny <0 || nx < 0 || ny >= R|| nx >= C || check[maps[ny][nx]-'A'] == true)
            continue;
        check[maps[ny][nx] - 'A'] = true;
        dfs(ny, nx, cnt + 1);
        check[maps[ny][nx] - 'A'] = false;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> R >> C;

    for (int i = 0; i < R;i++)
    {
        string in;
        cin >> in;
        for (int j = 0; j < C; j++)
            maps[i][j] = in[j];
    }

    check[maps[0][0] - 'A'] = true;
    dfs(0, 0, 1);

    cout << answer << endl;
}