강하게 연결된 요소(a strongly connected component)-LeetCode 문제

1. DFS 성질을 이용한 연결 요소 탐색

Easy 난이도

Problem 1: Number of Islands (LeetCode 200)
설명: 2D 그리드에서 '1'로 표시된 섬의 개수를 찾는 문제입니다. DFS를 사용하여 연결된 '1'들을 탐색해 섬의 개수를 계산합니다.
핵심 개념: DFS, 2D 그리드 탐색

Problem 2: Flood Fill (LeetCode 733)
설명: 시작 픽셀과 연결된 모든 픽셀을 탐색하여 색을 변경하는 문제입니다. DFS를 통해 인접한 픽셀을 처리합니다.
핵심 개념: DFS, 색칠 알고리즘

Problem 3: Max Area of Island (LeetCode 695)
설명: 2D 그리드에서 가장 큰 섬의 면적을 계산합니다. DFS로 연결된 '1'의 크기를 탐색합니다.
핵심 개념: DFS, 면적 계산

Problem 4: Island Perimeter (LeetCode 463)
설명: 2D 그리드에서 섬의 둘레를 계산하는 문제입니다. DFS로 경계를 탐색하여 둘레를 합산합니다.
핵심 개념: DFS, 경계 탐색

Problem 5: Merge Two Binary Trees (LeetCode 617)
설명: 두 이진 트리를 병합하는 문제입니다. DFS로 각 노드를 순회하며 병합합니다.
핵심 개념: DFS, 이진 트리

---

Medium 난이도

Problem 1: Number of Connected Components in an Undirected Graph (LeetCode 323)
설명: 무향 그래프에서 연결된 컴포넌트의 수를 찾는 문제입니다. DFS를 사용하여 각 컴포넌트를 탐색합니다.
핵심 개념: DFS, 연결 요소

Problem 2: Course Schedule (LeetCode 207)
설명: 수업들 간의 선후 관계를 바탕으로 모든 수업을 들을 수 있는지 확인하는 문제입니다. DFS로 사이클을 탐지합니다.
핵심 개념: DFS, 사이클 탐지

Problem 3: Course Schedule II (LeetCode 210)
설명: 수업들 간의 선후 관계를 바탕으로 가능한 수강 순서를 찾는 문제입니다. 위상 정렬을 수행합니다.
핵심 개념: DFS, 위상 정렬

Problem 4: Graph Valid Tree (LeetCode 261)
설명: 주어진 무향 그래프가 트리인지 확인하는 문제입니다. DFS로 연결성과 사이클 여부를 검사합니다.
핵심 개념: DFS, 연결성과 사이클

Problem 5: Pacific Atlantic Water Flow (LeetCode 417)
설명: 지형의 높이를 기반으로 태평양과 대서양으로 물이 흐를 수 있는 지점을 찾는 문제입니다. DFS로 탐색합니다.
핵심 개념: DFS, 양방향 탐색

 

2. 방향이 있는 그래프 문제

Easy 난이도

Problem 1: Find if Path Exists in Graph (LeetCode 1971)
설명: 유향 그래프에서 두 노드 간에 경로가 존재하는지 확인하는 문제입니다. DFS를 사용하여 탐색합니다.
핵심 개념: DFS, 경로 탐색

Problem 2: Find the Town Judge (LeetCode 997)
설명: 특정 노드가 모든 다른 노드로부터 신뢰를 받는지 확인하는 문제입니다.
핵심 개념: 유향 그래프, 신뢰 관계

Problem 3: Find Center of Star Graph (LeetCode 1791)
설명: 유향 그래프에서 스타 그래프의 중심 노드를 찾는 문제입니다.
핵심 개념: 유향 그래프, 중심 노드

Problem 4: Find All Numbers Disappeared in an Array (LeetCode 448)
설명: 배열에서 누락된 숫자를 찾는 문제로, 그래프 탐색의 개념을 활용합니다.
핵심 개념: 배열, 유향 그래프

Problem 5: Find the Difference (LeetCode 389)
설명: 두 문자열을 비교하여 추가된 문자를 찾는 문제입니다.
핵심 개념: 그래프 탐색 기초

Medium 난이도

Problem 1: Course Schedule (LeetCode 207)
설명: 수업들 간의 선후 관계를 바탕으로 모든 수업을 들을 수 있는지 확인하는 문제입니다. DFS로 사이클을 탐지합니다.
핵심 개념: DFS, 사이클 탐지

Problem 2: Course Schedule II (LeetCode 210)
설명: 수업들 간의 선후 관계를 바탕으로 가능한 수강 순서를 찾는 문제입니다. 위상 정렬을 수행합니다.
핵심 개념: DFS, 위상 정렬

