프로그래머스 250136 석유시추 파이썬 풀이

난이도 : Lv. 2

풀이일 : 2410314

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

프로그래머스

---

문제

---

아이디어

• 매장된 석유를 만나면 BFS탐색으로 석유의 양을 구한다.
• BFS 탐색 중에 제일 왼쪽 위치와 제일 오른쪽 위치를 기록한다.
• BFS 탐색 종료 후에 탐색한 석유 매장지의 횡방향 모든 칸에 석유의 양을 더해준다.
• 석유의 양이 가장 많은 칸의 값을 출력한다.

---

전체 풀이 코드

from collections import deque

def solution(land):
    N, M = len(land), len(land[0])
    oil = [0]*len(land[0]) # 세로 방향 석유 양 기록용
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 탐색 방향 지표
    
    for i in range(N):
        for j in range(M):
            if land[i][j]: # 석유 발견
                mini = maxi = j # 매장지 가로 길이 기록
                count = 0 # 석유 매장양
                queue = deque()
                queue.append((i, j))
                while queue:
                    x, y = queue.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        # 다음 탐색지가 유효한 땅이며 석유 매장지일 경우
                        if 0 <= nx < N and 0 <= ny < M and land[nx][ny]:
                            count += 1
                            land[nx][ny] = 0
                            queue.append((nx, ny))
                            # 현재 매장지 y좌표로 mini, maxi 비교
                            mini = ny if mini > ny else mini
                            maxi = ny if maxi < ny else maxi
                # 석유 매장지 j 좌표에 매장량 추가
                for l in range(mini, maxi + 1):
                    oil[l] += count if count else 1
	# 세로 방향 최대 매장지
    answer = max(oil)             
    return answer

---

느낀점

• BFS 탐색을 하면서 j 방향 기록만 해주면 간단하게 풀 수 있는 문제였다.
• BFS를 한동안 좋아했어서 금방 풀긴 했는데, 자바로도 다시 풀어봐야지