23.08.17. 풀었던 문제들 복기

Leetcode 542. 01 Matrix, 20분

 0과 1만 있는 matrix에서 0으로부터 거리를 리턴하면 되는 문제.

 나는 BFS를 사용했다.

• 모든 0지점부터 BFS 탐색을 시작한다. 단, 갱신할 수 없는 위치라면(다른 0으로부터 더 가깝다면) 그곳은 탐색하지 않는다.
• 하나의 최적화를 추가하는데, 0에서 BFS를 각각 수행하는 것이 아니라(그렇게 하면 BFS가 10000번 수행될 수도 있다.)
  • 모든 0을 queue에 넣고 한 칸씩 BFS 해 나가는 것이다. 그러면 0에 인접한 칸은 그 개수만큼 방문하지만, 다음 갱신할 칸은 1번씩만 방문한다.

 그러면 worst case 최대 1만번 겹치는 탐색이 존재하고, 모든 칸을 1만번씩 방문하게 되므로 시간 내에 충분히 풀 수 있다.

// Runtime 62 ms Beats 91.36%
// Memory 30.2 MB Beats 86.75%

typedef pair<int, int> pii;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size(), INF = 10001;
        vector<vector<int>> answer(m, vector<int>(n, INF));
        queue<pii> q;
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if(mat[i][j] == 0){
                     answer[i][j] = 0;
                     q.push({i, j});
                }
            }
        }

        while(!q.empty()){
            pii cur = q.front(); q.pop();
            for(int i = 0; i<4; i++){
                int nr = cur.first + dr[i];
                int nc = cur.second + dc[i];
                if(0 <= nr && nr < m && 0 <= nc && nc < n && answer[cur.first][cur.second] + 1 < answer[nr][nc]){
                    answer[nr][nc] = answer[cur.first][cur.second] + 1;
                    q.push({nr, nc});
                }
            }
        }

        return answer;
    }
};

 

시간복잡도

 BFS에 O(V+E)인데 V = 1만, E=4만, 추가적으로 O(V)만큼의 시간이 필요하다. 그러니까 O(V)이다. (V는 1만)

 

공간복잡도

 정답 배열을 만들기 위해 O(mn) size 배열을 만들어야 한다.

 

 

 

BOJ 14725. 개미굴, 25분

 이 문제는 그다?지 어렵지 않은 문제다. tree의 개념과 tree traverse를 알고 있다면 간단하게 풀 수 있는 문제. 단, [어떤 node의 child들이 여러 개가 들어갈 수 있다는 것 + child들이 이름 순으로 정렬되어야 한다는 것]을 유의해야 한다.

 일단 child들이 여러개가 들어갈 수 있으며 정렬되어야 하기 때문에 vector는 사용하지 않았다. 정렬하기 힘들기 때문이었다. 그러면 set, map이 남는데... set은 비교 함수를 만들어야 해서 map을 사용했다. child의 먹이 이름을 key, child node를 value로 설정했다. 그러면 child 먹이 이름을 사용해 쉽게 접근할 수 있을 뿐더러 정렬도 되어있기 때문에 위 조건을 만족하기 쉬웠다. 

 메모리까지 최적화하기 위해서는 set을 사용하는 것이 낫다. 내가 구현한 것은 map key에 name이 들어가고, 또 node에도 name이 들어가기 때문이다. 그러나 속도를 위해 이렇게 구현했다.

struct Node{
    string name;
    map<string, Node*> childs;
};

Node* root = new Node();

int N;

// 순회하며 먹이 이름을 출력
void traverse(Node* cur, int depth){
    for(int i = 0; i<2*depth; i++) cout<<'-';
    cout<<cur->name<<'\n';

    for(auto &elem : cur->childs){
        traverse(elem.second, depth+1);
    }
}

void solve(){
    // 입력과 동시에 tree 구성
	cin>>N;
    int K;
    for(int i = 0; i<N; i++){
        cin>>K;
        string name;
        Node* cur = root;
        for(int j = 0; j<K; j++){
            cin>>name;
            if(cur->childs.find(name) == cur->childs.end()){ // 없는 경우 새로 만들어 넣음.
                Node* new_node = new Node();
                new_node->name = name;
                cur->childs[name] = new_node;
                cur = cur->childs[name];
            } else{ // 있는 경우 기존 것으로 이동
                cur = cur->childs[name];
            }
        }
    }

    // traverse 및 출력
    for(auto &elem : root->childs){
        traverse(elem.second, 0);
    }
}

 

시간복잡도

 먹이 정보 개수 N은 1000보다 작으모, 각 먹이 정보 개수의 길이는 15보다 작다. 즉, depth가 최대 15인 tree이며 width가 최대 1000이라는 뜻이다. 그러면 worst case node 개수는 15000이다.

 tree traverse에 O(V+E)가, tree에 넣을 때 O(depth * logN)만큼이 걸린다. 그러면 O(V+E)가 더 우세하므로 O(15000)정도 걸릴 것으로 예상된다.

 

공간복잡도

 node 개수는 worst case 15000개이므로 O(15000)이다.