[leetcode] 1267. Count Servers that Communicate

class Solution {
public:
    int mvI[4] = {0,0,-1,1};
    int mvJ[4] = {1,-1,0,0};
    
    int DFS(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& visited){
        int ret = 1;
        
        if(visited[i][j]) return 0;
        visited[i][j] = true;
        bool goFlag = false;
                
        for(int k=0; k<4; k++){
                        
            for(int w = 1; w<max(grid.size(), grid[0].size()); w++){
                int newI = i + mvI[k] * w;
                int newJ = j + mvJ[k] * w;

                if(newI < 0 || newI >= grid.size()) continue;
                if(newJ < 0 || newJ >= grid[0].size()) continue;
                if(!grid[newI][newJ]) continue;

                goFlag = true;    
                ret += DFS(newI, newJ, grid, visited);    
            }
        }
        
        return goFlag ? ret : 0;
    }
    
    int countServers(vector<vector<int>>& grid) {
        vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), 0));
        int answer = 0;
        for(int i = 0; i<grid.size(); i++){
            for(int j = 0; j<grid[0].size(); j++){
                if(!grid[i][j]) continue;
                
                answer += DFS(i, j, grid, visited);
        
            }
        }
        return answer;
    }
};

가장 단순한 DFS를 무작정 돌려서 풀어보았습니다.

간신히 통과하는 군요,, ㅋㅋ

다시 생각해보니 DFS를 돌릴필요가 없던 문제였네요

그냥 배열을 행과 열 순서대로 한번씩 순회하기만 하면되는 간단한 문제입니다.

 

class Solution {
public:
    
    int countServers(vector<vector<int>>& grid) {
        vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), 0));
        
        int answer = 0;
        for(int i = 0; i<grid.size(); i++){
            vector<pair<int,int>> chk;
            for(int j = 0; j<grid[0].size(); j++){
                if(grid[i][j]) chk.push_back({i, j});
            }
            if(chk.size() <= 1) continue;
            answer += chk.size();
            
            while(!chk.empty()){
                pair<int, int> visit = chk.back();
                chk.pop_back();
                visited[visit.first][visit.second] = 1;
            }
            
        }
        for(int j = 0; j<grid[0].size(); j++){
            vector<pair<int,int>> chk;
            for(int i = 0; i<grid.size(); i++){
                if(grid[i][j]) chk.push_back({i, j});
            }
            if(chk.size() <= 1) continue;
            
            while(!chk.empty()){
                pair<int, int> visit = chk.back();
                chk.pop_back();
                if(visited[visit.first][visit.second]){
                    continue;
                }
                answer++;
            }
            
        }
        return answer;
    }
};

 

시간복잡도는 O(n) 정도이고 80% 정도 나왔으니 거이 최적에 가까운 풀이인가 봅니다.