1ilsang

Developer who will be a Legend

LeetCode 1267. Count Servers that Communicate

2019-12-03 1ilsangProblem Solving

Problem

처음에는 문제 제대로 안읽고 BFS 로 접근했다가 이상해서 다시보니 연결요소가 같은 행/열의 끝까지 인걸 깨닫게 되었다. 그래서 DFS 로 처리한 문제.

/**
 * @param {number[][]} grid
 * @return {number}
 */
const countServers = (grid) => {
    const visit = new Array(grid.length).fill(0).map(e => new Array(grid[0].length).fill(false));
    let answer = 0;

    for(let i = 0; i < grid.length; i++) {
        for(let j = 0; j < grid[0].length; j++) {
            if(visit[i][j] || !grid[i][j]) continue;
            visit[i][j] = true;
            answer += go(grid, visit, i, j);
        }
    }
    
    return answer;
};

const go = (grid, visit, r, c) => {
    let ret = 0;
    
    const dr = [ 0, 1, 0, -1 ];
    const dc = [ 1, 0, -1, 0 ];
    const queue = [];
    queue.push({r, c});
    
    while(queue.length > 0) {
        const cur = queue.shift();
        ret++;
        for(let i = 0; i < 4; i++) {
            let nr = cur.r + dr[i];
            let nc = cur.c + dc[i];
            while(nr >= 0 && nc >= 0 && nr < grid.length && nc < grid[0].length) {
                if(grid[nr][nc] && !visit[nr][nc]) queue.push({r: nr, c: nc});
                visit[nr][nc] = true;
                nr += dr[i];
                nc += dc[i];
            }
        }
    }

    return ret === 1 ? 0 : ret;
}

첫 번째 서버에서 상하좌우 직선 끝까지 돌리면서 그 경로에 연결되는 서버가 있는지 본다. 선상에 가능한 서버가 있다면 큐에 담고 돌린다. 이때 큐에서 나올때마다 ++ 을 해주면 연결된 개수를 알 수 있게 된다. 만약 반환 값이 1이면 자기자신 밖에 없는 경우이므로 0 을 리턴해주어야 한다.

그럼 이만!