[프로그래머스 코딩테스트][PCCP 기출문제] 2번 / 석유 시추 파이썬 문제 풀이 아이디어

문제 

프로그래머스

 

 

풀이 아이디어 

알고리즘: BFS

 

아이디어 석유 덩어리들의 크기를 bfs로 구한다. 그리고 각 열의 석유 시추량을 저장할 리스트를 생성하고 리스트의 각 열에 해당하는 덩어리들의 크기를 더한다. 이후 리스트에서 최댓값을 추출하면 정답을 구할 수 있다.   

 

풀이과정 

1. 먼저 석유가 있는 지점의 위치를 리스트로 저장 

2. 리스트의 첫 번째 요소에 대한 bfs 실행(이때 확인한 지점은 리스트에서 제외한다.)

3. 석유 덩어리의 크기를 구한뒤 그 덩어리가 속한 열에 덩어리의 크기 값을 더한다.  

4. 2,3 과정을 반복하여 모든 덩어리의 크기를 구한다. 

5. 석유 시추량을 저장한 리스트에서 최댓값을 추출한다. 

 

 

코드(미완성 -> 완성 버전은 아래에)

from collections import deque

directions = [[1,0],[-1,0],[0,1],[0,-1]]

#BFS  
def bfs(s, graph, line):
    q = deque()
    q.append(s)
    graph.remove(s)
    
    
    sum = 0# 덩어리 크디 
    visited = [0]*len(line)# 덩어리가 위치한 열의 위치를 저장할 리스트 
    
    # bfs
    while q:
        sum+=1
        current = q.popleft()
        
        # 석유가 매장된 열 위치 저장 
        if visited[current[1]]==0:
            visited[current[1]]=1
        
        for direction in directions:
            x = current[0]+direction[0]
            y = current[1]+direction[1]
            if [x,y] in graph:
                q.append([x,y])
                graph.remove([x,y])    
    
    #line 리스트에 석유 매장량 저장 
    for i in range(len(line)):
        line[i] = line[i]+(visited[i]*sum)
        
    return line


def solution(land):
    x = len(land)
    y = len(land[0])
    
    oil = [] # 석유가 매장된 위치
    for i in range(x):
        for j in range(y):
            if land[i][j]==1:
                oil.append([i,j])
                
    line = [0]*(y) # 석유 시추량을 저장할 리스트 
    
    # 모든 덩어리들에 대한 bfs 실행 
    while oil:
        bfs(oil[0],oil,line)
    
    # 최댓값 출력 
    answer = max(line)
    return answer

 

 

해결하지 못한 문제 

효율성 테스트 문제

아이디어 자체는 다른 사람과 같지만 효율성 테스트를 통과하지 못하였다. 정확성은 전부 통과하였다. 반복문 횟수가 더 많은 코드들도 정답이라고 올려놨는 데 그 이유를 확인할 수 없다.  

->remove 함수의 시간복잡도는 n으로 코드 전체의 실행시간을 크게 증가시킨다. 

->remove가 아닌 visited를 활용하여 검사하는 방안으로 진행 

 

 

최종 풀이 코드 

 

from collections import deque

directions = [[1,0],[-1,0],[0,1],[0,-1]]

def solution(land):
    x = len(land)
    y = len(land[0])
    
    line = [0]*(y)
    visited = [[0 for i in range(y)] for j in range(x)]
    def bfs(x,y):
        q = deque()
        q.append([x,y])
        sum = 0
        visited_line = [0]*len(line)
    
        while q:
            sum+=1
            current = q.popleft()
            if visited_line[current[1]]==0:
                visited_line[current[1]]=1
            for direction in directions:
                x = current[0]+direction[0]
                y = current[1]+direction[1]
                if x>=0 and x<len(land) and y>=0 and y<len(land[0]):
                    if visited[x][y] ==0 and land[x][y]==1:
                        visited[x][y] == 1
                        q.append([x,y])        
        for i in range(len(line)):
            line[i] = line[i]+(visited_line[i]*sum)
    
    for i in range(x):
        for j in range(y):
            if land[i][j]==1 and visited[i][j]==0:
                visited[i][j]=1
                bfs(i,j)
    
    answer = max(line)
    return answer