[Coding Test]석유시추

Author

SEOYEON CHOI

Published

January 4, 2025

- 링크

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

- 문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

제한사항

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

효율성 테스트 케이스 제한사항

주어진 조건 외 추가 제한사항 없습니다.

from collections import deque

def solution(land):
    rows = len(land)
    cols = len(land[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    def bfs(x, y):
        if land[x][y] == 1:
            queue = deque([(x, y)])
            visited[x][y] = True
            while queue:
                cx, cy = queue.popleft()
                for dx, dy in directions:
                    nx, ny = cx + dx, cy + dy
                    if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny] and land[nx][ny] == 1:
                        visited[nx][ny] = True
                        queue.append((nx, ny))

    rst_bfs = []
    for j in range(cols):
        visited = [[False for _ in range(cols)] for _ in range(rows)]
        for i in range(rows):
            bfs(i,j)
            rst_bfs.append(sum(row.count(True) for row in visited ))
    answer = max(rst_bfs)
    return answer
solution([[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]])
# 9
9
solution([[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]])
# 16
16

정확성은 맞으나 효율성은 실패 - 채점 결과 - 정확성: 60.0 - 효율성: 0.0 - 합계: 60.0 / 100.0

land = [[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]]
rows = len(land)
cols = len(land[0])
rows, cols
(5, 8)
from collections import deque
def bfs(x, y):
    if land[x][y] == 1:
        queue = deque([(x, y)])
        visited[x][y] = True
        while queue:
            cx, cy = queue.popleft()
            for dx, dy in directions:
                nx, ny = cx + dx, cy + dy
                if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny] and land[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False for _ in range(cols)] for _ in range(rows)]
for i in range(rows):
    bfs(i,0)
sum(row.count(True) for row in visited )
8
land
[[0, 0, 0, 1, 1, 1, 0, 0],
 [0, 0, 0, 0, 1, 1, 0, 0],
 [1, 1, 0, 0, 0, 1, 1, 0],
 [1, 1, 1, 0, 0, 0, 0, 0],
 [1, 1, 1, 0, 0, 0, 1, 1]]

BFS를 사용하였고,

타인의 코드를 참고하여

학습이 더 필요할 것으로 보임

from collections import deque

def solution(land):
    rows = len(land)
    cols = len(land[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited = [[0 for _ in range(cols)] for _ in range(rows)]
    sum_sum = [0 for _ in range(cols)]
    def bfs(x, y):
        min_y = y
        max_y = y
        count = 0
        queue = deque([(x, y)])
        visited[x][y] = 1
        while queue:
            cx, cy = queue.popleft()
            count += 1
            min_y = min(min_y,cy)
            max_y = max(max_y,cy)
            for dx, dy in directions:
                nx, ny = cx + dx, cy + dy
                if 0 <= nx < rows and 0 <= ny < cols and visited[nx][ny] != 1 and land[nx][ny] == 1:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))

        for i in range(min_y,max_y+1):
            sum_sum[i] += count

    for j in range(cols):
        for i in range(rows):
            if visited[i][j] == 0 and land[i][j]==1:
                bfs(i,j)
    answer = max(sum_sum)
    return answer
solution([[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]])
# 9
9
solution([[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]])
# 16
16

입출력 예 #1

가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

시추관의 위치 획득한 덩어리 총 석유량

1 [8] 8

2 [8] 8

3 [8] 8

4 [7] 7

5 [7] 7

6 [7] 7

7 [7, 2] 9

8 [2] 2

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

