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

📒문제

📒풀이

2차원 격자 모양의 땅이 있고, 시추관을 삽입했을 때 얻을 수 있는 가장 많은 석유의 양을 구하는 문제이다.

✔️첫 번째 접근 포인트

특정 열에 시추관을 삽입했을 때 얻을 수 있는 석유량을 매번 세어서 최대 석유량을 구하기

특정 열의 위치에서 탐색을 시작했을 때, 얻을 수 있는 석유량을 구한다.

이는 bfs로 접근할 수 있다.

from collections import deque

answer = 0

def init_visited(visited):
    for i in range(len(visited)):
        for j in range(len(visited[0])):
            visited[i][j] = False
            
def can_go(x, y, land, visited):
    n, m = len(land), len(land[0])
    # 해당 위치가 격자 범위를 벗어나는 경우
    if not (0 <= x < n and 0 <= y < m):
        return False
    # 해당 위치를 방문했거나, 벽인 경우
    if visited[x][y] or land[x][y] == 0:
        return False
    
    return True

def bfs(land, visited, queue):
    dxs = [0, 1, 0, -1]
    dys = [1, 0, -1, 0]
    cnt = 0
    while queue:
        cx, cy = queue.popleft()
        for dx, dy in zip(dxs, dys):
            nx, ny = cx + dx, cy + dy
            # 다음 위치로 갈 수 있는지 판단
            if can_go(nx, ny, land, visited):
                visited[nx][ny] = True
                queue.append((nx, ny))
                cnt += 1
    return cnt
                
        

def solution(land):
    global answer
    # 행, 열 길이
    n, m = len(land), len(land[0])
    queue = deque()

    # 하나의 열을 정해서 시추관 설치
    for i in range(m):
        cnt = 0
        visited = [
            [False] * m for _ in range(n)
        ]
        for j in range(n):
            # 설치한 시추관과 석유가 맞닿은 경우
            if not visited[j][i] and land[j][i] == 1:
                # 해당 위치에서 bfs 시작
                visited[j][i] = True
                queue.append((j, i))
                cnt = cnt + 1 + bfs(land, visited, queue)
        answer = max(answer, cnt)
                
    return answer

주의할 점은 매번 visited를 초기화해주기 위해 for loop 안에 visited 선언 및 초기화 구문을 작성하는 것이다.

🚨문제점

정확성 테스트는 통과하지만, 효율성 테스트는 실패한다.

위 코드는 O(N^4)의 시간복잡도를 갖는다.

왜냐하면 격자 범위 탐색을 위한 bfs 알고리즘이 O(N^2) 의 시간복잡도를 가지게 되는데, 이걸 매 격자 위치마다 bfs를 진행하기 때문이다.

물론 격자의 모든 위치에서 bfs를 매번 진행하는 것은 아니지만 최악의 경우에는 그렇게 된다는 이야기다.

✔️두 번째 접근 포인트

문제를 잘 살펴보면, 특정 열마다 시추관을 삽입하여 석유량을 구하는 작업을 매번하지 않아도 된다.

잘 보면 1번 열, 2번 열, 3번 열에 시추관을 삽입할 때, 얻을 수 있는 석유량은 동일하다.

이를 잘 활용하면 매번 visited를 초기화하지 않고 진행할 수 있다.

(3,1)에서 석유가 있어서 bfs 탐색을 진행하면 1~3열까지 살펴보게 된다.

그럼 1에서 3열까지는 시추관을 삽입해도 똑같은 석유량을 얻기 때문에 더 이상 살펴볼 필요가 없다.

from collections import deque
import sys

def solution(land):
    # 행, 열 길이
    n, m = len(land), len(land[0])
    visited = [
        [False] * m for _ in range(n)
    ]
    # 특정 열을 시추했을 때 얻을 수 있는 석유량
    count = [0] * m
    
    for row in range(n):
        for col in range(m):
            # 해당 위치를 방문하지 않았고, 석유가 있다면
            if not visited[row][col] and land[row][col] == 1:
                bfs(row, col, n, m, land, visited, count)
    
    return max(count)

def bfs(row, col, n, m, land, visited, count):
    queue = deque()
    queue.append((row, col))
    visited[row][col] = True
    cnt = 0
    dxs = [0, 1, 0, -1]
    dys = [1, 0, -1, 0]
    min_y, max_y = sys.maxsize, -sys.maxsize
    
    while queue:
        cx, cy = queue.popleft()
        cnt += 1
        # 방문한 위치 중 최소열과 최대열 값을 찾는다.
        min_y, max_y = min(min_y, cy), max(max_y, cy)
        for dx, dy in zip(dxs, dys):
            nx, ny = cx + dx, cy + dy
            # 다음 위치를 방문할 수 있다면
            if can_go(nx, ny, n, m, land, visited):
                queue.append((nx, ny))
                visited[nx][ny] = True
        
    for i in range(min_y, max_y+1):
        count[i] += cnt
    
            
def can_go(x, y, n, m, land, visited):
    # 해당 위치가 격자 범위를 벗어나는 경우
    if not in_range(x, y, n, m):
        return False

    # 해당 위치를 방문했거나, 벽인 경우
    if visited[x][y] or land[x][y] == 0:
        return False
    
    return True

def in_range(x, y, n, m):
    return 0 <= x < n and 0 <= y < m
    ```