[프로그래머스 PCCP 모의고사 2-2번] 시추관

 

from collections import deque

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

    n = len(land)
    m = len(land[0])
    
    visited = [[False]*m for _ in range(n)]
    total = [0]*m
    
    def bfs(x,y):
        
        if visited[x][y]:
            return
        
        visited[x][y] = True
        
        y_list = set()
        count = 0
        
        queue = deque([(x,y)])
        
        while queue:
            temp_x,temp_y = queue.popleft()
            count += 1
            y_list.add(temp_y)
            
            for i in range(4):
                nx = temp_x + dx[i]
                ny = temp_y + dy[i]
                
                if 0 <= nx < n and 0 <= ny < m and land[nx][ny] == 1 and not visited[nx][ny]:
                    queue.append((nx,ny))
                    visited[nx][ny] = True

        for i in y_list:
            total[i] += count
            
    
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and land[i][j] == 1:
                bfs(i,j)

    return max(total)

 

본 문제는 각 열을 기준으로 가장 많은 석유량(인접 영역)을 차지할 수 있는 경우의 수를 구하고, 해당 경우의 최대 석유량을 구하는 문제이다.

 

처음에는 모든 열을 순회하면서 DFS로 인접한 석유영역을 구하고 누적하는 방식으로 풀었는데, 당연히 이전에 탐색했던 영역을 새로 visited를 선언하고 탐색하게 되므로 "시간초과"가 발생하였다.

 

강사님의 풀이를 참고해본 결과, 결국 문제를 풀기 위해서는 세로(열)에 대한 정보만 필요하기 때문에 DFS나 BFS로 석유량을 한번 탐색할 때 각 열에서 추출할 수 있는 석유량을 누적해주면 된다.

 

결론적으로 각 열마다 시추관을 뚫을 때 마다 DFS나 BFS를 돌게 되면 상당히 비효율적으로 작동하기 때문에, 모든 영역을 단 한번만 탐색하고 필요한 정보를 그 때마다 저장해주는 방식으로 풀어야 한다 :)