[프로그래머스][PCCP 기출] 석유 시추

1. 문제

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

 

2. 코드

python 1

from collections import deque

def bfs(graph, start, visited):
    width, height = len(graph[0]), len(graph)
    paths = [(-1, 0), (1, 0), (0, -1),(0, 1)]
    queue = deque([start])
    visited[start[0]][start[1]] = True
    
    size = 0
    cols = set()
    
    while queue:
        x, y = queue.popleft()
        
        size += 1
        cols.add(y)
        
        for dx, dy in paths:
            nx = x + dx
            ny = y + dy
            
            if (0 <= nx < height) and (0 <= ny < width):
                if graph[nx][ny] == 1 and not visited[nx][ny]:
                    queue.append((nx, ny))
                    visited[nx][ny] = True
    
    return size, cols
    
def solution(land):
    width, height = len(land[0]), len(land)
    visited = [[False] * width for _ in range(height)]

    land_cols = [0] * width
    
    for h in range(height):
        for w in range(width):
            if land[h][w] == 1 and not visited[h][w]:
                size, cols = bfs(land, (h, w), visited)
            
                for col in cols:
                    land_cols[col] += size
            
    return max(land_cols)

풀이

1. BFS 함수 → 시작점에서 하나의 석유 덩어리를 탐색
   1. width, height를 구해 범위 확인
   2. paths = 상하좌우
   3. dequeue를 통해 시작 위치 추가
   4. visited를 통해 방문 처리
   5. queue를 돌면서
      1. 현재 덩어리의 크기(size) 1 증가
      2. 현재 칸이 속한 열 번호 cols 에 저장
      3. 현재 칸의 상하좌우가 1인 칸을 찾음 → width, height에 범위 안에 있는 것 중
         1. 인접한곳에 값이 1이고 방문 안했으면 → 방문처리, queue 에 넣음
2. solution 함수 → land 지도에서 덩어리들의 시작점 찾음
   1. land의 현재 값이 1 & 방문을 안했으면 → bfs 실행
   2. cols에 총 값을 lands_cols에 저장
3. 최종적으로 얻을 수 있는 최대 석유량 출력

 

3. 메모

• BFS 사용
  • [주의 ]BFS는 하나의 덩어리를 찾는 함수임
  • 해당 문제는 BFS/DFS 모두 가능 → python에서 재귀 DFS는 깊이 제한 문제 생길 수 있으니 해당 문제에서 권장X
• 시간 복잡도: O(W × H)