[코테] 석유시추

https://school.programmers.co.kr/learn/courses/30/lessons/250136?language=python3

 

문제요약: 

0이 땅 1이 석유이고, 열기준으로 시추를 진행합니다. 시추관이 석유의 일부를 지나면 해당덩어리에 속한 모든 석유를 뽑을 수 있다고 할때 시추관 하나를 설치했을때 뽑을 수 있는 석유의 가장 큰 값을 반환하시오.

 

소요시간:

25분

 

난이도:

level2

 

제출횟수:

2회

 

코딩:

from collections import deque
def solution(land):
    dy= [-1,0,1,0]
    dx= [0,1,0,-1]
    n,m = len(land),len(land[0])
    mass = {}
    def bfs(y,x,t):
        q=deque([[y,x]])
        land[y][x] = t
        mass[t] =1
        while q:
            y,x = q.popleft()
            for i in range(4):
                ny,nx = y+dy[i],x+dx[i]
                if 0<=ny<n and 0<=nx<m and land[ny][nx]==1 :
                    land[ny][nx] = t
                    mass[t] +=1
                    q.append([ny,nx])
    i = 1                
    for y in range(n):
        for x in range(m):
            if land[y][x] ==1:
                i+=1
                bfs(y,x,i)
    ans =[]
    for x in range(m):
        temp = 0
        #for k in set(list(zip(*land))[x]):
        for k in set([i[x] for i in land]):
            if k!=0:
                temp+=mass[k]
        ans.append(temp)
    return max(ans)

해당 문제는 bfs를 돌며 연결되어있는 석유를 파악하고, 이때 석유 번호를 매긴뒤 매장량을 dictionary에 저장한뒤, 열기준으로 돌면서 지나가는 석유번호들을 중복처리한 뒤 , 각 열마다 뽑을 수 있는 석유량을 ans에 append시켜 max를 구해 문제를 풀어주었습니다.
다만 효율성에서 한번 걸려서 제출을 두번하게 되었는데, 아래서 5,6번째 줄을 보면 기존에는 zip함수를 사용하여 열에 접근하였다면 뒤는 리스트 컴프리핸션을 통해 접근하였습니다. 시간 복잡도를 비교해 본다면 *land에서 언패킹하고 zip으로 다시 묶는 과정에서 원소들 전체에 접근하기 때문에 O(m * n)이 소요되는 반면, 리스트 컴프리핸션을 사용했을 땐 열의 크기만큼만 접근하면 되기 때문에 O(n)의 시간복잡도를 가져 더 효율적으로 됩니다.

 

무조건 zip함수가 오래걸리기 때문에 zip을 사용하지 말라는것이 아니라 상황에 따라 어떤것이 효율적인지 잘 판단을 해야합니다. 위와같은 케이스에서도 for x in range(m)으로 이미 열에 대해서 포문을 돌고있는데 안에서 전체에 대해 zip함수를 사용하여 같은 작업을 여러번 반복하여서 그렇지 밖에서 zip으로 작업한 뒤, 접근하게 된다면 같은 시간복잡도를 가져 동일한 시간이 소요되는것을 확인할 수 있습니다.

    land2 =list(zip(*land))
    for x in range(m):
        temp = 0
        for k in set(land2[x]):
            if k!=0:
                temp+=mass[k]
        ans.append(temp)

 

다른사람 풀이:

def solution(land):
    n, m = len(land), len(land[0])
    visited = [[True]*m for _ in range(n)]
    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    oil_cnt = [0]*m
    for i in range(n):
        for j in range(m):
            if land[i][j] and visited[i][j]:
                visited[i][j] = False
                s = [(i,j)]
                col = set()
                oil = 0
                while s:
                    x, y = s.pop()
                    col.add(y)
                    oil += 1
                    for dx, dy in delta:
                        X, Y = x+dx, y+dy
                        if 0<=X<n and 0<=Y<m and land[X][Y] and visited[X][Y]:
                            visited[X][Y] = False
                            s.append((X,Y))
                for y in col:
                    oil_cnt[y] += oil
    return max(oil_cnt)

처음부터 포문을 돌때 미리 계산을 하는 방법도 있습니다.

 

추가적으로 시간이 조금 오버되었는데 기본적인 bfs문제였던 만큼 이정도 난이도는 15분내로 풀 수 있을 정도로 훈련이 필요하다고 생각합니다.