[프로그래머스] 43162 네트워크(Lv.3) - BFS

문제

네트워크

• 예제1
  
• 예제2
  

코드

시도 1 - X

computers가 2차원 배열이라서 단순히 1인 노드가 연결된 뭉치의 개수를 구하는 문제로 잘못 이해했다.
시도 2로...

import java.util.*;
class Solution {

    boolean[][] visited;
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    public int solution(int n, int[][] computers) {
        visited = new boolean[n][n];
        int cnt = 0;
        for (int i = 0; i < computers.length; i++) {
            for (int j = 0; j < computers[0].length; j++) {
                if (computers[i][j] == 1 && !visited[i][j]) {
                    // q.offer(new int[] {i, j});
                    visited[i][j] = true;
                    bfs(computers, i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public void bfs(int[][] computers, int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x, y});
        while (!q.isEmpty()) {
            int[] current = q.poll();
            for (int i = 0; i < 4; i++) {
                int cx = current[0] + dx[i];
                int cy = current[1] + dy[i];

                if (cx >= 0 && cx < computers.length && cy >= 0 && cy < computers[0].length) {
                    if (computers[cx][cy] == 1 && !visited[cx][cy]) {
                        q.offer(new int[] {cx, cy});
                        visited[cx][cy] = true;
                    }
                }
            }
        }
    }
}

시도 2 - O

computers[행][열]의 행이 각 컴퓨터이고 열은 해당 행과의 연결 여부를 표현한 값이다.(1: 연결O, 0: 연결X)
즉, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]인 경우 1과 2가 연결되어 있고 1과 3은 연결되지 않았다. 2와 1이 연결되어 있고 2와 3은 연결되지 않았다. 3은 1, 2와 연결되지 않았다. 결국 아래 사진과 같이 된다.

이를 코드에 적용하면 노드는 총 n개만 존재하므로 visited 배열을 2차원 배열이 아닌 크기가 n인 1차원 배열로 선언하면 되고 큐 또한 각 노드의 좌표가 아닌 노드 자체를 저장해야 하기 때문에 Integer 자료형으로 선언한다.

boolean[] visited = new boolean[n];
Queue<Integer> q = new LinkedList<>();

나머지 코드는 기존의 BFS 풀이 방식과 동일하다.

import java.util.*;
class Solution {
    boolean[] visited;
    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        int cnt = 0;
        for (int i = 0; i < computers.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                bfs(computers, i);
                cnt++;
            }
        }
        return cnt;
    }

    public void bfs(int[][] computers, int node) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(node);
        while (!q.isEmpty()) {
            int current = q.poll();

            for (int i = 0; i < computers[current].length; i++) {
                if (computers[current][i] == 1 && !visited[i]) {
                    q.offer(i);
                    visited[i] = true;
                }
            }

        }
    }
}

후기

문제만 이해하면 매우 쉬운 문제이다. 그런데 문제를 잘못 이해해서 한참을 헤멨다 .... 잘 좀 보자