🔴 문제 개요

문제 원문 - 프로그래머스(Programmers)

🚀 난이도 : LEVEL2

위 그림처럼 격자 내 석유가 매장되어 있고, 한 번의 수직 시추로 가장 많은 석유를 뽑을 수 있는 경우의 석유량을 도출해내면 됩니다.

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
  • land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
  • land[i][j]는 0 또는 1입니다.
  • land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.
• 정확성 테스트 케이스 제한사항
  • 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100
• 효율성 테스트 케이스 제한사항
  • 주어진 조건 외 추가 제한사항 없습니다.

🟠 Solution(흔한 접근, 효율성 TLE)

그래프 탐색에 익숙하신 분들이라면, 완전탐색을 통한 BFS/DFS를 수행하여 답을 도출해낼 수 있다는 것을 빠르게 파악하셨을 것 같습니다. 가장 쉽게 생각할 수 있는 접근법이며, 솔루션은 다음과 같습니다.

from typing import List
from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def bfs(r: int, c: int, matrix: List[List[int]], visited: List[List[bool]]) -> int:
    """
    코드 생략
    (r, c)를 시작 좌표로, BFS 탐색을 통해 뽑을 수 있는 석유량 계산
    """            
    return result
            

def solution(land: List[List[int]]) -> int:
    N, M = len(land), len(land[0])
    answer = 0
    
    # 컬럼 별 완전탐색
    for c in range(M):
        visited = [[False for _ in range(M)] for _ in range(N)]
        result = 0
        for r in range(N):
            if not visited[r][c] and land[r][c] == 1:
                result += bfs(r, c, land, visited)
                
    	# 컬럼별 max 석유 시추량 업데이트
        if answer < result:
            answer = result
            
    return answer

이처럼 컬럼별로 완전탐색하여, 매 컬럼 별 max 석유 시추량을 업데이트해주면 되는 전형적인 BFS solution입니다. 다만, 이때 정확성 테스트는 통과할 수 있어도, 효율성 테스트는 통과할 수 없습니다.

제한 사항을 보면, 효율성 테스트시 격자의 크기는 최대 500x500입니다. 최악의 경우 매 칸마다 BFS탐색을 수행한다 했을 때, 500x500x500번 이상의 연산이 수행되어 제한시간 내에 테스트를 통과할 수 없습니다. (Python 언어의 제한시간이 명시되어 있지 않아 정확한 연산량을 계산할 수 없었습니다.)

🟡 Solution(효율성 개선)

잘 생각해보면, 매 컬럼마다 다시 BFS를 돌리지 않아도 됩니다. 특정 석유 덩어리에서 BFS를 하는 과정에서 우리는 좌표 정보를 알 수 있기 때문에 BFS 시에 거치는 컬럼 좌표를 따로 저장하여, 탐색이 끝나고 해당 컬럼들에 시추량을 더해주면 됩니다. 이 경우, 각 석유 덩어리에 대해 한 번의 BFS만 수행되게 되므로 무난하게 테스트를 통과할 수 있습니다.

개선한 점은 다음과 같습니다.
1. BFS 실행 전, column별 BFS 결과를 합산할 cols 리스트를 정의하였습니다.
2. BFS시 현재 탐색 중인 컬럼 좌표(x 좌표)를 cols_set 집합에 저장합니다.
3. BFS 종료 후 집합 내 컬럼 인덱스에 해당하는 cols의 원소에 BFS 결과를 합산합니다.
4. NxM의 격자 탐색이 끝나면 cols에서 최댓값을 정답으로 반환합니다.

전체 코드

from typing import List
from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]


def bfs(r: int,
        c: int,
        matrix: List[List[int]],
        visited: List[List[bool]],
        cols: List[int]) -> None:
    """
    :param r: BFS 시작 행 번호
    :param c: BFS 시작 열 번호
    :param matrix: 격자
    :param visited: 격자 특정 칸 방문장여부
    :param cols: 각 column별 BFS결과 저장
    :return: None
    
    (r, c)를 시작으로 석유가 있는 칸을 BFS한 결과를 cols에 거치는 column별로 저장한다.
    """

    N, M = len(matrix), len(matrix[0])
    queue = deque([(r, c)])
    visited[r][c] = True
    result = 0

    cols_set = set()    # 해당 BFS가 거치는 column 저장

    while queue:
        y, x = queue.popleft()
        cols_set.add(x)
        result += 1

        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]

            if 0 <= ny < N \
                    and 0 <= nx < M \
                    and not visited[ny][nx] \
                    and matrix[ny][nx] == 1:
                queue.append((ny, nx))
                visited[ny][nx] = True

    # 거치는 column에 BFS 결과 더해주기
    for col in cols_set:
        cols[col] += result

    return


def solution(land: List[List[int]]) -> int:
    N, M = len(land), len(land[0])

    visited = [[False for _ in range(M)] for _ in range(N)]
    cols = [0 for _ in range(M)]    # 각 column별 BFS 결과 저장

    for r in range(N):
        for c in range(M):
            if land[r][c] == 1 and not visited[r][c]:
                bfs(r, c, land, visited, cols)

    return max(cols)    # 최대 결과 column 반환

📚 고찰

쉽게 접근할 수 있는 문제일수록 바로 구현하기 전, 효율성을 개선할 여지가 있는지를 파악해야 합니다. 특히 이 때 제한 사항에 유의하여 연산량을 미리 파악할 수 있으면 미리 개선할 점을 고려하여 솔루션의 backborn을 구성하기 쉬워집니다. (Python의 경우 1초에 약 2천만 번 연산)

🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!

✏️ Algorithm Study
본 문제의 다른 풀이 및 피드백, 전체 문제 풀이 순서는 위 알고리즘 스터디 Repository에서도 확인 가능합니다.