[programmers lv.2 python] '석유 시추' 파이썬 풀이 (이제 시간초과를 곁들인 ..)

https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

문제

 

제한 사항

문제 접근

bfs를 통해 석유가 있는 땅인 land[i][j]가 1인 부분을 찾으면, 그 주변의 기름 양을 상하좌우로 탐색해 1로 이어져있는 칸의 개수를 전부 찾아 count에 저장하는 방법으로 접근해봤다.

 

1차 코드 👉 실패 ❌

from collections import deque

def solution(land):
    n = len(land)
    m = len(land[0])
    visited = [[False] * m for _ in range(n)]  # 방문 처리를 위한 2차원 배열
    
    # 현재 위치에서 상하좌우로 연결된 기름 덩어리들을 탐색하는 bfs
    def bfs(x, y):
        queue = deque([(x, y)])
        visited[x][y] = True
        size = 1  # 현재 덩어리 크기를 1로 초기화
        while queue:
            cur_x, cur_y = queue.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                # 현재 x, y좌표가 유효 범위에 있는지, 방문했는지 여부 검사
                nx, ny = cur_x + dx, cur_y + dy
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if visited[nx][ny] or land[nx][ny] == 0:
                    continue
                # 방문 표시 및 연결된 석유 크기 증가
                visited[nx][ny] = True
                size += 1
                # 다음 위치를 큐에 추가
                queue.append((nx, ny))
        return size
    
    max_oil = 0
    # 모든 석유 덩어리 크기 계산 (석유가 있고 방문하지 않았으면 bfs 호출)
    # 각 열에 대해 최대 석유량 계산
    for col in range(m):
        current_oil = 0
        for row in range(n):
            if land[row][col] == 1 and not visited[row][col]:
                # 새로운 덩어리 발견
                chunk_size = bfs(row, col)
                current_oil += chunk_size
        max_oil = max(max_oil, current_oil)
    return max_oil

 

1차로 위와 같은 코드를 작성했는데, 통과될 것이라고 예상했으나 결과는 처참한 실패

뭐가 틀렸을까 고민하다가 방문 배열(visited 배열)을 초기화해줘야 한다는 걸 깨달았다.

 

즉, 지금의 코드는

경우의 수를 1, 2번으로 생각해보면 (저 갈색의 선이 시추관임 ,, 아무튼 시추관임)

방문 배열을 각 열에 대해 최대 석유량을 계산하는 코드에서 visited 방문 배열을 초기화 하고 있지 않기 때문에

1번에서 bfs를 통해 최대 석유량이 10개라고 판단하고 석유 덩어리들에 방문 처리를 해준 후

2번에서 bfs를 돌리면 여기서 또한 최대 석유량이 10개가 나와야 하는데, 1번에서 방문 처리 해 준 배열이 초기화 되어 있지 않기 때문에 이미 방문한 석유 덩어리라고 판단하고 누락시켜 결과는 0이 나와버리는 것이다.

 

2차 코드👉 실패 ❌

그래서 1번 코드에서의 문제점을 개선한 visited 배열을 초기화해주어 돌려봤더니 테스트 코드에서는 모두 통과했다. 그래서 호기롭게 오 당연히 패스하겠지 ..? 하고 결과 채점하기 버튼을 누른 나

    max_oil = 0
    # 모든 석유 덩어리 크기 계산 (석유가 있고 방문하지 않았으면 bfs 호출)
    # 각 열에 대해 최대 석유량 계산
    for col in range(m):
        current_oil = 0
        visited = [[False] * m for _ in range(n)]   # 방문 처리 배열 초기화 (이 부분 추가!)
        for row in range(n):
            if land[row][col] == 1 and not visited[row][col]:
                # 새로운 덩어리 발견
                chunk_size = bfs(row, col)
                current_oil += chunk_size
        max_oil = max(max_oil, current_oil)
    return max_oil

멸망

