프로그래머스 [PCCP 기출문제] 2번 / 석유 시추 (Python, BFS)

문제 출처: 석유 시추

 

 

 

처음 풀이(정확성 테스트 모두 통과, 효율성 테스트 모두 미통과)

• BFS로 시도함

from collections import deque

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


def bfs(y, m, n, graph, visited):
    queue = deque()
    count = 0

    for x in range(m):
        if graph[x][y] == 1 and visited[x][y] == 0:  # y값은 고정, x값만 증가시킨다.
            queue.append([x, y])
            visited[x][y] = 1  # 방문 처리
            count += 1
            while queue:
                x2, y2 = queue.popleft()
                for k in range(4):
                    nx = x2 + dx[k]
                    ny = y2 + dy[k]
                    if 0 <= nx < m and 0 <= ny < n and graph[nx][ny] == 1 \
                            and visited[nx][ny] == 0:
                        queue.append([nx, ny])
                        count += 1
                        visited[nx][ny] = 1  # 방문 처리

    return count


def solution(land):
    m = len(land)  # 가로길이
    n = len(land[0])  # 세로길이

    answer = 0
    for i in range(n):
        visited = [[0] * n for _ in range(m)]
        count = bfs(i, m, n, land, visited)
        answer = max(answer, count)
    return answer

 

 

 

이후 풀이(정확성 테스트, 효율성 테스트 모두 통과)

• 검색을 하면서 알게 되었다.
• 애초에 y값을 기준으로 돌기 때문에 매번 y값만큼 bfs를 돌지 말고, 전체 land에 대한 bfs를 돌면서 덩어리 크기의 값을 y값 기준인 배열에 넣는다.
• 따라서 bfs를 돌면서 석유덩이의 최소 y와 최대 y를 구해서 result라는 리스트에 석유 매장량을 저장한다. 이를 통해 y값을 기준으로 겹치는 만큼 저장한다.

from collections import deque


def solution(land):
    m = len(land)  # 가로길이
    n = len(land[0])  # 세로길이
    
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    def bfs(x, y):
        queue = deque()
        queue.append([x, y])
        land[x][y] = 0  # 방문 처리
        count = 1       # 개수 count 시작
        
        max_y = float('-inf')
        min_y = float('inf')
        
        while queue:
            for _ in range(len(queue)):
                x2, y2 = queue.popleft()
                max_y, min_y = max(max_y, y2), min(min_y, y2)
                
                for k in range(4):
                    nx = x2 + dx[k]
                    ny = y2 + dy[k]
                    if 0 <= nx < m and 0 <= ny < n and land[nx][ny] == 1:
                        queue.append([nx, ny])
                        count += 1        # 카운팅
                        land[nx][ny] = 0  # 방문 처리
                
        return min_y, max_y, count

    y_list = [0] * n # 세로의 값을 저장할 배열을 만든다.
    for i in range(m):
        for j in range(n):
            if land[i][j] == 1: # 방문이 가능하면
                miny, maxy, c = bfs(i, j)
                
                # 이후 y_list Update
                for l in range(miny, maxy + 1, 1):
                    y_list[l] += c
    print(y_list)
    return max(y_list)