문제 난이도GOLD I (링크)   문제 풀이각각의 독립된 섬들을 최단 거리로 연결하고 싶을 때, 놓을 수 있는 다리의 총 길이의 최소값을 구하는 문제.역시나 최소 신장 트리를 응용한 문제가 되겠다. 이번에는 각 간선을 구하는 것과 더불어, 이 섬이 어느 정점인지를 구하는 것도 필요하다. 결국엔 두 정점 사이의 간선을 구해서 문제를 풀어야하기 때문이다.  위의 그림처럼 문제에서 요한 3가지 올바르지 않은 방법과 함께, 추가로 두 가지만 주의한다면 쉽게 풀 수 있다. 처음 다른 섬을 만났을 때 만족하지 않는 조건이라면 바로 빠져나올 것.부끄럽게도 처음 코드를 완성시켰을 때,  다른 섬을 만났을 때, 종료 조건을 부족하게 작성하여 아래 그림처럼 더이상 탐색하지 못함에도 불구하고 탐색을 시켰다.   Union..

https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 완전탐색 문제를 처음으로 외부 검색 없이 혼자 해결한 문제... 고생의 노력이 드디어 빛을 조금 본 것 같다. 1. boolean타입의 이차원 배열 선언 - 해당 칸이 숫자일 경우 true처리 2. dfs메서드에서 한번 탐색이 끝나서 list.add가 되는 경우는 무인도끼리 연결이 되지 않을 때, 즉 해당 섬의 연결이 끝났을 때가 될 수 있게 조건을 줬다. public void dfs(St..

너비 우선 탐색 ( Breadth-first search )트리나 그래프를 방문 또는 탐색하는 방법으로 루트 노드에서 시작해서 인접 노드를 먼저 탐색하는 방법.   탐색 방법1. 루트노드에서 시작한다.  2. 자식노드들을 저장한다.  3. 저장되어있는 노드를 방문하며 저장되어있는 노드들의 자식들을 저장하며  4. 위의 과정을 모든 노드를 방문할 때 까지 반복하며 완료 시 탐색을 종료한다.   특징1. 어떤 노드를 방문했는지 반드시 검사 해야 한다.2. Queue를 사용하는 경우가 일반적이며 재귀적으로 동작하지 않는다.3. Prim, Dijkstra알고리즘과 유사하다.  장점1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다.3. 너비..