늘 겸손하게

목차 문제명 문제풀이 코드 백준 - 16929번 : Two Dots 문제 유형 : DFS, 그래프 탐색 난이도 : 골드 4 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제 풀이 모든 정점에 대하여 1. 주어지는 게임판과 동일한 넓이, 높이의 배열을 선언하고 2. dfs로 그래프를 탐색하면서 시작점에서 몇번째로 탐색한 정점인지를 기록합니다. 3. 탐색이 끝나면 시작점 주위에 값이 4 이상인 값이 있다면 싸이클이 있는것이므로 "Yes..

안녕하세요 besforyou입니다. 이번 글은 리트코드 111번 문제입니다. 문제 설명 이진 트리가 주어졌을 때 최소 깊이를 구하라. 최소 깊이는 루트 노드로부터 가장 가까운 leaf 노드까지 갈 때 거쳐가는 노드의 개수입니다. 문제 풀이 깊이 우선 탐색(DFS)법으로 탐색하되 leaf 노드를 만나면 전역 변수로 선언해 높은 변수와 현재 깊이를 비교하여 현재 깊이 값이 더 작다면 변수를 교환합니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 var minDepth = function(root) { let min = 100001; let dfs = function(root, depth) { if(!root) return; if(!root.left ..

안녕하세요 besforyou입니다. 백준 11724 문제풀이를 적어보겠습니다. 문제 해설 정점과 간선이 주어졌을 때 방향 없는 그래프의 연결 요소( Connected Component )의 개수를 구하는 문제입니다. 문제 풀이 Connected Component의 개수는 dfs로 쉽게 알 수 있습니다. dfs로 방향 없는 그래프를 탐색하면 한번 탐색할 때 연결된 모든 정점들을 한 번씩 탐색합니다. 그러므로 dfs함수를 호출한 횟수가 connected component의 개수입니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ..

안녕하세요 besforyou입니다. 백준 문제 1260 소개를 시작하겠습니다. 문제 풀이 입력받은 정점과 간선들로 그래프를 생성하고 DFS search, BFS search를 해주면 된다. DFS 탐색 방법 : https://besforyou.tistory.com/122 Depth First Search for a Graph - 그래프 깊이-우선 탐색 안녕하세요 besforyou 입니다 이번 글에서는 그래프의 DFS에 대해 소개하겠습니다. 출처 : https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/ Depth First Search or DFS for a Graph - Geek.. besforyou.tistory.com BFS 탐색..