[Programmers] Lv.2 _ [PCCP 기출문제] 2번 / 석유 시추

 

풀이

1. 시추 가능한 덩어리 별 크기를 카운트

2. 해당 덩어리가 포함된 y 축에 덩어리 크기를 더해준다.

 

덩어리 별 크기 카운트를 위해서는 2차원 BFS를 사용했다.

그리고 해당 덩어리가 포함된 y 축을 구하기 위해 BFS로 좌표를 돌면서 set을 통해 y 값을 넣어줬다.

한 덩어리 당 BFS가 종료되면 y 값이 담긴 set을 순회하며 해당 y 값에 덩어리 크기를 더해줬다.

 

효율성 검사도 포함되어 있기 때문에 처음엔 통과하지 못했다.

최대한 자료구조를 덜 쓰기 위해

queue 라이브러리 대신 list를 사용했고, set을 사용하였다.

코드

queue = []


def bfs(land, oils, visited):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    cnt = 0
    columns = set()

    while len(queue) > 0:
        x, y = queue.pop(0)
        cnt += 1
        visited[x][y] = True

        columns.add(y)

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < len(land) and ny >= 0 and ny < len(land[0]):
                if visited[nx][ny] == False and land[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append([nx, ny])

    for col in columns:
        oils[col] += cnt


def solution(land):
    answer = 0

    xLen = len(land)
    yLen = len(land[0])

    visited = [[False for _ in range(yLen)] for _ in range(xLen)]
    oils = [0 for _ in range(yLen)]

    for i in range(xLen):
        for j in range(yLen):
            if visited[i][j] == False and land[i][j] == 1:
                queue.append([i, j])
                bfs(land, oils, visited)
    answer = max(oils)
    return answer