24.03.14 19:21 작성
·
146
0
안녕하세요 선생님, 항상 강의 잘 보고 있습니다!!
이 문제 답의 visited가 1차원 배열이냐, 2차원 배열이냐에 따라서 시간복잡도 차이가 3배이상 나더라구요.
배열과 관련한 연산은 인덱스를 통한 참조와 삽입밖에 없는데 이렇게 차이가 많이 나는 이유가 뭘까요?
2차원 배열을 사용해서 통과한 답 첨부해드립니다. 감사합니다.
답변 2
1
0
2024. 03. 15. 12:10
안녕하세요 현진님 ㅎㅎ
이 문제 답의 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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.