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에 게시됨
그래프 이론의 깊이 우선 탐색과 너비 우선 탐색
DFS와 BFS 기초
그래프 문제를 해결할 때 DFS와 BFS는 필수적인 알고리즘입니다.
DFS는 깊이 우선 탐색으로, 한 경로를 끝까지 탐색한 후 백트래킹을 통해 다른 경로를 탐색합니다.
BFS는 너비 우선 탐색으로, 현재 노드의 모든 인접 노드를 탐색한 후 다음 레벨의 노드를 처리합니다.
98. 모든 접근 가능한 경로 찾기
1번 노드에서 5번 노드로 가는 모든 경로를 찾는 문 ...
6월 23일 20:46에 게시됨
전화선 최소 비용 계산
문제 개요
농부 존은 자신의 농장에 전화선을 설치해야 한다. 그러나 통신사의 협조가 부족하여, 일부 전화선은 비용을 지불해야 한다.
전체적으로는 N (1 ≤ N ≤ 1,000)개의 전화 기둥이 있으며, 각각 1부터 N까지 번호가 매겨져 있다. 현재는 아무 기둥도 연결되어 있지 않다.
총 P (1 ≤ P ≤ 10,000)개의 기둥 쌍 사이에 전화선을 설치할 수 있으며, 나머지는 거리가 너무 ...
5월 22일 02:20에 게시됨
POJ2230 문제: 이중 방향 유일 경로 탐색 및 오일러 회로 구현
문제 개요
주어진 그래프에서 시작 정점 1에서 출발하여 모든 간선을 정방향과 역방향으로 정확히 한 번씩 지나가며, 다시 1로 돌아오는 경로를 찾는 문제이다. 이는 양방향 그래프 내에서 오일러 회로를 구성하는 전형적인 예시이다.
접근 방법
모든 간선이 두 번(정방향/역방향) 방문되며, 시작과 끝이 동일한 특성은 오일러 회로의 조건을 만족한다. 따라서 깊이 우선 ...
5월 21일 21:30에 게시됨