얼음 얼려 먹기 문제 정리 | DFS로 연결 요소 개수 세는 방법

이 문제의 핵심은 연결 요소 개수 세는 DFS 라는것이다.

핵심은 어렵지 않다.

값이 0인 칸을 만나면 DFS로 연결된 0을 전부 방문 처리하고, 그 DFS가 한 번 끝날 때마다 개수를 1 올리면 된다.

처음 보면 얼핏 미로 탐색이랑 비슷해 보이는데,

막상 풀어보면 결이 좀 다르다.

미로 탐색은 시작점이 정해져 있고 최단거리를 구하는 문제였다면,

이 문제는 출발점이 고정되어 있지 않고, 전체 격자를 돌면서 새로운 덩어리를 몇 개 찾는지 세는 문제다.

즉 이 문제는

DFS/BFS 자체보다 “탐색을 전체 격자 순회 안에 한 번 더 감싸는 구조”를 이해하는 게 핵심이다.

---

🔗 문제 링크

이코테 예제 - 얼음 얼려 먹기

(백준/프로그래머스 공식 문제는 아니고, 탐색 기본 문제로 자주 나오는 유형)

참고 설명 링크

https://hongs-coding.tistory.com/52#google_vignette

---

문제 정리

문제 조건을 정리하면 이렇다.

• 0은 구멍이 뚫린 부분
• 1은 칸막이
• 상하좌우로 연결된 0은 하나의 덩어리로 본다
• 얼음 틀 전체에서 총 몇 개의 덩어리가 있는지 구하면 된다

즉, 이 문제는 결국

격자에서 연결된 0 영역이 몇 개인지 세는 문제다.

여기서 바로 봐야 하는 건 두 가지다.

• 최단거리 문제가 아니다
• 시작점이 하나가 아니다

그래서 이 문제는

미로 탐색처럼 BFS 한 번 돌리고 끝나는 구조가 아니라,

전체를 순회하면서 DFS를 여러 번 호출하는 구조로 가야 한다.

---

✅ 핵심 아이디어

이 문제는 아래 흐름으로 풀면 된다.

1. 전체 격자를 이중 for문으로 다 돈다
2. 0인 칸을 만나면 DFS 시작
3. DFS 안에서 연결된 0들을 전부 1로 바꾼다
4. DFS가 한 번이라도 시작됐으면 덩어리 1개를 찾은 거니까 result += 1

정리하면 이거다.

• 0을 만나면
• 그 연결된 덩어리를 DFS로 싹 밀고
• 개수 1 증가

이 문제는 BFS로 풀어도 되긴 하는데,

구조상 DFS 재귀가 더 직관적이다.

---

정답

n, m = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False

    if graph[x][y] == 0:
        graph[x][y] = 1

        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)

        return True

    return False

result = 0

for i in range(n):
    for j in range(m):
        if dfs(i, j):
            result += 1

print(result)

---

생각해야 하는 부분

이 문제는 DFS를 아는지보다

언제 DFS를 시작해야 하는지를 보는 게 더 중요하다.

---

1. 출발점이 하나가 아니다

미로 탐색은 (0, 0)에서 시작하면 됐다.

근데 이 문제는 그런 식으로 출발점이 고정되어 있지 않다.

즉, 전체 격자를 다 돌면서

• 여기가 0인가?
• 아직 안 뒤집힌 새로운 덩어리인가?

를 계속 봐야 한다.

그래서 바깥에 이중 for문이 붙는다.

for i in range(n):
    for j in range(m):
        if dfs(i, j):
            result += 1

이게 이 문제 핵심 구조다.

---

2. DFS는 “개수 세기”보다 “한 덩어리 밀기” 역할이다

처음 보면 DFS가 개수를 세는 것처럼 보일 수도 있는데,

실제로 DFS가 하는 일은 그게 아니다.

DFS는 그냥

현재 시작점과 연결된 0들을 전부 방문 처리하는 역할이다.

즉 DFS는 이렇게 생각하면 된다.

• 지금 (x, y)가 0이면
• 이 칸을 1로 바꾸고
• 상하좌우 4방향으로 이어진 0도 전부 처리

그러면 DFS 한 번이

