[BOJ] 알파벳(1987) - C++

R X C의 2차원 보드의 각 위치에 영문 대문자가 들어있다. (0, 0)의 좌표에서 상하좌우 중 한 방향으로 이동하려고 하는데, 가려고 하는 좌표의 값이 이미 지나온 경로에 있는 값이라면 갈 수 없다. 이때 이동할 수 있는 최대 거리를 구하는 문제이다.

1987번: 알파벳

---

풀이 과정

(0, 0)의 좌표에서 이동하면서 현재까지 지나온 값을 저장해야 한다. 보드의 값이 대문자 알파벳(A ~ Z) 26개로 한정돼 있으므로 26개 길이의 배열을 선언해 각 알파벳의 사용 여부 (True / False)를 저장한다. 4방향 중에 한 방향으로 탐색을 진행한 후에는 다른 방향으로도 진행이 가능하다면 탐색을 해야 하므로 그래프 탐색 기법인 '깊이 우선 탐색(DFS)'를 활용한다.

갈 수 있는 최대 길이를 정답으로 출력해야 하므로 각 탐색마다 정답으로 출력할 값을 현재 값과, 현재 재귀 깊이(탐색한 횟수)와 비교하며 더 큰 값으로 업데이트해줘야 한다.

 

---

소스코드

#include <iostream>
#define MAXN 20
using namespace std;
 
int ans = 0;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int R, C;
 
void DFS(int depth, int x, int y, bool bucket[], char matrix[MAXN][MAXN], bool visited[MAXN][MAXN]) {
 
    bucket[matrix[x][y] - 'A'] = true;
    ans = ans > depth + 1 ? ans : depth + 1;
    visited[x][y] = true;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (0 <= nx && nx < R and 0 <= ny && ny < C && visited[nx][ny] == false) {
            if (bucket[matrix[nx][ny] - 'A'] == false)
                DFS(depth + 1, nx, ny, bucket, matrix, visited);
 
        }
    }
    bucket[matrix[x][y] - 'A'] = false;
    visited[x][y] = false;
}
 
int main(void) {
 
    bool bucket[26] = { false };
    char matrix[MAXN][MAXN];
    bool visited[MAXN][MAXN] = { false };
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            cin >> matrix[i][j];
    
 
    DFS(0, 0, 0, bucket, matrix, visited);
    cout << ans << endl;
}

 

주석 추가

#include <iostream>
#define MAXN 20
using namespace std;
 
int ans = 0;
int dx[4] = { -1, 1, 0, 0 }; // 상하좌우 방향배열
int dy[4] = { 0, 0, -1, 1 };
int R, C; //행의 수, 열의 수
 
void DFS(int depth, int x, int y, bool bucket[], char matrix[MAXN][MAXN], bool visited[MAXN][MAXN]) { //재귀 깊이, x좌표, y좌표, 보드, 방문여부
 
    bucket[matrix[x][y] - 'A'] = true; // 현재 좌표 알파벳 방문 체크
    ans = ans > depth + 1 ? ans : depth + 1; // 정답(최대값) 갱신
    visited[x][y] = true; // 방문 체크
 
    for (int i = 0; i < 4; i++) { // 상하좌우 4방향
        int nx = x + dx[i]; // 다음 x좌표
        int ny = y + dy[i]; // 다음 y좌표
 
        if (0 <= nx && nx < R and 0 <= ny && ny < C && visited[nx][ny] == false) { // 다음 좌표가 보드 범위 내에 있고 방문하지 않았었다면
            if (bucket[matrix[nx][ny] - 'A'] == false) // 지나온 경로에 다음 좌표 값이 없었다면
                DFS(depth + 1, nx, ny, bucket, matrix, visited); // 다음 위치로 이동
 
        }
    }
    bucket[matrix[x][y] - 'A'] = false; // 혀재 좌표 알파벳 방문 체크 해제
    visited[x][y] = false; // 방문 여부 초기화
}
 
int main(void) {
 
    bool bucket[26] = { false }; // 알파벳이 나왔는 지 여부를 저장할 배열 (알파벳 대문자 26개)
    char matrix[MAXN][MAXN]; // 보드
    bool visited[MAXN][MAXN] = { false }; // 방문 여부 체크
    cin >> R >> C; // 행, 열 입력
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            cin >> matrix[i][j]; // 보드 입력
    
 
    DFS(0, 0, 0, bucket, matrix, visited); // DFS로 그래프 탐색
    cout << ans << endl; // 저장된 최대 길이 출력
}

---

채점 결과

처음에 방문 여부를 unordered_set을 써서 집합으로 관리를 했는데, 시간 초과가 났다. 이유가 생각나지 않아서 질문을 올려봐야겠다.

+) 질문 답변 결과

unordered_set도 hashSet 구조이기 때문에 추가와 삽입이 O(1) 시간이어서 시간 초과가 나지 않아야 한다고 생각했다. 하지만 정확히 1의 시간이 걸리는 것이 아니라 해쉬 함숫값 관리에 필요한 상수값이 클 수도 있어서 시간 초과가 난다는 답변을 받았다. 즉 N에 비례해 시간이 증가하는 것은 아니지만 삽입, 삭제에 상수 시간으로 시간이 오래 걸리므로 시간 초과가 났다.

시간 초과 코드 (주석을 모두 지우고, bucket 배열 대신 uset을 쓰면 시간 초과)

#include <iostream>
#define MAXN 20
//#include <unordered_set>
using namespace std;
 
int ans = 0;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int R, C;
 
//void DFS(int depth, int x, int y, unordered_set<char> & uset, char matrix[MAXN][MAXN], bool visited[MAXN][MAXN]) {
void DFS(int depth, int x, int y, bool bucket[], char matrix[MAXN][MAXN], bool visited[MAXN][MAXN]) {
 
    //uset.insert(matrix[x][y]);
    bucket[matrix[x][y] - 'A'] = true;
    ans = ans > depth + 1 ? ans : depth + 1;
    visited[x][y] = true;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (0 <= nx && nx < R and 0 <= ny && ny < C && visited[nx][ny] == false) {
            //if (uset.find(matrix[nx][ny]) == uset.end())
            if (bucket[matrix[nx][ny] - 'A'] == false)
                //DFS(depth + 1, nx, ny, uset, matrix, visited);
                DFS(depth + 1, nx, ny, bucket, matrix, visited);
 
        }
    }
    //uset.erase(matrix[x][y]);
    bucket[matrix[x][y] - 'A'] = false;
    visited[x][y] = false;
}
 
int main(void) {
 
    //unordered_set<char> uset;
    bool bucket[26] = { false };
    char matrix[MAXN][MAXN];
    bool visited[MAXN][MAXN] = { false };
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            cin >> matrix[i][j];
    
 
    //DFS(0, 0, 0, uset, matrix, visited);
    DFS(0, 0, 0, bucket, matrix, visited);
    cout << ans << endl;
}