석유 시추

프로그래머스 석유 시추 문제 풀이 포스팅용입니다 👇

---

# 🛢️ [프로그래머스] 석유 시추 - BFS 덩어리 탐색 문제풀이 (Python)

---

## 📘 문제 설명

2차원 리스트 `land`가 주어집니다. 각 칸은 다음을 의미합니다.

- `1`: 석유가 있는 땅
- `0`: 석유가 없는 땅

시추관은 위에서 아래로 **하나의 열(column)** 을 선택해서 수직으로 시추할 수 있습니다.  
이때, 해당 열과 연결된 석유 덩어리를 전부 채굴할 수 있습니다.

> ⚠️ **석유는 상하좌우로 연결된 1들의 묶음**이며,  
> 시추관이 뚫린 열에 연결된 모든 석유를 채굴합니다.

---

## ❌ 내가 처음 작성한 코드

```python
from collections import deque

def solution(land):
    n = len(land)
    m = len(land[0])
    answer = 0
    dx = [0, 1, -1, 0]
    dy = [1, 0, 0, -1]

    for i in range(m):  # 열 단위로 탐색
        oil = deque()
        visited = [[0] * m for _ in range(n)]
        for j in range(n):
            if land[j][i] == 1:
                oil.append((j, i))

        cnt = 0
        while oil:
            x, y = oil.popleft()
            visited[x][y] = 1
            cnt += 1
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0 and land[nx][ny] == 1:
                    visited[nx][ny] = 1
                    oil.append((nx, ny))

        answer = max(answer, cnt)
    return answer

---

❗ 이 코드의 문제점

문제	설명
visited를 열마다 초기화	덩어리를 여러 열에서 중복 탐색하여 석유량이 중복 계산됨
열 단위로 BFS 시작	연결된 석유 덩어리를 덩어리 단위가 아닌, 열 단위로 나눠 탐색하여 정확한 계산 불가

결과적으로, 같은 석유 덩어리를 여러 번 세는 구조가 되므로 정답이 틀어지게 됩니다.

---

✅ 정답 풀이: 덩어리 단위로 BFS 탐색

핵심은 다음과 같습니다:

1. 모든 1을 BFS로 탐색하며 덩어리(그룹)를 나눈다
2. 각 그룹의 석유량과 해당 그룹이 포함된 열(column)을 저장한다
3. 열마다 연결된 그룹의 석유양을 더하고, 그 중 최대값을 구한다

---

✅ 정답 코드 (Python)

from collections import deque

def solution(land):
    n = len(land)
    m = len(land[0])

    visited = [[0] * m for _ in range(n)]
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    group_id = 1
    group_oil = dict()

    def bfs(sx, sy, group_id):
        q = deque([(sx, sy)])
        visited[sx][sy] = group_id
        oil_amount = 1

        while q:
            x, y = q.popleft()
            for d in range(4):
                nx, ny = x + dx[d], y + dy[d]
                if 0 <= nx < n and 0 <= ny < m:
                    if land[nx][ny] == 1 and visited[nx][ny] == 0:
                        visited[nx][ny] = group_id
                        oil_amount += 1
                        q.append((nx, ny))

        group_oil[group_id] = oil_amount

    # 1. 전체 지도 돌면서 그룹화
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and visited[i][j] == 0:
                bfs(i, j, group_id)
                group_id += 1

    # 2. 각 열마다 연결된 그룹 ID만 뽑아서 석유량 합산
    answer = 0
    for col in range(m):
        connected_groups = set()
        for row in range(n):
            gid = visited[row][col]
            if gid > 0:
                connected_groups.add(gid)
        total = sum(group_oil[gid] for gid in connected_groups)
        answer = max(answer, total)

    return answer

---

🔍 예시로 이해하기

land = [
  [1, 0, 0, 1],
  [1, 1, 0, 0],
  [0, 1, 1, 1]
]

• 덩어리 A (group 1): (0,0)-(1,0)-(1,1)-(2,1) → 열 0, 1
• 덩어리 B (group 2): (0,3)-(2,2)-(2,3) → 열 2, 3

열 번호	연결된 그룹	석유 총량
0	1, 2	4 + 3 = 7
1	1	4
2	2	3
3	2	3

👉 최종 정답: 7

---

✅ 핵심 요약

• 시추는 열 단위로 하지만 석유는 덩어리 단위로
• 열마다 석유를 중복 계산하지 않도록 전역 visited + 그룹 관리
• 덩어리를 그룹핑해서 열-그룹 연결 구조로 정답 계산

---

📌 마무리

처음엔 "열에서 BFS 시작해서 석유를 센다"는 아이디어로 접근했지만,
덩어리를 중복 탐색하게 되어 틀린 결과가 나왔습니다.

문제의 본질을 파악하고 덩어리 단위로 처리하는 방식으로 구조를 바꾸면서
정확하고 효율적인 풀이가 가능해졌습니다.

---