C++ BFS 알고리즘을 활용한 FloodFill 문제 해결
FloodFill 유형 문제 분석
1. 벽과 문 거리 계산
문제 설명:
2D 그리드에서 방 상태를 나타내는 rooms 배열이 주어집니다. 각 셀은 벽(-1), 문(0), 빈 방(2³¹-1) 중 하나입니다. 모든 빈 방에 대해 가장 가까운 문까지의 거리를 계산하세요.
제약 조건:
m == rooms.length
n == rooms[i].length
1 ≤ m, n ≤ 250
해결 전략:
모든 문의 위치를 큐에 초기 삽입합니다. BFS를 ...
6월 25일 00:44에 게시됨
너비 우선 탐색(BFS)으로 Flood Fill 유형 문제 풀이
너비 우선 탐색(BFS)은 그래프나 그리드에서 최단 경로를 찾거나 연결된 구성 요소를 탐색하는 데 자주 사용되는 강력한 알고리즘입니다. Flood Fill 알고리즘은 특정 시작점에서 인접한 모든 요소들을 탐색하여 변경하는 과정으로, BFS의 대표적인 응용 사례 중 하나입니다. 이 글에서는 BFS를 활용하여 Flood Fill 계열의 문제들을 해결하는 방법을 다룹니다.
1. 이미지 ...
6월 23일 03:44에 게시됨
문자열 변환 문제(무향 그래프 중복 제거)
문자열 변환 문제
문제 설명
이 문제는 문자열 A와 B, 그리고 최대 6개의 문자열 변환 규칙을 주고, A를 B로 변환하는 최소 단계 수를 찾는 문제입니다. 각 변환 규칙은 "A1→B1" 형식으로 주어집니다.
예를 들어, A가 "abcd", B가 "xyz"이고 변환 규칙이 다음과 같다면:
abc→xu
ud→y
y→yz
이 경우, A는 3번의 변환을 통해 B로 변환될 수 ...
6월 21일 20:45에 게시됨
세 컵 콜라 분배 문제의 BFS 해법
문제 개요
세 개의 컵 용량이 각각 S, N, M(S = N + M, 양의 정수)으로 주어집니다. 처음에 S 용량 컵은 가득 차 있고, 나머지는 비어 있습니다. 컵 간 콜라를 서로 붓는 작업을 최소화하여 두 컵에 S/2의 콜라가 담긴 상태를 만드는 것이 목표입니다. 단, S가 홀수이면 해결 불가능합니다.
BFS 접근 방식
각 컵의 현재 상태를 (a, b, c)로 표현하여 BFS를 적용합니다. ...
6월 8일 21:07에 게시됨
그래프 순회 알고리즘: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)
너비 우선 탐색 (Breadth-First Search, BFS)
너비 우선 탐색은 시작 정점으로부터 가까운 노드를 우선적으로 탐색하는 알고리즘으로, 이진 트리의 레벨 순회(Level-order traversal) 방식과 유사합니다. 탐색 과정에서 큐(Queue)를 사용하여 정점을 관리하고, 방문 여부를 기록하기 위한 불리언 배열을 사용합니다.
시작 정점을 큐에 넣고 방문 처리한 뒤, 큐가 ...
6월 8일 16:40에 게시됨
삼차원 던전 탈출 문제 - BFS 알고리즘 풀이
문제 출처
백준 온라인 저지(BOJ) 2251번, POJ 2251, 정보학奥賽一本通
알고리즘 분류
너비 우선 탐색(BFS), 삼차원 그래프 탐색
문제 설명
삼차원 던전에서 가장 빠른 탈출 경로를 찾아야 한다. 던전은 여러 층으로 구성되어 있으며, 각 층은 행과 열로 구분되는 单位 격자로 이루어져 있다.
각 이동은 北, 南, 東, 西, 上, 下 중 하나의 방향으로 정확히 한 칸 이동하 ...
6월 8일 03:29에 게시됨
ABC348 문제 풀이
A 문제
주어진 수 만큼 "oox" 패턴을 반복 출력하고, 나머지에 따라 추가 문자를 붙인다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int full_cycles = n / 3;
for (int i = 0; i < full_cycles; ++i) {
cout x[i] >> y[i];
}
for (int i = 1; i color;
if (seen[col ...
6월 7일 23:02에 게시됨
BFS를 활용한 최단경로 탐색 및 상태 공간 탐색
Breadth-First Search (BFS) 개요
BFS는 트리 또는 그래프 구조에서 노드를 너비 우선으로 탐색하는 알고리즘입니다. 시작점에서 출발하여, 현재 레벨의 모든 인접 노드를 먼저 방문한 후 다음 레벨로 이동합니다. 이 방식은 '원형 확장'과 유사하며, 최단 경로 문제에 적합합니다. 왜냐하면 같은 거리의 노드들이 모두 한 번에 처리되기 때문입니다.
주요 특징
최단 경 ...
5월 31일 15:35에 게시됨
上海市计算机학회 경시대회 2023년 8월 월례丙조 T5 격자 경로
T5 격자 경로
메모리 제한: 256 Mb | 시간 제한: 1000 ms
문제 설명
n × m개의 격자로 이루어진 지도가 주어진다. 각 격자에는 지형 정보가 있다:
일부 격자는 벽(#)이며, 통과할 수 없다.
일부 격자는 길(.)이며, 통과할 수 있다.
좌상단 격자에서 시작하여 우하단 격자까지 최단 거리로 도착하는 경우의 수를 구해야 한다. 이동 중에는 벽 격자로 진입할 수 없으며, ...
5월 31일 13:16에 게시됨
이진 트리의 핵심 개념과 활용
이진 트리는 계층적 데이터를 표현하는 대표적인 비선형 자료구조로, 각 노드가 최대 두 개의 자식을 가지는 구조를 말합니다. 분할 정복의 "반으로 나누기" 전략을 직관적으로 구현할 수 있어 다양한 알고리즘의 기반이 됩니다.
노드 구조와 기본 개념
이진 트리의 기본 단위인 노드는 데이터 값과 두 개의 자식 참조로 구성됩니다. 부모-자식 관계를 통해 하위 트리가 ...
5월 23일 05:59에 게시됨