Problem 3: Minimum Height Trees (LeetCode 310)
설명: 그래프에서 최소 높이 트리를 구성하는 루트를 찾는 문제입니다.
핵심 개념: 그래프 탐색, 트리

Problem 4: Reconstruct Itinerary (LeetCode 332)
설명: 항공권 목록을 기반으로 여행 일정을 재구성하는 문제입니다. DFS를 통해 경로를 탐색합니다.
핵심 개념: DFS, 경로 탐색

Problem 5: All Paths From Source to Target (LeetCode 797)
설명: 유향 그래프에서 시작 노드부터 종료 노드까지의 모든 경로를 찾는 문제입니다.
핵심 개념: DFS, 경로 탐색

 

3. 방향이 없는 그래프 문제

Easy 난이도

Problem 1: Number of Connected Components in an Undirected Graph (LeetCode 323)
설명: 무향 그래프에서 연결된 컴포넌트의 수를 찾는 문제입니다. DFS 또는 BFS로 각 컴포넌트를 탐색합니다.
핵심 개념: DFS, BFS, 연결 요소

Problem 2: Graph Valid Tree (LeetCode 261)
설명: 주어진 무향 그래프가 트리인지 확인하는 문제입니다. DFS를 통해 연결성과 사이클 여부를 검사합니다.
핵심 개념: DFS, 사이클 탐지, 연결성

Problem 3: Friend Circles (LeetCode 547)
설명: 친구 관계를 통해 형성된 그룹의 수를 찾는 문제입니다. 무향 그래프를 탐색합니다.
핵심 개념: DFS, 연결 요소

Problem 4: Connected Components in Graph (미등록 문제, 유사 문제는 323번과 동일)
설명: 무향 그래프에서 각 연결 요소를 출력합니다. DFS를 사용하여 컴포넌트를 탐색합니다.
핵심 개념: DFS, 연결 요소

Problem 5: Find All Groups of Farmland (LeetCode 1992)
설명: 2D 그리드에서 연결된 농지의 그룹을 찾는 문제입니다. DFS를 통해 영역을 탐색합니다.
핵심 개념: DFS, 2D 그래프 탐색

Medium 난이도

Problem 1: Longest Increasing Path in a Matrix (LeetCode 329)
설명: 2D 행렬에서 증가하는 가장 긴 경로를 찾는 문제입니다. DFS와 메모이제이션을 활용합니다.
핵심 개념: DFS, 메모이제이션

Problem 2: Critical Connections in a Network (LeetCode 1192)
설명: 네트워크에서 중요한 연결(브리지)를 찾는 문제입니다. Tarjan’s Algorithm을 사용합니다.
핵심 개념: DFS, 그래프 브리지

Problem 3: Keys and Rooms (LeetCode 841)
설명: 주어진 방들과 열쇠들로 모든 방에 들어갈 수 있는지 확인하는 문제입니다. DFS로 해결합니다.
핵심 개념: DFS, 연결성

Problem 4: Accounts Merge (LeetCode 721)
설명: 이메일 계정이 겹치는 경우 계정을 병합하는 문제입니다. DFS를 통해 연결된 계정을 탐색합니다.
핵심 개념: DFS, 연결 요소

Problem 5: Path With Minimum Effort (LeetCode 1631)
설명: 2D 격자에서 최소한의 노력을 들여 목표 지점까지 도달하는 경로를 찾는 문제입니다.
핵심 개념: DFS, 최단 경로

 

4. 무차별 대입 (Brute Force) 방식으로 푸는 문제

Easy 난이도

Problem 1: Subsets (LeetCode 78)
설명: 주어진 배열의 모든 부분 집합을 생성하는 문제입니다. 무차별 대입으로 모든 경우의 수를 생성합니다.
핵심 개념: Brute Force, 백트래킹

Problem 2: Permutations (LeetCode 46)
설명: 배열의 모든 순열을 생성하는 문제입니다. Brute Force로 모든 조합을 생성합니다.
핵심 개념: Brute Force, 백트래킹

Problem 3: Letter Combinations of a Phone Number (LeetCode 17)
설명: 전화번호 키패드를 사용하여 가능한 문자 조합을 찾는 문제입니다. 모든 조합을 생성합니다.
핵심 개념: Brute Force, 조합

Problem 4: Generate Parentheses (LeetCode 22)
설명: 주어진 조건을 만족하는 모든 괄호 조합을 생성하는 문제입니다. 모든 경우의 수를 탐색합니다.
핵심 개념: Brute Force, 백트래킹

