안녕하세요! 오늘은 대표적인 그래프 탐색(DFS/BFS) 응용 문제인 백준 3184번 '양' 문제의 풀이 과정을 공유하려고 합니다. 단순히 영역의 개수나 크기를 세는 것을 넘어, 각 영역의 구성 요소를 파악하고 비교해야 하는 흥미로운 문제였습니다. 특히 재귀 DFS를 구현하면서 겪었던 두 가지 큰 실수를 통해 많은 것을 배울 수 있었습니다.📔문제 설명https://www.acmicpc.net/problem/3184이 문제는 울타리로 둘러싸인 영역 안의 양과 늑대의 수를 세고, 양이 늑대보다 많으면 늑대가 잡아먹히고, 그렇지 않으면 양이 모두 잡아먹히는 규칙을 적용하는 문제입니다. 최종적으로 살아남은 양과 늑대의 총 수를 출력해야 합니다.🔍 접근법먼저 '울타리로 나뉜 영역'이라는 점에서 그래프의 연결 ..

📔문제 설명https://www.acmicpc.net/problem/1926안녕하세요! 오늘은 대표적인 그래프 탐색 문제인 백준 1926번 '그림' 문제 풀이 과정을 공유하려고 합니다.단순히 정답 코드를 나열하기보다, 제가 처음에 어떤 실수를 했고 그 과정에서 무엇을 배워 코드를 개선했는지를 담아보았습니다.이 문제는 주어진 도화지(2차원 배열)에서 연결된 그림의 총 개수와, 그중 가장 넓은 그림의 넓이를 출력하는 문제입니다.🔍 접근법첫 번째 접근: "모든 넓이를 저장하고 나중에 정렬하자"처음에는 이렇게 생각했습니다."DFS로 그림을 하나씩 찾을 때마다 그 넓이를 계산해서, ArrayList에 모든 그림의 넓이를 저장하자. 탐색이 다 끝나면 리스트를 내림차순으로 정렬해서 첫 번째 값을 가져오면 그게 최..

📔문제https://leetcode.com/problems/find-peak-element/description/🔍 접근법이 문제는 비의 양에 따라 물의 높이가 달라질 때, 물에 잠기지 않는 '안전 영역'의 최대 개수를 구하는 문제입니다. 여기서 '안전 영역'이란, 물에 잠기지 않은 육지들이 상하좌우로 붙어있는 덩어리를 의미합니다.문제를 처음 봤을 때, 다음과 같은 단계로 해결 전략을 세웠습니다.물의 높이 시뮬레이션: 비가 아예 오지 않은 상황부터, 가장 높은 지역이 잠길 때까지 모든 경우를 확인해야 합니다. 따라서, 물의 높이를 0부터 맵의 최대 높이까지 1씩 증가시키는 반복문이 필요합니다.영역 개수 계산: 특정 물의 높이가 정해졌을 때, 물에 잠기지 않는 육지 덩어리가 몇 개인지 세어야 합니다.최..

문제 설명https://www.acmicpc.net/problem/24480접근법기본적인 DFS 문제처럼 보이지만, 한 가지 제약 조건 때문에 흥미로운 최적화를 시도해볼 수 있었습니다.이 문제는 주어진 무방향 그래프를 깊이 우선 탐색(DFS)으로 순회하는 문제입니다. 시작 정점 R에서부터 탐색을 시작하며, 각 정점의 방문 순서를 출력해야 합니다.핵심적인 제약 조건은 다음과 같습니다.인접 정점은 내림차순으로 방문해야 한다.예를 들어, 현재 정점 5에 연결된 인접 정점이 [1, 4, 2] 라면, 우리는 [4, 2, 1] 순서로 방문해야 합니다. 이 조건 때문에 일반적인 DFS 구현 방식에 약간의 수정이 필요했습니다.List와 Collections.sort() 를 통한 첫번째 접근가장 직관적으로 떠올릴 수 있..

