[programmers] [PCCP 기출문제] 2번 / 석유 시추

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

프로그래머스

 

문제는 위에 링크를 클릭하면 된다.

 

해당 문제는 NxM 배열에서 얼마나 많은 석유를 시추 할 수 있는지 최대값을 출력하는 문제 이다.

 

저는 이 문제는 DFS 형식으로 방문 처리를 진행 했습니다.

여기서 제일 핵심은 해당 좌표의 값이 1 이고, 1과 같이 붙어있는 석유들을 하나의 그룹으로 지정하는 것이 핵심 입니다.

 

그 후 마지막에 시추 하는 형식으로 for문으로 탐색 하며 각 인덱스의 그룹의 값을 더해주어 max를 비교하면 되는 문제입니다.

 

def dfs(x, y, land, visited, oil_group):
    stack = [(x, y)]
    visited[x][y] = True
    oil_count = 1  # 현재 덩어리 크기

    # 4방향 탐색
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    while stack:
        cx, cy = stack.pop()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < len(land) and 0 <= ny < len(land[0]) and not visited[nx][ny] and land[nx][ny] == 1:
                visited[nx][ny] = True
                stack.append((nx, ny))
                oil_count += 1
                
    oil_group.append(oil_count)

def solution(land):
    n, m = len(land), len(land[0])
    visited = [[False] * m for _ in range(n)]
    oil_groups = []  # 각 덩어리의 크기 리스트
    group_map = [[-1] * m for _ in range(n)]  # 각 칸이 속한 덩어리 번호를 기록
    
    # 석유 덩어리 탐색
    group_id = 0
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and not visited[i][j]:
                # 새로운 덩어리 발견
                dfs(i, j, land, visited, oil_groups)
                # 덩어리의 모든 칸에 그룹 번호 할당
                stack = [(i, j)]
                visited[i][j] = True
                group_map[i][j] = group_id
                while stack:
                    cx, cy = stack.pop()
                    for dx, dy in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
                        nx, ny = cx + dx, cy + dy
                        if 0 <= nx < n and 0 <= ny < m and land[nx][ny] == 1 and group_map[nx][ny] == -1:
                            group_map[nx][ny] = group_id
                            stack.append((nx, ny))
                group_id += 1
    
    # 각 열에 대해 얻을 수 있는 석유량 계산
    max_oil = 0
    for j in range(m):
        oil_sum = 0
        seen_groups = set()
        for i in range(n):
            if land[i][j] == 1:
                group_id = group_map[i][j]
                if group_id not in seen_groups:
                    oil_sum += oil_groups[group_id]
                    seen_groups.add(group_id)
        max_oil = max(max_oil, oil_sum)
    
    return max_oil