곧 얼음 덩어리 하나 전체를 처리하는 작업이 된다.

---

3. 방문 처리는 따로 배열 안 두고 graph를 바로 바꿔도 된다

이 문제는 별도 visited 배열 없이도 충분하다.

graph[x][y] = 1

이 한 줄이 곧 방문 처리다.

어차피 원래 0과 1만 있는 문제니까,

0을 1로 바꿔버리면 “이미 처리한 칸”이라는 의미까지 같이 갖게 된다.

이렇게 하면 구조가 훨씬 단순해진다.

---

4. 이 문제는 최단거리 문제가 아니다

이걸 먼저 구분해야 한다.

이 문제는 “몇 칸 만에 가는가”를 묻지 않는다.

그냥 덩어리가 몇 개인지를 묻는다.

그래서 미로 탐색처럼 거리 누적이 필요 없고,

BFS 레벨 탐색도 필요 없다.

그냥 연결된 곳을 전부 방문 처리만 하면 된다.

즉,

• 미로 탐색 → 거리 기록 필요
• 얼음 얼려 먹기 → 방문 처리만 필요

이 차이가 있다.

---

예외처리 / 주의할 점

⚠️ 1. 범위 체크는 DFS 맨 앞에서 바로 해야 한다

격자 문제는 항상 이게 먼저다.

if x < 0 or x >= n or y < 0 or y >= m:
    return False

범위 밖이면 더 볼 것도 없이 끝낸다.

이걸 뒤로 빼면 인덱스 에러 나기 쉽다.

---

⚠️ 2. 0일 때만 DFS를 확장해야 한다

이 문제에서 의미는 명확하다.

• 0 → 구멍, 탐색 가능
• 1 → 막힌 칸, 또는 이미 방문 처리된 칸

그래서 DFS 안에서도

graph[x][y] == 0일 때만 탐색을 이어가야 한다.

if graph[x][y] == 0:
    graph[x][y] = 1
    ...

괜히 1인 칸까지 재귀를 계속 걸면 구조가 꼬인다.

---

⚠️ 3. DFS가 True를 리턴하는 의미를 정확히 봐야 한다

이 줄이 중요하다.

if dfs(i, j):
    result += 1

여기서 True는

“새로운 덩어리를 하나 찾았다”는 뜻이다.

즉,

• dfs(i, j)가 False → 이미 1이거나 범위 밖, 새 덩어리 아님
• dfs(i, j)가 True → 새로운 0 덩어리를 처리 시작함

그래서 True일 때만 개수를 올리는 거다.

이 반환값 의미를 헷갈리면

왜 result가 증가하는지 감이 안 잡힌다.

---

내 시행착오

이 문제에서 내가 처음 헷갈린 건 크게 세 가지였다.

---

1. 미로 탐색처럼 시작점을 하나만 찾으려고 했다

탐색 문제를 연달아 보다 보면

무의식적으로 “시작점이 어딘데?”부터 찾게 된다.

근데 이 문제는 그게 아니다.

시작점이 하나로 정해진 문제가 아니라,

모든 칸이 시작점 후보다.

이걸 늦게 보면 구조가 안 잡힌다.

---

2. DFS가 개수를 직접 세는 줄 알았다

처음엔 DFS 안에서 뭔가 개수를 세야 하나 싶었다.

근데 이 문제에서 DFS는 카운터가 아니다.

그냥 한 덩어리를 전부 방문 처리하는 역할이다.

개수는 DFS 바깥에서 센다.

• DFS 한 번 시작됨
• 덩어리 하나 처리됨
• result += 1

이 흐름이 훨씬 명확했다.

---

3. 방문 배열을 따로 둘까 고민했다

처음엔 visited 배열을 따로 둘까 싶었는데,

이 문제는 그렇게까지 갈 필요가 없었다.

어차피 값이 0 / 1 두 개뿐이라

0을 1로 바꾸는 것만으로 방문 처리까지 끝난다.

즉,

graph[x][y] = 1

이 방식이 제일 단순하다.

---

한 줄 정리

이 문제는 DFS로 연결된 0 덩어리를 전부 방문 처리하고, DFS가 시작될 때마다 개수를 1 올리는 연결 요소 문제다.