효율성 테스트에서 시간 초과로 싹 다 걸려버렸다.

이유가 뭘까?

 

위 코드는 한 번 시추관이 내려올 때 마다, visited 배열을 초기화하면서 bfs를 돌린다.

즉, 매번 bfs로 전체 탐색을 반복하면서 MAX 값을 찾으니까 시간 복잡도가 매우 비효율적인 코드였던 것 ..! 

 

이런 불필요한 재연산을 어떻게 줄일 수 있을까. 아무리 고민해도 답을 모르겠어서 구글링 찬스를 썼다.

bfs로 푸신 분들 중에서 set 자료구조를 이용하신 분들을 보고 2차 코드를 set 자료구조를 사용해서 리팩토링 해 봤다.

 

3차 코드 👉 성공 ⭕

from collections import deque

def solution(land):
    n = len(land)
    m = len(land[0])
    result = [0 for _ in range(m)]  # 각 열의 석유 총량 저장
    visited = [[0] * m for _ in range(n)]  # 방문 배열
    
    dx = [-1, 1, 0, 0]  # 상하좌우 이동
    dy = [0, 0, -1, 1]
    
    def bfs(pos):
        x, y = pos
        cnt = 1  # 현재 덩어리 크기
        visited[x][y] = 1  # 방문 처리
        oil_covered = set()  # 방문한 열을 저장
        oil_covered.add(y)  # 시작 열 추가
        
        queue = deque([pos])
        while queue:
            cx, cy = queue.popleft()
            for i in range(4):
                nx, ny = cx + dx[i], cy + dy[i]
                # 유효한 좌표인지 검사
                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and land[nx][ny] == 1:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
                    cnt += 1
                    oil_covered.add(ny)  # 새로운 열 추가
        
        # BFS로 찾은 덩어리 크기를 모든 열에 추가
        for col in oil_covered:
            result[col] += cnt
    
    # 모든 땅 탐색
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and not visited[i][j]:
                bfs((i, j))
    
    # 가장 큰 석유량 반환
    return max(result)

 

2번째 코드와 3번째 코드를 비교해보자.

 

2차 코드는 각 열(column)을 탐색할 때마다 방문 배열을 새로 초기화해서, 중복된 계산이 발생하고 이미 처리한 영역도 다시 탐색한다는 문제가 있었다.

즉, 쉽게 설명하면 석유 덩어리가 여러 열에 걸쳐 있는 경우, 모든 열마다 이미 탐색했던 석유 덩어리를 다시 탐색한다는 거다.

 

set() 의 사용

BFS 탐색에서 set()을 사용해 연결된 열(column)들을 추적(?)하도록 구현했다.

1. 시작 좌표에서 모든 연결된 석유 덩어리를 탐색한다.
2. 덩어리가 여러 열에 걸쳐 있을 경우, 해당 열의 번호를 set에 저장한다.
3. set은 중복 값을 자동으로 제거하므로, 같은 열을 여러 번 처리하지 않는다.
4. BFS가 끝난 뒤, 한 번에 관련 열들의 석유량을 업데이트한다.

성공 ~

 

결론

결론을 말하면!

덩어리가 여러 열에 걸쳐 있어도 중복 계산을 방지할 수 있도록 set() 메서드를 사용해서 👉 BFS를 덩어리별로 딱 한 번만 수행하도록 만들어 시간 복잡도를 개선했다는 것이 결론 😀

 

• 기존 코드: 열마다 방문 배열 초기화와 BFS 호출로 인해 중복 탐색 발생.
  • 시간 복잡도: O(m * n * m)
• 리팩토링 코드: 방문 배열을 재사용하며, BFS를 통해 모든 열의 석유량을 한 번에 업데이트.
  • 시간 복잡도: O(n * m)

 

왜 lv.2 짜리 문제였는지 이해할 수 있었던 문제였다. DFS로도 함 풀어봐야지