"이 네트워크에 별개 친구 그룹이 몇 개야? 이 지도에 섬이 몇 개야? 둘 다 같은 질문이야 — 끊긴 조각이 몇 개냐 — 그리고 방문-안-한-노드마다-BFS-나-DFS 하나가 답해."
연결 요소
연결 요소 (connected component)는 서로 다 닿을 수 있는 노드의 최대 그룹이야. 소셜 그래프는 큰 요소 하나 더하기 고립된 클러스터 몇 개일 수 있고; 지도는 본토랑 섬 여럿일 수 있어. 찾는 건 깔끔한 패턴이야: 모든 노드를 돌며; 방문 안 한 거 칠 때마다, 거기서 BFS 나 DFS 를 시작. 그 한 순회가 닿을 수 있는 모든 걸 통해 흘러 — 요소 하나 전체 — visited 표시하며. 새 순회를 시작해야 하는 횟수가 정확히 요소 수야. 총 O(V + E), 모든 순회를 합쳐 각 노드랑 엣지가 한 번 건드려지니까.
플러드 필: 격자에서 같은 아이디어
2D 격자는 사실 그래프야 — 각 셀이 노드, 그 이웃이 인접 셀 (위/아래/왼쪽/오른쪽). 그래서 페인트통 도구, "섬 세기", 이미지의 영역 검출이 다 플러드 필이야: 셀에서 시작해 연결된 같은-색 셀 전부로 BFS/DFS, 가면서 칠해. "섬 개수" 는 말 그대로 "땅 셀의 연결 요소 세기" — 정확히 같은 loop-and-flood 패턴, 그냥 격자 좌표가 노드고 네 이웃으로 암시적 엣지. 격자를 그래프로 알아보는 게 이 트랙 전체에서 가장 레버리지 큰 재구성 중 하나야.
연결 요소 = 아직 방문 안 한 각 노드에서 BFS/DFS 시작; 시작 횟수가 요소 수, 총 O(V+E). 격자가 그래프 그 자체 (셀 = 노드, 인접 = 엣지) 라, 플러드 필 / 섬 세기가 같은 loop-and-flood 패턴이야.
사촌: 이분 그래프 확인 (2-색칠)
같은 순회 골격이 또 다른 고전에 답해: 그래프가 이분 (bipartite) 이야 — 모든 엣지가 그룹 사이를 건너도록 (그룹 내 엣지 없음) 노드를 두 그룹으로 나눌 수 있어? BFS/DFS 를 돌리며 노드를 2-색칠하려 시도해, 각 엣지 너머로 색을 번갈아; 이미 인접한 두 노드에 같은 색을 줘야 하게 되면, 이분이 아니야. '내부 충돌 없이 두 팀으로 나눌 수 있어?' 를 모델링해 — 스케줄링, 매칭, 충돌 검출. BFS/DFS 가 알고리즘 하나가 아니라 다른 장부를 거는 골격이란 걸 상기시켜.
피파의 고백
"섬 세기" 가 날 막았는데 아빠가 물었어, "각 격자 셀이 그래프 노드면?" 문제 전체가 녹았어 — 이웃이 네 인접 셀인 연결 요소일 뿐이었어. 난 그걸 그래프 문제인데 격자 문제로 노려보고 있었어, 격자 좌표 입은. 그 뒤로, 격자를 보면, 셀을 노드로 대하는 게 어려워 보이는 퍼즐을 내가 이미 아는 BFS 로 바꾸는지 조용히 물어.
Code
연결 요소와 섬 플러드 필·python
# 연결 요소 세기: 요소당 DFS 시작 한 번.
def count_components(graph):
visited, count = set(), 0
def dfs(node):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb)
for node in graph:
if node not in visited:
count += 1 # 새 시작 = 새 요소
dfs(node)
return count
g = {"A":["B"], "B":["A"], "C":["D"], "D":["C"], "E":[]}
print("components:", count_components(g)) # 3 ({A,B}, {C,D}, {E})
# 섬 개수: 격자가 그래프; 각 땅 영역을 플러드-필.
def num_islands(grid):
if not grid: return 0
rows, cols, count = len(grid), len(grid[0]), 0
def flood(r, c):
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
return
grid[r][c] = "0" # '가라앉혀' 재방문 안 함 (visited 표시)
flood(r+1, c); flood(r-1, c); flood(r, c+1); flood(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
count += 1 # 새 땅 셀 = 새 섬
flood(r, c)
return count
ocean = [["1","1","0","0"], ["1","0","0","1"], ["0","0","1","1"]]
print("islands:", num_islands(ocean)) # 2
1 = 땅, 0 = 물인 격자에서, 땅 셀이 대각선 아니라 위/아래/왼쪽/오른쪽으로만 연결될 때, 플러드 필이 어떻게 섬을 세는지, 'visited' 집합 역할을 뭐가 하는지 묘사해. 그다음: 대각선 연결도 인접으로 치면, 답이 어떻게 바뀌고, 코드의 어느 한 부분을 편집해?
Hint
모든 셀 돌기; 방문 안 한 땅 셀에서, 카운트 올리고 연결된 영역 전체를 플러드 필 (DFS/BFS), 셀을 0 으로 가라앉혀 visited 표시. 대각선 인접은 flood 의 재귀 호출에 네 대각선 이웃 추가 — 더 적고 더 큰 섬이 나와.
Progress
Progress is local-only — sign in to sync across devices.