문제 설명https://www.acmicpc.net/problem/11724 🔍 접근법이 문제는 서로 연결된 정점들을 하나의 묶음(연결 요소)으로 보고, 그런 묶음이 총 몇 개인지를 세는 전형적인 그래프 탐색 문제입니다. 한 정점을 기준으로 더 이상 연결된 노드가 없을 때까지 탐색을 반복하면 해당 연결 요소 전체를 방문하게 되므로, 그래프 전체를 순회하면서 아직 방문하지 않은 정점이 발견될 때마다 DFS 또는 BFS 탐색을 시작하면 됩니다. DFS, BFS 모두 적용 가능하다고 판단하여 DFS로 먼저 풀어본 뒤, 동일한 방식으로 BFS도 구현해 보았습니다. 구현 과정에서 유의할 점은, 인접 행렬 기반 DFS에서 graph[x][y]가 1인 경우 y를 다음 탐색 대상 노드로 삼는다는 구조이며, 이는 다음..

문제 설명🔍 접근법주어진 2차원 격자에서 집으로 이루어진 단지의 개수와 각 단지에 속한 집의 수를 오름차순으로 출력하는 문제입니다. 연결된 집은 상하좌우로 인접한 경우로 정의되며, 그래프 탐색 문제입니다.문제를 보자마자 dfs로 해결할 수 있다는 생각이 들었습니다. 단지의 범위를 파악하려면, 한 집을 시작점으로 삼아 상하좌우로 연결된 모든 집을 탐색하며 방문 여부를 체크하고 집의 개수를 카운팅하면 됩니다. 최종적으로 단지 수와 각 단지의 집 수를 오름차순으로 출력해야 하므로, 이를 저장할 배열인 houseCnt를 선언해서 사용했습니다.💻 코드import java.io.*;import java.util.*;public class Main { static int[][] houseMap; //집 배치..

문제 설명https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:[4,5,6,7,0,1,2] if it was rotated 4 times.[0,1,2,4,5,6,7] if it was rotated 7 times.Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in th..

문제 설명https://leetcode.com/problems/find-peak-element/description/A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be st..

우선순위 큐(Priority Queue)란?높은 우선순위를 가진 요소가 먼저 처리되는 큐로, 선입선출이 기본인 일반 큐와 달리 우선순위 큐는 들어오는 순서에 관계없이 우선순위에 따라 요소가 정렬되어 처리된다.Java의 PriorityQueuejava.util.PriorityQueue는 힙(Heap) 구조를 기반으로 동작하는 큐 컬렉션이다.내부적으로 Min-Heap 구조를 사용하여, 기본적으로 가장 작은 값이 최상단 노드에 위치한다.Comparator를 전달하면 우선순위 기준을 사용자가 원하는대로 정의할 수 있다.PriorityQueue pq = new PriorityQueue(); // 기본: 오름차순PriorityQueue reversePq = new PriorityQueue(Collections.re..

문제괄호를 적절히 쳐서 식의 값을 최소로 만드는 문제🛠 사용 기술StringTokenizer(문자열)그리디 알고리즘Approach 1 ⭕🔍 접근법최소값을 만들기 위해서는 최대한 많이 값을 누적해 더해뒀다가 한번에 빼줘야한다. 즉, 뺄셈 기호(-) 이후에는 가능한 모든 수를 괄호로 묶어서 한 번에 빼주는 전략이 필요하다. 이 작업을 위해서 먼저 ‘-’ 기준으로 문자를 분리하고, 이후에 분리된 문자 내에서 ‘+’를 기준으로 값을 누적해 더한 후 전체에서 이를 빼준다.55 - 50 + 40 => 55 - (50 + 40) = -35 (최소값)=> 55 - 50 + 40 = 45뺄셈 연산이 시작되는 시점부터는 전부 빼야 하므로 먼저 ‘-’를 기준으로 분리한다.이후 1번 과정에서 분리된 문자열 내에서 괄호 안..