석유 시추(L2)

문제 설명

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

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

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

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

시추관의 위치	획득한 덩어리	총 석유량
1	[8]	8
2	[8]	8
3	[8]	8
4	[7]	7
5	[7]	7
6	[7]	7
7	[7, 2]	9
8	[2]	2

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

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

---

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
  • land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
  • land[i][j]는 0 또는 1입니다.
  • land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

정확성 테스트 케이스 제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

입출력 예

land	result
[[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]]	9
[[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]]	16

---

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.

시추관의 위치	획득한 덩어리	총 석유량
1	[12]	12
2	[12]	12
3	[3, 12]	15
4	[2, 12]	14
5	[2, 12]	14
6	[2, 1, 1, 12]	16

6번 열에 시추관을 설치하면 크기가 2, 1, 1, 12인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 16으로 가장 많습니다. 따라서 16을 return 해야 합니다.

나의 풀이

from collections import deque,defaultdict

def BFS(visited,land,s,tmp_list,count_dict):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=True
    R=len(land)
    C=len(land[0])
    dr=[-1,0,1,0]
    dc=[0,-1,0,1]
    tmp_list.append(s)
    cnt=1
    while q:
        r,c=q.popleft()
        for i in range(4):
            nr=r+dr[i]
            nc=c+dc[i]
            if 0<=nr<R and 0<=nc<C and not visited[nr][nc] and land[nr][nc]:
                visited[nr][nc]=True
                tmp_list.append([nr,nc])
                q.append([nr,nc])
                cnt+=1
    column_set=set()
    for t in tmp_list:
        column_set.add(t[1])
    for cs in column_set:
        count_dict[cs]+=cnt

def solution(land):
    answer = 0
    
    visited=[[False]*len(land[0]) for _ in range(len(land))]
    count_dict=defaultdict(int)
    for i in range(len(land)):
        for j in range(len(land[0])):
            if land[i][j]!=0 and not visited[i][j]:
                tmp_list=[]
                BFS(visited,land,[i,j],tmp_list,count_dict)
    answer=max(count_dict.values())
    
    return answer

• dfs로 풀었다.
• 연결된 석유들의 전체 양을 cnt로 구한 후, count_dict에 column마다 얻을 수 있는 석유의 양을 더해준다. 이 때 하나의 column에 석유의 전체 양이 여러번 등장할 수 있기 때문에, bfs로 찾은 좌표의 column을 set()에 넣어주어 중복되지 않도록 해주었다.
• 위처럼 생각을 해보니 tmp_list가 필요 없어서, 없는 코드로 조금 더 최적화해보았다.

나의 풀이 (개선)

from collections import deque,defaultdict

def BFS(visited,land,s,count_dict):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=True
    R=len(land)
    C=len(land[0])
    dr=[-1,0,1,0]
    dc=[0,-1,0,1]
    column_set=set()
    column_set.add(s[1])
    cnt=1
    while q:
        r,c=q.popleft()
        for i in range(4):
            nr=r+dr[i]
            nc=c+dc[i]
            if 0<=nr<R and 0<=nc<C and not visited[nr][nc] and land[nr][nc]:
                visited[nr][nc]=True
                q.append([nr,nc])
                column_set.add(nc)
                cnt+=1
    for cs in column_set:
        count_dict[cs]+=cnt

def solution(land):
    answer = 0
    
    visited=[[False]*len(land[0]) for _ in range(len(land))]
    count_dict=defaultdict(int)
    for i in range(len(land)):
        for j in range(len(land[0])):
            if land[i][j]!=0 and not visited[i][j]:
                BFS(visited,land,[i,j],count_dict)
    answer=max(count_dict.values())
    
    return answer

나의 풀이(오답)

from collections import deque

def BFS(visited,land,s,tmp_list):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=True
    R=len(land)
    C=len(land[0])
    dr=[-1,0,1,0]
    dc=[0,-1,0,1]
    tmp_list.append(s)
    cnt=1
    while q:
        r,c=q.popleft()
        for i in range(4):
            nr=r+dr[i]
            nc=c+dc[i]
            if 0<=nr<R and 0<=nc<C and not visited[nr][nc] and land[nr][nc]:
                visited[nr][nc]=True
                tmp_list.append([nr,nc])
                q.append([nr,nc])
                cnt+=1
    for t in tmp_list:
        land[t[0]][t[1]]=cnt

def solution(land):
    answer = 0
    
    visited=[[False]*len(land[0]) for _ in range(len(land))]
    
    for i in range(len(land)):
        for j in range(len(land[0])):
            if land[i][j]==1 and not visited[i][j]:
                tmp_list=[]
                BFS(visited,land,[i,j],tmp_list)
    for j in range(len(land[0])):
        pre=0
        tmp_max=0
        for i in range(len(land)):
            if land[i][j]!=pre:
                tmp_max+=land[i][j]
                pre=land[i][j]
        answer=max(answer,tmp_max)
    
    return answer

• land상에 각 영역마다 석유의 전체 양을 넣어주어, column마다 sum을 해서 최대값을 구하려고 했는데, 생각해보니 하나의 column에서 같은 석유양을 나타내는 원소가 여러번 등장할 수 있다. 따라서 해당 코드 대신 위처럼 코드를 개선했다.