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

처음에 방문 처리를 map 자료형으로 처리했더니 1600ms가 나와서

강의를 보고 풀이를 봤습니다. 풀이는 map을 배열로만 바꿨을 뿐 다른점이 없어보였는데 400ms가 나오더군요.

보니까 map은 찾는 시간이 O(log n)이라서 오래 걸린다 생각하여 O(1)에 해당하는 unordered_map으로 바꿔보니 시간 초과가 났습니다.. 이런 유형은 그냥 map 쓰지말고 배열로 처리하는 게 나을까요?

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int n, m;
string graph[22];
unordered_map<char, bool> visited;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int ans;
void DFS(int x, int y, int depth) {
    ans = max(ans, depth);

    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (visited[graph[nx][ny]]) continue;
        visited[graph[nx][ny]] = 1;
        DFS(nx, ny, depth + 1);
        visited[graph[nx][ny]] = 0;
    }
    
}

int main() {
    fastIO();

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> graph[i];
    }

    visited[graph[0][0]] = 1;
    DFS(0, 0, 1);

    cout << ans << endl;

    return EXIT_SUCCESS;
}