까만 창에 개발 블로그

📋 개요  🧩 문제https://www.acmicpc.net/problem/1753 📝  형식 📥 입력📤 출력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으..

DFS와 BFS란? 일단, 항상 공부하기전에 용어를 정리하는 습관을 기르고자 합니다. DFS(Depth-First Search) : 깊이 우선 탐색 BFS(Breadth-First Search) : 너비 우선 탐색 말그대로, 깊이 먼저 탐색하냐, 너비 먼저 탐색하냐 차이인거 같아요 그렇다면 뭘 탐색할까요? 그래프(Graph) 탐색 알고리즘 입니다. 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 DFS와 BFS는 대표적인 그래프 탐색 알고리즘 입니다. DFS의 동작 원리 깊이 우선 탐색 답게 깊이를 우선적으로 탐색합니다. 수직적 탐색 이라고 생각하면 쉬울것 같네요 이렇게 수직 방향으로 탐색을 하게 됩니다. Java를 통해 구현해볼까요?? import java.util.Linked..