인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ.

사실 제가 여러번 고치면서 시도해봤는데 잘 안되네요...

이 문제가 아마 시간상한선이 좀 타이트해서 그러는 것 같습니다.

걸리는 것은 Set의 count, find는 O(logN)인데 비해 비트마스킹은 O(1)로 visited를 체킹할 수 있습니다. 비트마스킹으로 해보시겠어요?

참고로 제가 고친 코드는 다음과 같습니다. 불필요한 부분 등을 빼면서 고쳐봤습니다.

#include <iostream>
#include <vector>
#include <set>
using namespace std;

typedef vector<vector<char>> Board;

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int DFS(int y, int x, const Board& board, set<char>& visited) {
    int max_distance = 1;

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

        if (nx < 0 || nx >= board[0].size() || ny < 0 || ny >= board.size()) continue;
        if (visited.count(board[ny][nx])) continue;

        visited.insert(board[ny][nx]);
        max_distance = max(max_distance, 1 + DFS(ny, nx, board, visited));
        visited.erase(board[ny][nx]);
    }
    return max_distance;
}

int main() {
        ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int row, column;
    cin >> row >> column;

    Board board(row, vector<char>(column));
    for (int y = 0; y < row; ++y) {
        for (int x = 0; x < column; ++x) {
            cin >> board[y][x];
        }
    }

    set<char> visited;
    visited.insert(board[0][0]);
    cout << DFS(0, 0, board, visited) << "\n";

    return 0;
}

감사합니다.

안녕하세요, 인프런 AI 인턴입니다. kimmistral님.

백트래킹을 사용하고, unorded_set로 시간 복잡도 O(1)을 목표로 하셨지만 여전히 시간 초과 문제가 발생하고 있는 것에 대해 질문 주셨습니다. 이 문제를 해결하기 위해 다음의 포인트를 고려해 보시기 바랍니다:

1. 백트래킹 최적화:

   • 백트래킹은 재귀를 통해 여러 경로를 탐색하는 방식입니다. 따라서 불필요한 탐색을 줄이기 위한 가지치기(pruning) 기법이 중요합니다. 조건문을 추가하여 더 이상 필요 없는 탐색을 조기에 종료할 수 있도록 코드를 최적화해 보세요.
     

2. unorded_set의 사용:

   • unorded_set은 보통 O(1)의 시간 복잡도를 가지지만, 해시 충돌이 발생할 경우 최악의 경우 O(N)까지 시간이 소요될 수 있습니다. 해시 함수나 데이터 셋의 특성에 따라 성능이 저하될 수 있으니 이 부분도 검토해 보시기 바랍니다.
     

3. 참조 및 원상복구:

   • 레퍼런스 매개변수로 데이터를 전달하고 원상복구를 사용하여 메모리 사용을 줄이는 것은 좋은 접근입니다. 그러나 각 단계에서의 복구 단계가 적절히 진행되고 있는지, 혹시 불필요한 복구 과정이 추가로 수행되고 있는지 점검해 보세요.
     

관련 질문과 설명이 되어 있는 게시물을 참고하시면 도움이 될 것 같습니다:
- 시간초과 질문있습니다 - 큰돌님의 답변

이와 관련된 자료를 더 보면 unorder_map 또는 unorder_set이 최악의 경우 O(N)까지 걸릴 수 있다는 언급이 있습니다. 따라서 최솟값 테스트 케이스를 다양하게 시도하여 모든 경우의 수를 고려하고 있는지 확인해보세요.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드립니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.