[PCCP 기출문제] 2번
난이도
LEVEL 2
문제
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
세로길이가 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 |
풀이
BFS로 풀었습니다.
일반적인 BFS와 같이 2차원 배열을 탐색하며 석유가 존재하는 좌표를 찾습니다.
그 후, 해당 좌표부터 시작하여 붙어 있는 석유를 탐색. 해당 좌표의 y좌표를 oil_y에 넣고 cnt를 1 증가시킵니다.
-> y좌표는 한 번만 있어도 되기 때문에 set으로 하였습니다.
탐색이 끝나면 해당 석유가 포함하는 y좌표들과 크기를 반환하여 oil에 저장합니다.
모든 좌표를 탐색한 후, 석유의 정보가 저장된 oil 배열을 탐색합니다.
현재 석유의 모든 y좌표를 탐색하며 현재 좌표에서 얻을 수 있는 석유(ans[y])의 크기를 증가시켜줍니다.
코드
from collections import deque
def solution(land):
n, m = len(land), len(land[0])
visited = [[False] * m for _ in range(n)] # 방문 여부 체크
dxy = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 상하좌우 탐색용
oil = [] # 석유 정보
ans = [0] * m # y 좌표 당 채굴 가능한 석유의 양
def bfs(x, y): # 기본적인 bfs 풀이는 생략
q = deque([(x, y)])
visited[x][y] = True
cnt = 1 # 현재 석유의 크기
oil_y = {y} # 현재 석유가 포함하는 y좌표
while q:
x, y = q.popleft()
for dx, dy in dxy:
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and land[nx][ny] == 1:
visited[nx][ny] = True
q.append((nx, ny))
cnt += 1 # 석유의 크기 증가
oil_y.add(ny) # 석유가 포함하는 y좌표 추가
return (oil_y, cnt) # 석유의 y좌표와 크기 반환
for x in range(n):
for y in range(m):
if land[x][y] and not visited[x][y]:
oil.append(bfs(x, y)) # 석유가 존재하면 bfs로 정보 저장
for o, cnt in oil: # 저장된 석유 탐색
for y in o: # 석유에 포함된 y좌표 탐색
ans[y] += cnt # 해당 좌표의 수 석유의 크기만큼 증가
return max(ans) # 최대 채굴 가능한 석유 출력