BFS

• 큐 구현: Queue<Integer> q = new LinkedList<Integer>();
  
  • 큐 생성 시, arrayList사용안하고 LinkedList사용하는 이유: 삽입 삭제의 효율적인 측면에서 arrayList의 경우에는 중간에 요소를 추가,삭제할때 원소들이 이동해야해서 비효율적임, LinkedList는 요소를 추가 삭제할때 리스트의 요소들의 순서 이동이 없기에 효율적임. --> 결과적으로 삽입 삭제가 빈번하게 일어나는 큐는 ArrayList가 더 효율적임.
  • queue.add(): 큐에 값 추가, full --> 에러 발생
  • queue.offer(): 큐에 값 추가, full --> false return
  • queue.poll: 큐의 첫번째 요소 삭제, 큐가 비어있을 때 null return
  • queue.remove: 큐의 첫번째 요소 삭제, 큐가 비어있을 때 예외 발생
• 기본적으로 자바에서 문자열을 사용하는 String은 불변객체임(한번생성시 변경 불가)
  • ex> string + string --> 메모리 할당과 메모리 해제를 발생시키며 성능적으로 안좋음.
• 이를 해결하기 위해 나온 개념이 StringBuilder
  • StringBuilder는 mutable한 성질을 가지고 있음.
  • 문자열을 더할때 새로운 객체를 생성하는 것이 아닌, 기존의 데이터에 더하는 방식을 사용 --> 빠른 속도, 적은 부하
  • --> 긴 문자열 더할때는 StringBuffer, StringBuilder 사용 추천
  • 문자열 변경이 빈번하지 않을 때 --> String 사용
  • 문자열이 빈번하게 변경, 멀티쓰레드 환경 --> StringBuffer 사용
  • 문자열이 빈번하게 변경, 멀티쓰레드 환경X --> StringBuilder 사용

import java.util.LinkedList;
import java.util.Queue;
import java.lang.StringBuilder;

public class Solution {
    
    static String bfs(int start, int[][] graph, boolean[] visited) {
        // bfs 출력 결과
        StringBuilder sb = new StringBuilder();
        // bfs에 사용할 큐 생성
        Queue<Integer> q = new LinkedList<Integer>();
        
        // q에 시작 노드 삽입
        q.offer(start);
        
        // 시작 노드 방문 처리
        visited[start] = true;
        
        // 큐가 빌때가지 반복
        while(!q.isEmpty()) {
            int nodeIndex = q.poll();
            sb.append(nodeIndex + " -> ");
            // 큐에서 꺼낸 노드와 연결된 노드 체크
            for(int i = 0; i < graph[nodeIndex].length; i++) {
                int temp = graph[nodeIndex][i];
                if(!visited[temp]) {
                    visited[temp] = true;
                    q.offer(temp);
                }
            }
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
        
        boolean[] visited = new boolean[9];
        
        System.out.println(bfs(1, graph, visited));
    }
}