[프로그래머스] 석유 시추 (python)

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

프로그래머스

풀이 방법

처음엔 문제를 x축으로 나누어서 진행했다. 같은 x축일 때 까진 visited 배열을 초기화하지 않고 진행했고 x축이 증가할 때마다 visited 방문 배열을 초기화해주었다. 이렇게 하니 효율성 문제가 발생했다.

그래서 다른 분들의 풀이 방법을 참고하니 정사영이라는 알고리즘을 사용하는 것을 볼 수 있었다.

먼저 x축에 따른 추출 가능한 석유량을 count하는 배열 result를 생성한다. 그 후 완전 탐색을 하며 만약 방문하지 않았고 석유라면 bfs 탐색을 시작한다. bfs 탐색을 할 때 x의 최대 최소를 저장해 두고 bfs 함수가 종료되기 전 count 변수로 파악해 놓은 석유량을 min_x부터 max_x까지 result에 더해 준다. 이 과정이 끝나면 result에서 최대 값을 추출하면 정답이 된다.

 

from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def solution(land):
    answer = 0
    n = len(land) ## 새로 길이 y
    m = len(land[0]) ## 가로 길이 x    
    visited = [[0 for _ in range(m)] for _ in range(n)] ## 2차원 배열 생성  
    result = [0 for _ in range(m)] ## 결과 배열 저장    
    def bfs(y, x):
        cnt = 1
        q = deque()
        q.append((y, x))
        visited[y][x] = 1
        min_x, max_x = x, x
        while q:
            yy, xx = q.popleft()
            for i in range(4):
                ny = yy + dy[i]
                nx = xx + dx[i]                    
                if (ny >= 0 and ny < n and nx >= 0 and nx < m):                    
                    if (visited[ny][nx] == 0 and land[ny][nx] == 1):
                        min_x = min(min_x, nx)
                        max_x = max(max_x, nx)
                        cnt += 1
                        q.append((ny, nx))
                        visited[ny][nx] = 1        
        for i in range(min_x, max_x + 1):
            result[i] += cnt        
        
    for i in range(n): ## y
        for j in range(m): ## x
            if(land[i][j] == 1 and visited[i][j] == 0):
                bfs(i, j)
    for i in range(m):
        answer = max(answer, result[i])
    return answer