99클럽 코테 스터디 19일차 TIL - 그래프

오늘의 학습 키워드

그래프, BFS

---

알고리즘 문제

• 프로그래머스 Level 3. 가장 먼 노드
• https://school.programmers.co.kr/learn/courses/30/lessons/49189 

프로그래머스

 

---

공부한 내용

Tree 자료 구조

• Parent - Child 관계를 나타낼 수 있는 자료구조
• 노드 한 개에 1개의 Parent 노드가 있을 수 있다.
• 노드 한 개에 N개의 Child 노드가 있을 수 있다. 
• e.g.) 폴더, 조직도, 가족 관계도
• Binary Tree: 노드 한 개에 최대 2개의 Child 노드를 가질 수 있는 자료구조. => 왼쪽 Child 노드, 오른쪽 Child 노드.

class Node {
    int value;
    Node next;
    
    Node(int val) {
        this.value = val;
        this.next = null;
    }
}

class BinaryNode {
    int value;
    BinaryNode leftChild;
    BinaryNode rightChild;
    
    BinaryNode(int val) {
    	this.value = val;
        this.leftChild = null;
        this.rightChilde = null;
    }
}

 

DFS

• 한 방향을 먼저 쭉 탐색하고, 그 후에 다음 노드로 올라와서 쭉 탐색한다.
• 재귀 (Reculsive)로 간단하게 구현 가능.

BFS

• Level 별로 탐색한다. 루트노드로부터 1칸 떨어진 노드들 탐색 -> 2칸 떨어진 노드들 탐색 -> ... 
• Queue 자료구조로 구현 가능.
  • 처음에 시작할 루트노드를 queue에 먼저 넣는다.
  • 이후에 큐가 비어있지 않으면 계속 반복하면서 탐색한다.
  • 일반적으로 탐색 종료 조건은 큐의 사이즈가 0. 즉, 큐가 비어있으면 탐색 종료를 의미한다.

---

오늘의 회고

처음 시도

• 이전에 BFS, DFS 개념은 알고 있었지만 막상 알고리즘을 짜려고 보니 아직 개념이 부족하다고 느껴서 다시 Tree 자료구조에 대해 공부했다.
• BFS, DFS 개념을 다시 보니 이번 문제는 BFS로 풀면서 정해진 루트노드 1부터 시작해서 depth 별로 탐색하면서 depth마다 노드가 몇 개인지 카운트를 해야 한다고 생각했다.

해결

• BFS로 문제를 풀 때, 먼저 자료구조 Queue를 사용하면 depth 별로 queue에 담을 수 있어서 편리하다.
• BFS 문제 풀 때, 방문한 노드 체크 배열과 인접 행렬(노드 간 연결 관계 2차원 배열)을 만들어서 탐색 관리를 한다.
  • 인접 행렬 => 노드 A와 노드 B 사이에 간선 존재 여부를 시간복잡도 O(1)로 조회할 수 있다. (1이면 존재)
  • 방문 체크 배열 => 총 노드 개수 +1 사이즈로 1차원 배열을 만들어서 방문했다면 true로 알 수 있다.
• 일반적으로 BFS 문제는 queue가 빈 경우를 탐색 종료 조건(반복문 종료)으로 사용한다. 
  • 이번 문제에서는 존재하는 마지막 depth에 노드 개수를 알아야 하기 때문에, depth를 반복할 때마다 큐의 사이즈를 업데이트하도록 했다.
  • 그리고 큐가 비어있다면, depth(노드들)이 더이상 존재하지 않기 때문에 종료하고, 마지막에 업데이트된 큐 사이즈가 마지막 depth의 노드 개수를 의미하게 된다.

---

문제 풀이

import java.util.*;

class Solution {
    //return: 1번 노드와 가장 멀리 떨어진 노드는?
    boolean[] visit;		// 해당 노드(배열 인덱스)에 이미 방문했는지 여부
    boolean[][] relative;	// 인접 행렬 (그래프 관계)
    
    public int bfs(int[][] edge) {
        Queue<Integer> que = new LinkedList<>();
        que.offer(1);
        visit[1] = true;
        
        for (int i = 0; i < edge.length; i++) {
            int x = edge[i][0];
            int y = edge[i][1];
            
            relative[x][y] = true;
            relative[y][x] = true;
        }
		
        int size = 0;
        while (!que.isEmpty()) {
            size = que.size();
            
            for (int i = 0; i < size; i++) {
                int current = que.poll();
                
                for (int j = 1; j < visit.length; j++) {
                    if (!visit[j] && relative[current][j]) {
                        que.add(j);
                        visit[j] = true;
                    }
                }
            }
        }
        return size;
    }
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        this.visit = new boolean[n+1];
        this.relative = new boolean[n+1][n+1];
        
        answer = bfs(edge);
        
        return answer;
    }
}