문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

시추관의 위치획득한 덩어리총 석유량1[8]82[8]83[8]84[7]75[7]76[7]77[7, 2]98[2]2

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

정답

from collections import deque 

def solution(land):
    h, w = len(land), len(land[0])
    sum_arr = [0]*w
    move = [(0,1),(0,-1),(1,0),(-1,0)]
    visited = [[False for i in range(w)] for j in range(h)]
    
    for j in range(h):
        
        for i in range(w):
            if visited[j][i] == True or land[j][i] == 0 :
                continue
            
            cols = set()
            # 1인 경우
            s = 0
            q = deque([(j,i)])
            while q :
                a,b = q.popleft()
                
                if visited[a][b] == True or land[a][b] == 0:
                    continue
                
                
                s+=1
                visited[a][b] = True
                cols.add(b)
                
                for x,y in move:
                    if 0 <= a+x < h and 0<= b+y < w: # 인덱스 초과 여부 검사
                        if visited[a+x][b+y] == False and land[a+x][b+y] == 1: # 미리 검사해서 큐에 삽입
                            q.append((a+x, b+y))                 
            
            for col in cols :
                sum_arr[col]+=s
                
    return max(sum_arr)



=====효율성 테스트 결과
테스트 1 〉	통과 (69.46ms, 13.2MB)
테스트 2 〉	통과 (171.14ms, 13.2MB)
테스트 3 〉	통과 (170.71ms, 13.1MB)
테스트 4 〉	통과 (66.54ms, 13.1MB)
테스트 5 〉	통과 (335.93ms, 13.2MB)
테스트 6 〉	통과 (72.70ms, 13.2MB)

===== 행 -> 열 조회로 바꿨을 때 : 아마 C나 C++이었으면 미세한 속도 차이가 난다고 함. 
테스트 1 〉	통과 (69.66ms, 13.2MB)
테스트 2 〉	통과 (193.02ms, 13.2MB)
테스트 3 〉	통과 (171.34ms, 13.1MB)
테스트 4 〉	통과 (65.35ms, 13.2MB)
테스트 5 〉	통과 (343.65ms, 13.1MB)
테스트 6 〉	통과 (78.03ms, 13.1MB)
 


===== 큐 삽입 조건 수정 시 
               for x,y in move:
                    if 0 <= a+x < h and 0<= b+y < w: # 인덱스 초과 여부 검사
                        if visited[a+x][b+y] == False and land[a+x][b+y] == 1: # 미리 검사해서 큐에 삽입
                            q.append((a+x, b+y))  


테스트 1 〉	통과 (67.02ms, 13.2MB)
테스트 2 〉	통과 (161.54ms, 13.2MB)
테스트 3 〉	통과 (158.07ms, 13.2MB)
테스트 4 〉	통과 (63.19ms, 13.2MB)
테스트 5 〉	통과 (345.03ms, 13.1MB)
테스트 6 〉	통과 (66.12ms, 13.2MB)

풀이과정 

1. BFS 정확성 테스트 통과, 효율성 테스트 실패

from collections import deque 

def solution(land):
    h, w = len(land), len(land[0])
    sum_arr = [0]*w
    move = [(0,1),(0,-1),(1,0),(-1,0)]
    
    for i in range(w):
        visited = [[False for i in range(w)] for j in range(h)]
        for j in range(h):
            if visited[j][i] == True or land[j][i] == 0 :
                continue
            
            # 1인 경우
            s = 0
            q = deque([(j,i)])
            while q :
                a,b = q.popleft()
                
                if visited[a][b] == True or land[a][b] == 0:
                    continue
                
        
                s+=1
                visited[a][b] = True
                cols.add(b)
                
                for x,y in move:
                    if 0 <= a+x < h and 0<= b+y < w: # 인덱스 초과 여부 검사
                        if visited[a+x][b+y] == False and land[a+x][b+y] == 1: # 미리 검사해서 큐에 삽입
                            q.append((a+x, b+y))                 
            
            
            sum_arr[col]+=s
                
    return max(sum_arr)

코드 문제점 :   visited = [[False for i in range(w)] for j in range(h)]  즉, 방문여부 체크 배열을 매 열을 검사할 때 마다 새로 생성했음. 매번 배열을 새로 생성하고 새로 검사하는 구 조다 보니 속도 문제가 생김. 

2.  최초 정답 : 매번 배열을 새로 생성하지 않고 기존의 배열을 활용, 덩어리별 열 값을 세트로 저장했다가 마지막에 넣어줌.

from collections import deque 

def solution(land):
    h, w = len(land), len(land[0])
    sum_arr = [0]*w
    move = [(0,1),(0,-1),(1,0),(-1,0)]
    visited = [[False for i in range(w)] for j in range(h)]
    
    for i in range(w):
        for j in range(h):
            if visited[j][i] == True or land[j][i] == 0 :
                continue
            
            cols = set()
            # 1인 경우
            s = 0
            q = deque([(j,i)])
            while q :
                a,b = q.popleft()
                
                if visited[a][b] == True or land[a][b] == 0:
                    continue
                
                
                s+=1
                visited[a][b] = True
                cols.add(b)
                
                for x,y in move:
                    if 0 <= a+x < h and 0<= b+y < w: # 인덱스 초과 여부 검사
                        q.append((a+x, b+y))                 
            
            for col in cols :
                sum_arr[col]+=s
                
    return max(sum_arr)