[c++] BOJ 1987 :: 알파벳

난이도 : 골드 4

걸린 시간 : 40분

 

문제

알파벳 문제 바로가기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	49866	15734	9600	29.155%

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

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

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

 

풀이

• 주의! 입력이 20이므로 적지만 경로 문제이므로 길어질 수 있음
• DFS를 사용
• 지금까지 나온 알파벳을 저장하는 방법
  • unordered_set
  • int 배열

 

코드

#include <iostream>
#include <queue>

using namespace std;

int direction[4][2] = { {0,1}, {1,0}, {0, -1}, {-1, 0} };
int R, C;
char arr[21][21];
int visited[26];
int res = -1;

void dfs(int r, int c, int num) {
    res = res < num ? num : res;

    for (int i = 0; i < 4; i++) { // 상하좌우 돌면서
        int rp = r + direction[i][0];
        int cp = c + direction[i][1];
        if (rp < 0 || cp < 0 || rp >= R || cp >= C) // 맵 밖에 위치하면 제외
            continue;
        if (!visited[arr[rp][cp]-'A']) {
            // 경로에 이미 포함되어 있는 곳은 제외
            visited[arr[rp][cp] - 'A'] = 1;
            num++;
            dfs(rp, cp, num);
            num--;
            visited[arr[rp][cp] - 'A'] = 0;
        }
    }
}

int main() {
    // 입력 받기
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
        }
    }

    fill(&visited[0], &visited[25], 0); // 초기화
    visited[arr[0][0]-'A'] = 1;
    dfs(0, 0, 1);
    cout << res << '\n';
}

 

주의할 점

• 메모이제이션을 사용해보려고 했지만 해당 위치에서의 가능 최대 경로가 이전 경로에 종속적이므로 (해당 위치까지의 경로가 달라지면 앞으로 가능한 경로도 달라지므로) 불가능
• unordered_set으로 저장해보려고 했지만 시간초과가 나옴 => 기본 배열로 하는 것이 좋음
  • unordered_set의 삽입 시간 복잡도 O(N)와 find 시간 복잡도 O(N)을 가지고 있기 때문이다.
  • 배열로 하면 해당 알파벳이 이미 나왔는지 확인하기 위해 O(1)의 시간복잡도가 필요하다.

 

결과