연결 요소와 플러드 필
섬의 개수를 세고 영역에 라벨을 붙입니다
연결 요소와 플러드 필은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
컴포넌트란 무엇인가요
연결 요소는 서로 모두 도달할 수 있는 노드들의 그룹입니다. 하나의 그래프에 여러 개의 분리된 그룹이 있을 수 있습니다. 🧩
연결 요소 세기
연결 요소의 수를 세려면 방문하지 않은 각 노드에서 탐색을 시작하세요. 새로 시작할 때마다 하나의 새로운 그룹 전체가 표시됩니다.
모든 노드 순회하기
노드를 1부터 n까지 순회하세요. 아직 방문하지 않은 노드를 발견하면 탐색해야 할 새로운 연결 요소를 찾은 것입니다.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1그룹마다 한 번 탐색하기
내부의 BFS 또는 DFS가 전체 연결 요소를 방문 표시하므로, 바깥 반복문은 다음 순회에서 해당 요소를 건너뜁니다.
격자도 그래프입니다
2차원 격자는 숨겨진 그래프입니다. 각 칸이 이웃 칸과 연결된 노드입니다. 이를 통해 고전적인 플러드 필 개념을 사용할 수 있습니다. 🗺️
네 방향
한 칸에서는 보통 위, 아래, 왼쪽, 오른쪽으로 이동합니다. 이러한 이동을 방향 벡터로 저장하면 코드가 깔끔해집니다.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]격자 범위를 벗어나지 않기
이동하기 전에 새 행과 열이 범위 안에 있는지 확인해야 합니다. 이 확인을 건너뛰면 인덱스 오류가 발생하거나 오답을 낼 수 있습니다.
if 0 <= nr < rows and 0 <= nc < cols:
pass한 영역 플러드 필하기
플러드 필은 한 칸에서 시작해 연결된 같은 유형의 모든 칸으로 퍼져 나갑니다. 페인트 통 도구와 같은 방식입니다.
섬 개수 세기
섬의 개수를 세려면 격자를 순회하면서, 새로 발견한 땅 칸마다 섬 전체를 플러드 필하고 개수에 1을 더하면 됩니다.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1영역에 라벨 붙이기
채우는 동안 각 칸에 라벨을 저장할 수 있습니다. 그러면 나중에 어떤 칸이 어느 영역에 속하는지 즉시 알 수 있습니다.
격자 크기에 선형 비례하기
각 칸을 한 번씩 방문하므로 격자에서 플러드 필을 수행하는 데는 O(행 수 × 열 수) 시간이 걸립니다. 이는 대회 제한 시간에도 충분히 맞는 속도입니다.
빠른 확인
연결 요소의 개수는 어떻게 세나요?
복습
방문하지 않은 각 노드에서 순회를 시작해 요소의 개수를 세고, 격자에서는 플러드 필을 사용해 영역에 라벨을 붙이고 섬의 개수를 셉니다. 🎉
자주 묻는 질문
“연결 요소와 플러드 필” 강의는 무료인가요?
네 — “연결 요소와 플러드 필” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“연결 요소와 플러드 필”에서 뭘 배우나요?
섬의 개수를 세고 영역에 라벨을 붙입니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“연결 요소와 플러드 필” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.