dfs

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 적록색약" 문제는 빨간색과 초록색의 구분이 어려운 적록 색약인 사람이 보는 지역의 구역 수와 적록색약이 아닌 사람이 보는 지역의 구역 수를 구하는 문제입니다. 설명이 쉽도록 적록색약인 사람은 "적록색약", 적록색약이 아닌 사람은 "정상인"이라고 칭하겠습니다. 문제의 예제 입력 1번을 예로 들어 설명하자면 위와 같이 지역이 색깔에 맞게 구분이 됩니다.정상인 = 빨간색(R) = 2 + 초록색(G) = 1 + 파란색(B) = 1 ➡️ 4개의 구역적록색약  = 빨간색 && 초록색(RG) = 2 + 파란색(B) = 1 ➡️ 3개의 구역즉, 해당 문제는 적록색약과 정상인을 처리하기 위해 적록(Red & Green)을 하나의 색으로 취급하거나, 정상적인 색상 구..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 안전 영역" 문제는 다음과 다음과 같은 조건이있을 때 비의 양(즉, 높이)이 0부터 최대 높이까지 변할 때, 안전 영역의 최대 개수를 구하는 문제입니다. 어떤 지역의 높이가 주어졌을 때, 일정 높이 이하의 지역이 물에 잠긴다고 가정합니다.이때, 물에 잠기지 않은 구역들을 "안전 영역"이라고 부릅니다.즉, 물에 잠기지 않는 안전한 영역의 최대 개수를 출력하는 문제입니다. 이해를 돕기위해 예제 입력 1번을 가지고 접근해보겠습니다. 높이가 4일때는 왼쪽 그림과 같이 빨간색 영역이 물에 잠기게 되고, 높이가 5일 경우 오른쪽 그림과 같이 빨간색 영역이 물에 잠기게 됩니다. 그러면 물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, ..

개요알고리즘을 공부하다 보면 자주 마주치는 두 가지 개념이 있습니다. 바로 백트래킹(Backtracking)과 깊이 우선 탐색(DFS, Depth-First Search)인데요. 본 글에서는 얼핏 보면 비슷해 보이는 이 두 알고리즘의 차이점에 대해 정리하고자 합니다.  깊이 우선 탐색(DFS)이란❓DFS는 그래프나 트리를 탐색하는 방법 중 하나입니다.  시작 정점에서 출발하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 마치 미로를 탐색할 때 한 방향으로 끝까지 가보는 것과 같습니다.  [Algorithm] 효율적인 그래프 탐색: 자바로 구현한 DFS 알아보기 (1/2)이번 포스팅에서는 Java 알고리즘에서 필수적이라고도 말할 수 있는 DFS와 BFS에 대해서 알아보겠습니다. ..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 트리의 부모 찾기" 문제는 트리의 부모 노드를 찾는 문제입니다. 트리의 루트 노드는 항상 1이며, 루트 노드를 기준으로 2번 노드부터각 노드의 부모를 출력해야 합니다. 트리의 특징은 간선이  N-1개로 주어지며, 이는 사이클이 없고 모든 노드가 연결된 그래프를 뜻합니다.하나의 그래프에서 루트를 기준으로 트리를 구성하는 방법은 여러 가지가 존재할 수 있습니다. 저는 문제를 이해하기 위해 다음과 같은 트리 형태를 그려보았습니다. DFS 알고리즘을 사용하여 루트 1번부터 순회를 한다면, 1→6→3→5 순으로 내려가고, 다시 1로 돌아와서 4→2, 4→7 로 진행이 됩니다. 문제 접근트리 구성 : 연결정보는 방향성이 없이 주어지기 때문에 양방향 연결을 위한 ..