https://school.programmers.co.kr/learn/courses/30/lessons/250136
문제 설명:
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.
예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.
시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.
오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다. 석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.
풀이:
from collections import deque, defaultdict
def solution(land):
res = 0
zone = 2 # 구역넘버 시작
count = []
dic_count = defaultdict(int)
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visited = [[False] * len(land[0]) for _ in range(len(land))]
# 구역별로, 갯수
def bfs(a, b, zone):
Q = deque([(a, b)])
visited[a][b] = True
land[a][b] = zone
count = 1
while Q:
x, y = Q.popleft()
for dx, dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < len(land) and 0 <= ny < len(land[0]) and not visited[nx][ny] and land[nx][ny] == 1:
visited[nx][ny] = True
land[nx][ny] = zone
Q.append((nx, ny))
count += 1
return count
for x in range(len(land)):
for y in range(len(land[0])):
if land[x][y] == 1 and visited[x][y] == False:
dic_count[zone] = bfs(x, y, zone)
zone += 1
# x 좌표
result = []
for y in range(len(land[0])):
result_temp =set()
for x in range(len(land)):
if land[x][y] != 0:
result_temp.add(land[x][y])
res = max(res,sum(dic_count[x] for x in result_temp))
return res
print(solution([[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
# print(solution([[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
내 알고리즘은 석유가 있는곳을 구역을 나누고, 딕셔너리에 넣어서 관리한다
예를들어 첫번째 예시로 돌리면
defaultdict(<class 'int'>, {2: 7, 3: 8, 4: 2})
land =
[
[0, 0, 0, 2, 2, 2, 0, 0],
[0, 0, 0, 0, 2, 2, 0, 0],
[3, 3, 0, 0, 0, 2, 2, 0],
[3, 3, 3, 0, 0, 0, 0, 0],
[3, 3, 3, 0, 0, 0, 4, 4]
]이렇게 나온다
구역번호는 2번부터 시작하고
2번구역은 7개 3번구역은 8개 4번은2개 이런식으로 딕셔너리에 넣어준다 . 그러면
시추관을 석유를 꼽았을때 거기에 해당하는 zone을 찾아서 석유를 얼마나 뽑아 올 수 있는지 알 수 있다.
그리고 석유좌표들을 zone 좌표로 바꿔준다. 그래야 나중에 딕셔너리에서 찾아 올 수 있다.
이중포문을 돌리면서 y값만 바꿔주고. 거기에 들어간 zone을 담아 석유 총합을 구하면서 최댓값을 최신화 해준다.
댓글