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

사용 언어 - Python3

문제 -  PCCP 기출 2번 석유 시추

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

프로그래머스

 

정답

DFS 알고리즘

x,y 좌표를 nx,ny로 이동하면서, 가장 깊게까지 들어갈 수 있는 min_y, max_y를 찾기

from collections import deque
def solution(land):
    answer = 0
    n = len(land) # 세로
    m = len(land[0]) # 가로 
    
    # 이동
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    result = [0 for i in range(m+1)] # 석유매장량
    visited = [[0 for i in range(m)] for j in range(n)] # 방문여부
    
    def bfs(a,b):
        count = 0 # 석유량
        visited[a][b] = 1 # 방문처리
        q = deque()
        q.append((a,b))
        min_y, max_y = b, b # y 기준으로 가장 작고 큰 값 = 세로로 뚫은 시추량
        while q:
            x,y = q.popleft()
            min_y = min(min_y,y)
            max_y = max(max_y,y)
            count += 1
            for i in range(4): # 이동
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= m: # 범위초과시 무시
                    continue
                if visited[nx][ny] == 0 and land[nx][ny] == 1: # 방문 X, 석유있다면
                    visited[nx][ny] = 1
                    q.append((nx,ny))
                    
        for i in range(min_y, max_y+1):
            result[i] += count # 총 석유량 저장
            
    for i in range(n):
        for j in range(m):
            if visited[i][j] == 0 and land[i][j] == 1:
                bfs(i,j)

    answer = max(result)
    
    return answer

 

 

 

레퍼런스

• 깃허브 정답