Problem 5: Maximum Subarray (LeetCode 53)
설명: 배열에서 연속된 부분 배열의 최대 합을 찾는 문제입니다. Brute Force로 모든 가능한 부분 배열을 탐색합니다.
핵심 개념: Brute Force, 부분 배열

Medium 난이도

Problem 1: N-Queens (LeetCode 51)
설명: N개의 퀸을 체스판에 놓는 모든 가능한 배치를 찾는 문제입니다.
핵심 개념: Brute Force, 백트래킹

Problem 2: Combination Sum (LeetCode 39)
설명: 주어진 숫자 배열로 목표 합을 만드는 모든 조합을 찾는 문제입니다.
핵심 개념: Brute Force, 조합

Problem 3: Word Search (LeetCode 79)
설명: 2D 보드에서 주어진 단어를 찾는 문제입니다. 모든 가능한 경로를 탐색합니다.
핵심 개념: Brute Force, 백트래킹

Problem 4: Subsets II (LeetCode 90)
설명: 배열의 중복 요소를 고려하여 모든 부분 집합을 생성합니다.
핵심 개념: Brute Force, 조합

Problem 5: Palindrome Partitioning (LeetCode 131)
설명: 문자열을 분할하여 각 부분이 회문인 모든 경우를 찾는 문제입니다.
핵심 개념: Brute Force, 백트래킹

 

5. 코사라주 Kosaraju 알고리즘을 이용하는 문제

Easy 난이도

 

Problem 1: Find if Path Exists in Graph (LeetCode 1971)
설명: 방향 그래프에서 두 노드 간 경로가 존재하는지 확인하는 문제입니다. Kosaraju 알고리즘의 초기 단계인 DFS를 연습하기 적합합니다.
핵심 개념: DFS, 경로 탐색

Problem 2: Number of Connected Components in an Undirected Graph (LeetCode 323)
설명: 무향 그래프에서 연결된 컴포넌트의 수를 찾는 문제입니다. Kosaraju 알고리즘에서 역방향 탐색 없이 연결 요소를 탐색하는 연습이 가능합니다.
핵심 개념: DFS, 연결 요소

Problem 3: Strongly Connected Components in Simple Graph (유사 문제, LeetCode 미등록)
설명: 단순 방향 그래프에서 각 노드가 속한 강하게 연결된 요소를 확인합니다. Kosaraju의 기본 아이디어를 연습합니다.
핵심 개념: DFS, 방향 그래프

Problem 4: Connected Components in Graph (LeetCode 547 - Friend Circles)
설명: 방향성 없는 그래프에서 친구 관계를 통해 그룹을 찾는 문제입니다. Kosaraju의 첫 번째 DFS 탐색 연습으로 적합합니다.
핵심 개념: DFS, 무방향 그래프

Problem 5: Detect Cycle in a Directed Graph (유사 문제, LeetCode 미등록)
설명: 방향 그래프에서 사이클이 존재하는지 확인합니다. Kosaraju 알고리즘의 중간 단계를 이해하는 데 도움이 됩니다.
핵심 개념: DFS, 사이클 탐지

Medium 난이도

Problem 1: Strongly Connected Components (SCC 찾기, LeetCode와 직접 매칭된 문제 없음)
설명: 주어진 방향 그래프에서 강하게 연결된 요소를 찾는 문제입니다. Kosaraju 알고리즘으로 해결합니다.
핵심 개념: Kosaraju 알고리즘, 역방향 그래프

Problem 2: Critical Connections in a Network (LeetCode 1192)
설명: 네트워크의 중요한 연결을 찾는 문제입니다. Tarjan 알고리즘과 함께 Kosaraju 개념을 활용할 수 있습니다.
핵심 개념: Kosaraju, 그래프 탐색

Problem 3: Course Schedule II (LeetCode 210)
설명: 선수 과목 조건에 따라 수강 순서를 결정하는 문제입니다. Kosaraju 알고리즘으로 사이클을 탐지합니다.
핵심 개념: Kosaraju, 위상 정렬

Problem 4: Reconstruct Itinerary (LeetCode 332)
설명: 항공편을 기반으로 여행 일정을 재구성합니다. Kosaraju 알고리즘으로 경로 탐색을 최적화할 수 있습니다.
핵심 개념: Kosaraju, 경로 탐색

Problem 5: All Paths From Source to Target (LeetCode 797)
설명: 시작 노드에서 종료 노드까지의 모든 경로를 탐색합니다. Kosaraju 알고리즘을 활용한 변형 가능.
핵심 개념: Kosaraju, 경로 탐색