[프로그래머스] Level3 43162번: 네트워크 (JAVA)

문제

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

 

 

풀이코드

import java.util.*;

/**
 * @Date 2022/05/24
 * @URL https://programmers.co.kr/learn/courses/30/lessons/43162
 */
public class P43162_네트워크 {
    static int sumCount = 0;
    static boolean[][] visited;

    /**
     * x, y 좌표를 위한 노드
     */
    static class Node {
        private int x;
        private int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return this.x;
        }

        public int getY() {
            return this.y;
        }
    }

    public static void main(String[] args) {
        // write your code here
        P43162_네트워크 main = new P43162_네트워크();

        int[][] a = new int[][] { {1,1,0}, {1,1,0}, {0,0,1}};
        System.out.println(main.solution(3, a));
    }

    public int solution(int n, int[][] computers) {
        int answer = 0;

        visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) { // 방문하지 않았을때
                    if (computers[i][j] == 1) { // 1일때
                        bfs(i, j, n, computers);
                        sumCount++;
                    }
                }
            }
        }

        answer = sumCount;
        return answer;
    }

    private static void bfs(int x, int y, int n, int[][] graph) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        visited[x][y] = true;

        while (!q.isEmpty()) {
            /* 탐색 대상 : node */
            Node node = q.poll();

            int start = node.getY();
            for (int end = 0; end < n; end++) {
                /* 방문 가능 조건 */
                /* 방문하지 않았고, 숫자가 같을 경우  */
                if (!visited[start][end] && graph[start][end] == graph[x][y]) {
                    visited[start][end] = true;

                    /* queue push */
                    q.offer(new Node(start, end));
                }
            }
        }
    }
}

 

 

디버깅

(혼자 풀지 못한 문제이므로, 디버깅으로 과정을 파악해보자.)

 

1) i = 0, j = 0

 

2) while문 수행

큐에서 꺼낸 데이터

(x, y)	(0, 0)
(start, end)	(0, 0) (0, 1) (0, 2) : 반복문 수행 예정

 

• start = 0, end = 0

이미 방문했다.

 

• start = 0, end = 1

진행한다.

 

• start = 0, end = 2

if 조건문을 만족하지 않으므로 PASS한다.

if (!visited[start][i] && graph[start][i] == graph[x][y]) {

 

 

큐에서 꺼낸 데이터

(x, y)	(0, 1)
(start, end)	(1, 0) (1, 1) (1, 2) : 반복문 수행 예정

 

• start = 1, end = 0

처리한다.

 

• start = 1, end = 1

처리한다.

 

• start = 1, end = 2

if 조건문을 만족하지 않으므로 PASS한다.

 

 

큐에서 꺼낸 데이터

(x, y)	(1, 0)
(start, end)	(0, 0) (0, 1) (0, 2) : 모두 이전에 이미 수행되었다.

 

 

큐에서 꺼낸 데이터

(x, y)	(1, 1)
(start, end)	(1, 0) (1, 1) (1, 2) : 모두 이전에 이미 수행되었다.

 

while문 수행이 완료되어 다시, for 문으로 돌아가고 sumCount가 1 증가한다.

for (int j = 0; j < n; j++) {
    if (!visited[i][j]) { // 방문하지 않았을때
        if (computers[i][j] == 1) { // 1일때
            bfs(i, j, n, computers);
            sumCount++;
        }
    }
}

 

3) i = 0, j = 1

if (!visited[i][j]) { // 방문하지 않았을때

visited[0][1] 은 이미 방문하였다.

 

4) i = 0, j = 2

방문하지 않았지만, computers[0][2] 는 0이므로 if문을 만족하지 않는다.

if (computers[i][j] == 1) { // 1일때

 

5) i = 1, j = 0

이미 방문하였다.

 

6) i = 1, j = 1

이미 방문하였다.

 

7) i = 1, j = 2

computers[1][2] 는 1이 아니다.

 

8) i = 2, j = 0

computers[2][0] 는 1이 아니다.

 

9) i = 2, j = 1

computers[2][1] 는 1이 아니다.

 

10) i = 2, j = 2

computers[2][2] 일때는 조건이 만족하여, bfs 를 호출한다. 결론적으로 sumCount가 1 증가한다.

 

 

결론

위 배열에서 computers[0] 에 해당하는 요소 순서대로 순회한다.

그 후, 조건에 만족하는 경우 큐에 삽입되고, 이때의 (x, y) y값이 그 다음 순회할때 (x, y) x 값으로 선언된다.

예를들어 큐에 (0, 1)이 삽입되고, 이 데이터의 차례가 왔을때 y는 1이다.
앞으로 for문으로 수행될 데이터는 (1, 0), (1, 1), (1, 2)다. (end < n)

 

이런식으로 찾게됬을때 한번의 while문이 수행되는 동안이 하나의 네트워크로 볼 수 있다.

while (!q.isEmpty()) {
    /* 탐색 대상 : node */
    Node node = q.poll();

    int start = node.getY();
    for (int end = 0; end < n; end++) {
        /* 방문 가능 조건 */
        /* 방문하지 않았고, 숫자가 같을 경우  */
        if (!visited[start][end] && graph[start][end] == graph[x][y]) {
            visited[start][end] = true;

            /* queue push */
            q.offer(new Node(start, end));
        }
    }
}

 

그래서 sumCount가 bfs를 호출할때 증가된다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (!visited[i][j]) { // 방문하지 않았을때
            if (computers[i][j] == 1) { // 1일때
                bfs(i, j, n, computers);
                sumCount++;
            }
        }
    }
}