PostsSeriesLabsAlgo

그래프 탐색

연결 요소

섬이 몇 개인지 세기

노란 칸은 땅이고 빈 칸은 바다입니다. 땅이 이어진 덩어리가 섬이에요. 섬이 몇 개일지 먼저 고르고 땅을 눌러 섬을 하나씩 칠하며 세어 보세요.

노란 칸은 땅이고 빈 칸은 바다예요. 땅이 이어진 덩어리가 섬입니다. 섬이 모두 몇 개일까요?

센 섬 0개

내 예상 개 · 실제 3개 → 달랐어요

섬 1: 3칸 → 섬 2: 3칸 → 섬 3: 2칸땅 8칸을 칸마다 센 게 아니라 번지기를 시작한 횟수 3번을 셌습니다.

  • 한 번 번지기 시작하면 — 이어진 땅이 모두 칠해졌다
  • 섬 수 — 번지기를 새로 시작한 횟수와 같다

한 덩어리로 이어진 칸 묶음 = 연결 요소(connected component)

번지는 일은 앞에서 본 BFS(가까운 칸부터 한 겹씩)나 DFS(막다른 길까지 파고들기)가 합니다. 이 페이지 코드는 큐로 번지는 BFS 를 씁니다.

이어졌다는 건 위·아래·왼쪽·오른쪽이다

  • 방금 겪은 대각선 — 대각선으로만 닿은 땅은 번지지 않았다. 그래서 다른 섬이다. 대각선까지 이으면 이 지도는 2개가 된다
  • 센 땅은 표시해 둔다 — 칠한 땅을 또 만나도 세지 않아야 한다. 표시가 없으면 같은 섬을 두 번 센다
  • 칸마다 한 번씩만 본다 — 칸이 N개면 걸리는 시간도 N에 비례한다. 100만 칸 지도도 직접 재 보니 1초쯤 걸렸다(Python 3.14, 컴퓨터마다 다르다)

코드는 땅을 만날 때마다 번지기를 한 번 시작한다

큐 = 먼저 넣은 게 먼저 나오는 줄. 위에서 번진 것과 같은 지도입니다. (r, c) 는 위에서 r번째 줄, 왼쪽에서 c번째 칸이고 0부터 셉니다.

다음을 눌러 한 줄씩 넘기며 칠해지는 칸과 큐를 보세요. 바다 칸은 건너뛰고 땅인 칸만 보여 줍니다.

센 섬 0개

큐← 꺼낸다
  1. 비어 있음
넣는다 →

다음을 눌러 한 줄씩 넘겨 보세요

count = 0 len(seen) = 0

count_islands.py
  1. 1from collections import deque
  2. 2
  3. 3def count_islands(grid):
  4. 4 rows, cols = len(grid), len(grid[0])
  5. 5 seen = set()
  6. 6 count = 0
  7. 7 for r in range(rows):
  8. 8 for c in range(cols):
  9. 9 if grid[r][c] == 1 and (r, c) not in seen:
  10. 10 count += 1
  11. 11 seen.add((r, c))
  12. 12 q = deque([(r, c)])
  13. 13 while q:
  14. 14 cr, cc = q.popleft()
  15. 15 for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
  16. 16 nr, nc = cr + dr, cc + dc
  17. 17 if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in seen:
  18. 18 seen.add((nr, nc))
  19. 19 q.append((nr, nc))
  20. 20 return count
0 / 32
  • seen — 이미 센 칸 모음. 칠하는 칸마다 여기에 넣는다
  • count += 1 — 안 센 땅을 만났을 때만 오른다. 새 섬이라는 뜻이다
  • while q: — 큐가 빌 때까지 이웃 땅을 칠하며 번진다

대각선으로 닿은 땅도 이어진 것으로 세면(8방향) 이 지도의 섬은 몇 개일까요?

섬 세기에서 틀리는 자리

  • seen.add((nr, nc)) 를 지우면 — 큐가 끝나지 않는다. 두 칸이 서로를 번갈아 큐에 넣는다. 1000번을 꺼내도 계속 돌았다
  • 바깥 not in seen 을 지우면 — 같은 섬의 칸마다 count 가 올라서 3이 아니라 8이 나온다
  • 경계 검사를 지우면 — 통째로 지우면 IndexError: list index out of range 가 난다. 0 <= 만 지우면 에러가 안 나서 더 위험하다. 음수 인덱스는 맨 뒤 칸을 읽고(grid[-1] 은 맨 아래 줄), 이 지도에서는 우연히 답이 같았다
  • 재귀로 번지면 — 100×100 지도가 전부 땅이면 RecursionError: maximum recursion depth exceeded 가 난다. 같은 지도를 큐로 번지면 섬 1개로 끝난다
  • 대각선까지 이으려면 — 이웃 방향 4개를 8개로 늘린다. 이 지도는 2개가 된다

문제에서 이 말이 보이면

덩어리가 몇 개인가섬·영역서로 이어진 것끼리 묶는다

다음 장에서는 길마다 걸리는 시간이 다를 때의 최단 거리, 다익스트라를 봅니다.