land = [[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]]
rows, cols = len(land), len(land[0])
rows, cols 
(5, 8)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[0 for _ in range(cols)] for _ in range(rows)]
visited
[[0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]
sum_sum = [0 for _ in range(cols)]
sum_sum
[0, 0, 0, 0, 0, 0, 0, 0]
def bfs(x, y):
    min_y = y
    max_y = y
    count = 0
    queue = deque([(x, y)])
    visited[x][y] = 1
    while queue:
        # count를 1 증가시키며 방문한 영역의 크기를 세어줍니다.
        # min_y와 max_y를 갱신하며 탐색 중 만난 열의 범위를 추적합니다.
        cx, cy = queue.popleft()
        count += 1
        min_y = min(min_y,cy)
        max_y = max(max_y,cy)
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            # 방문하지 않은 visited[nx][ny] != 1 곳 방문
            # 하지만 석유가 흘러야 함 land[nx][ny] == 1
            if 0 <= nx < rows and 0 <= ny < cols and visited[nx][ny] != 1 and land[nx][ny] == 1:
                visited[nx][ny] = 1
                queue.append((nx, ny))

    for i in range(min_y,max_y+1):
        sum_sum[i] += count
        print({'i': i, 'min': min_y, 'max': max_y, 'sum':sum_sum[i]})
for j in range(cols):
    for i in range(rows):
        if visited[i][j] == 0 and land[i][j]==1:
            bfs(i,j)
{'i': 0, 'min': 0, 'max': 2, 'sum': 8}
{'i': 1, 'min': 0, 'max': 2, 'sum': 8}
{'i': 2, 'min': 0, 'max': 2, 'sum': 8}
{'i': 3, 'min': 3, 'max': 6, 'sum': 7}
{'i': 4, 'min': 3, 'max': 6, 'sum': 7}
{'i': 5, 'min': 3, 'max': 6, 'sum': 7}
{'i': 6, 'min': 3, 'max': 6, 'sum': 7}
{'i': 6, 'min': 6, 'max': 7, 'sum': 9}
{'i': 7, 'min': 6, 'max': 7, 'sum': 2}
sum_sum
[8, 8, 8, 7, 7, 7, 9, 2]
visited
[[0, 0, 0, 1, 1, 1, 0, 0],
 [0, 0, 0, 0, 1, 1, 0, 0],
 [1, 1, 0, 0, 0, 1, 1, 0],
 [1, 1, 1, 0, 0, 0, 0, 0],
 [1, 1, 1, 0, 0, 0, 1, 1]]
max(sum_sum)
9

입출력 예 #2

시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.

시추관의 위치 획득한 덩어리 총 석유량

1 [12] 12

2 [12] 12

3 [3, 12] 15

4 [2, 12] 14

5 [2, 12] 14

6 [2, 1, 1, 12] 16

6번 열에 시추관을 설치하면 크기가 2, 1, 1, 12인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 16으로 가장 많습니다. 따라서 16을 return 해야 합니다.

land = [[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]]
land
[[1, 0, 1, 0, 1, 1],
 [1, 0, 1, 0, 0, 0],
 [1, 0, 1, 0, 0, 1],
 [1, 0, 0, 1, 0, 0],
 [1, 0, 0, 1, 0, 1],
 [1, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1]]
rows, cols = len(land), len(land[0])
rows, cols 
(7, 6)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[0 for _ in range(cols)] for _ in range(rows)]
visited
[[0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0]]
sum_sum = [0 for _ in range(cols)]
sum_sum
[0, 0, 0, 0, 0, 0]
def bfs(x, y):
    min_y = y
    max_y = y
    count = 0
    queue = deque([(x, y)])
    visited[x][y] = 1
    while queue:
        # count를 1 증가시키며 방문한 영역의 크기를 세어줍니다.
        # min_y와 max_y를 갱신하며 탐색 중 만난 열의 범위를 추적합니다.
        cx, cy = queue.popleft()
        count += 1
        min_y = min(min_y,cy)
        max_y = max(max_y,cy)
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            # 방문하지 않은 visited[nx][ny] != 1 곳 방문
            # 하지만 석유가 흘러야 함 land[nx][ny] == 1
            if 0 <= nx < rows and 0 <= ny < cols and visited[nx][ny] != 1 and land[nx][ny] == 1:
                visited[nx][ny] = 1
                queue.append((nx, ny))

    for i in range(min_y,max_y+1):
        sum_sum[i] += count
        print({'i': i, 'min': min_y, 'max': max_y, 'sum':sum_sum[i]})
for j in range(cols):
    for i in range(rows):
        if visited[i][j] == 0 and land[i][j]==1:
            bfs(i,j)
{'i': 0, 'min': 0, 'max': 5, 'sum': 12}
{'i': 1, 'min': 0, 'max': 5, 'sum': 12}
{'i': 2, 'min': 0, 'max': 5, 'sum': 12}
{'i': 3, 'min': 0, 'max': 5, 'sum': 12}
{'i': 4, 'min': 0, 'max': 5, 'sum': 12}
{'i': 5, 'min': 0, 'max': 5, 'sum': 12}
{'i': 2, 'min': 2, 'max': 2, 'sum': 15}
{'i': 3, 'min': 3, 'max': 3, 'sum': 14}
{'i': 4, 'min': 4, 'max': 5, 'sum': 14}
{'i': 5, 'min': 4, 'max': 5, 'sum': 14}
{'i': 5, 'min': 5, 'max': 5, 'sum': 15}
{'i': 5, 'min': 5, 'max': 5, 'sum': 16}
sum_sum
[12, 12, 15, 14, 14, 16]
visited
[[1, 0, 1, 0, 1, 1],
 [1, 0, 1, 0, 0, 0],
 [1, 0, 1, 0, 0, 1],
 [1, 0, 0, 1, 0, 0],
 [1, 0, 0, 1, 0, 1],
 [1, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1]]
max(sum_sum)
16