C++ 프로그래머스 무인도 여행

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

 

처음에 bfs로 풀었는데 dfs로 푸는 것이 시간 복잡도 측면에서 유리한 것 같아서 차이를 정리하려고 합니다.

 

처음 한 풀이 (bfs)

#include <string>
#include <vector>
#include <bits/stdc++.h>

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
bool vis[101][101];

using namespace std;
// 격자의 각 칸에는 X 또는 1~9사이 자연수. X는 바다, 숫자는 무인도 
// 지도의 각 칸에 적힌 숫자는 식량을 나타냄. 며칠동안 머물 수 있는지
// 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return
// 지낼 수 있는 무인도가 없으면 -1
// 모든 칸 탐색 100*100 = 10^4
vector<int> solution(vector<string> maps) {
    vector<int> answer;
    queue<pair<int, int>> q;
    int n = maps.size();
    int m = maps[0].size();
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(maps[i][j] != 'X') {
                if(vis[i][j])   continue;
                vis[i][j] = true;
                q.push({i, j});
                int days = 0;
                while(!q.empty()) {
                    auto cur = q.front();
                    q.pop();
                    days += maps[cur.first][cur.second] - '0';
                    for(int dir=0; dir<4; dir++) {
                        int ny = cur.first + dy[dir];
                        int nx = cur.second + dx[dir];
                        if(nx < 0 || ny < 0 || ny >=n || nx >= m)   continue;
                        if(vis[ny][nx] || maps[ny][nx] == 'X') continue;
                        vis[ny][nx] = true;
                        // cout << ny << nx << maps[ny][nx] << '\n';
                        q.push({ny, nx});
                    }
                 }
                answer.push_back(days);
            }
        }
    }
    if(answer.empty())  answer.push_back(-1);
    sort(answer.begin(), answer.end());
    return answer;
}

시작점이 여러개인 bfs로 maps를 순회하며 X가 아니면 큐에 넣고, 그 지점을 시작점으로 탐색을 하여 더하도록 하였다. 

이렇게 하면 최악 시간 복잡도는 O(n*m*n*m)이 된다. 이렇게 되는 이유는 이중 for문을 돌며 시작점을 탐색하는 부분에서 n*m이 들고, maps가 모두 숫자로 채워져 있을 경우 한 시작점을 큐에 넣었을 때 모든 지점을 탐색하게 되어 큐에 m*n개의 좌표가 들어가게 되므로 내부 while문이 n*m번 반복하게 된다. 

 

두 번째 풀이(dfs, 전역 변수 사용)

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

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
bool vis[101][101];
int days;
// 격자의 각 칸에는 X 또는 1~9사이 자연수. X는 바다, 숫자는 무인도 
// 지도의 각 칸에 적힌 숫자는 식량을 나타냄. 며칠동안 머물 수 있는지
// 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return
// 지낼 수 있는 무인도가 없으면 -1
// 모든 칸 탐색 100*100 = 10^4
// bfs 시간 복잡도 O(10^8) 
// dfs 시간 복잡도 O(n*m = 10^4)


void dfs(vector<string> maps, int y, int x) {
    int n = maps.size();
    int m = maps[0].size();
    days += maps[y][x] - '0';
    vis[y][x] = true;
    for(int dir=0; dir<4; dir++) {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if(ny < 0 || ny >= n || nx < 0 || nx >= m || maps[ny][nx] == 'X' || vis[ny][nx])   continue;
        dfs(maps, ny, nx);
    }
}

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    
    int n = maps.size();
    int m = maps[0].size();
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(maps[i][j] != 'X' && !vis[i][j]) {
                dfs(maps, i, j);
                answer.push_back(days);
                days = 0;
            }
        }
    }
    if(answer.empty())
        answer.push_back(-1);
    sort(answer.begin(), answer.end());
    return answer;
}

전역 변수를 사용하는 dfs를 작성하여 풀이하였다. 이 경우 시간 복잡도는 dfs 호출 횟수에 의해 좌우된다. 현재 칸이 숫자일 경우에만 dfs를 호출하므로 maps가 모두 숫자로 채워져있을 경우 최악의 시간 복잡도 O(n*m)이다. 

 

세 번째 풀이(dfs, 리턴 값 사용)

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

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
bool vis[101][101];
// 격자의 각 칸에는 X 또는 1~9사이 자연수. X는 바다, 숫자는 무인도 
// 지도의 각 칸에 적힌 숫자는 식량을 나타냄. 며칠동안 머물 수 있는지
// 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return
// 지낼 수 있는 무인도가 없으면 -1
// 모든 칸 탐색 100*100 = 10^4
// bfs 시간 복잡도 O(10^8) 
// dfs 시간 복잡도 O(n*m = 10^4)


int dfs(vector<string> maps, int y, int x) {
    int n = maps.size();
    int m = maps[0].size();
    if(y < 0 || y >= n || x < 0 || x >= m || maps[y][x] == 'X' || vis[y][x])    return 0;
    int ret = maps[y][x] - '0';
    vis[y][x] = true;
    for(int dir=0; dir<4; dir++) {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        ret += dfs(maps, ny, nx);
    }
    return ret;
}

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    
    int n = maps.size();
    int m = maps[0].size();
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(maps[i][j] != 'X' && !vis[i][j]) {
                int sum = dfs(maps, i, j);
                answer.push_back(sum);
            }
        }
    }
    if(answer.empty())
        answer.push_back(-1);
    sort(answer.begin(), answer.end());
    return answer;
}

마지막 풀이는 dfs를 다른 방식으로 작성하여 보았다.

전체적인 구조는 위 dfs코드와 같지만, dfs에서 값을 return 하도록 하였다.

 

이 문제에서 bfs와 dfs의 시간 복잡도 차이가 발생하는 이유

maps의 모든 좌표에 값이 숫자라고 가정하자.

 

bfs에서 (0, 0)을 큐에 넣고 while문에 진입하게 되는데, 이 때 모든 좌표를 넣게 되므로 n*m번 반복한다.

while문이 종료후 모든 좌표를 탐색하였지만 이중 for문에서 (0, 0)을 제외하고 남은 n*(m-1) 불필요하게 확인하여야 하므로 O(n*m*n*m)이 된다.

 

dfs의 경우는 앞서 말한 것과 같이 dfs함수 호출 횟수에 따라 시간 복잡도가 결정된다. 탐색하려는 셀에 숫자가 있는 경우만 dfs를 호출하므로 시간 복잡도는 전체 셀의 개수인 O(m*n)이 된다.