백준 1987 - 알파벳

문제 설명

세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1$1$행 1$1$열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

https://www.acmicpc.net/problem/1987

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, R x C 문자로 이루어진 2차원 행렬이 주어지면, {0, 0}에서 시작해서 같은 문자를 포함하지 않으며 최대한 많이 이동한 길이를 구하는 것이다.

 

R, C가 20으로 제한되어 있기 때문에 dfs, bfs 등으로 간단하게 해결할 수 있다고 생각할 수 있다.

하지만, 일반적인 방법으로 문제를 풀게되면 시간 초과 혹은 메모리 초과가 발생한다.

bfs에서는 현재 포함한 문자들을 확인하기 위해 추가적인 자료구조가 필요했다.

set으로 체크를 해봤지만, 메모리 초과가 발생해서 dfs로 변경하였다.

 

하지만, 이번엔 시간초과가 발생했다.

포함한 문자를 체크하기 위해 N번의 연산이 추가로 필요한 게 문제라고 생각했다.

따라서, 이를 전역 변수인 map으로 포함된 문자를 카운팅하며 dfs를 진행하면 된다 생각했다.

문제는 맞았지만, 시간이 다른 사람의 풀이보다 몇 배는 오래 걸렸다.

 

이를 해결하기 위해 비교해 보니 포함된 문자를 체크하는 부분을 map이 아닌 vector를 사용하면 된다.

알파벳은 26개로 한정되어 있기 때문에, 문자를 key가 아닌 index로 사용하는 것이다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int R, C;
int ans = 1;
vector<vector<char>> board;

vector<int> dy = { -1, 0, 1, 0 };
vector<int> dx = { 0, 1, 0, -1 };

vector<int> Cnt(26, 0);

void dfs(int y, int x, int depth)
{
    ans = max(ans, depth);
    for (int i = 0; i < 4; i++)
    {
        int newY = y + dy[i];
        int newX = x + dx[i];

        if (newY < 0 || newY >= R || newX < 0 || newX >= C) continue;
        if (Cnt[board[newY][newX] - 'A'] > 0) continue;

        Cnt[board[newY][newX] - 'A']++;
        dfs(newY, newX, depth + 1);
        Cnt[board[newY][newX] - 'A']--;
    }
}

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

    cin >> R >> C;
    
    board.resize(R, vector<char>(C));
    for (int i = 0; i < R; i++)
    {
        string input;
        cin >> input;
        for (int j = 0; j < C; j++)
        {
            board[i][j] = input[j];
        }
    }

    Cnt[board[0][0]-'A'] = 1;
    dfs(0, 0, 1);

    cout << ans;

    return 0;
}

---