3-L 질문 있습니다!

안녕하세요 현진님 ㅎㅎ

이 문제 답의 visited가 1차원 배열이냐, 2차원 배열이냐에 따라서 시간복잡도 차이가 3배이상 나더라구요.

>> 음.. 제 생각에는 map도 쓰셨기 때문에 시간이 더 드는 것 같습니다.

map은 기본적으로 O(logN)의 시간복잡도를 가집니다.

현진님의 코드를 보시면...

void dfs(int y, int x, int cnt)
{
    visited[y][x] = 1;
    m[a[y][x]] = 1;
    ret = max(ret, cnt);

visited를 2차원으로 함 -> 이렇게 구현하려면 map이 필요함. 근데 사실 map만으로도 가능합니다.

예를 들어 A -> B이렇게 정점을 방문했을 때 A를 방문한다면 그 다음 A를 방문하지 않는 로직만이 필요하기 때문에 (2차원 좌표를 중심으로 하는게 아닌) map만으로도 충분히 가능합니다.

제가 현진님 코드를 좀 수정해봤습니다. 2차원 visited를 사용하지 않고 해보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int r, c, ret;
char a[20][20]; 
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
map<char, int> m;

int num()
{
    int n = 0;
    for (int i = 'A'; i <= 'Z'; i++)
    {
        if (m[i] == 1) n++;
    }
    return n;
}

void dfs(int y, int x, int cnt)
{ 
    m[a[y][x]] = 1;
    ret = max(ret, cnt);

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

        if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; 
        if (m[a[ny][nx]] == 1) continue; 
        dfs(ny, nx, cnt + 1); 
        m[a[ny][nx]] = 0;
    }
}

int main()
{
    for (int i = 'A'; i <= 'Z'; i++) m.insert({ i, 0 });

    cin >> r >> c;

    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> a[i][j];
        }
    }

    dfs(0, 0, 1);
    cout << ret;

    return 0;
}

지금 보시는 것처럼 map만을 이용했고 시간은

1528ms가 걸리는 것을 볼 수 있습니다.

즉, visited 2차원이 아니라 map을 사용하셔서 시간이 더 걸리는 것입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

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