풀이
1. 시추 가능한 덩어리 별 크기를 카운트
2. 해당 덩어리가 포함된 y 축에 덩어리 크기를 더해준다.
덩어리 별 크기 카운트를 위해서는 2차원 BFS를 사용했다.
그리고 해당 덩어리가 포함된 y 축을 구하기 위해 BFS로 좌표를 돌면서 set을 통해 y 값을 넣어줬다.
한 덩어리 당 BFS가 종료되면 y 값이 담긴 set을 순회하며 해당 y 값에 덩어리 크기를 더해줬다.
효율성 검사도 포함되어 있기 때문에 처음엔 통과하지 못했다.
최대한 자료구조를 덜 쓰기 위해
queue 라이브러리 대신 list를 사용했고, set을 사용하였다.
코드
queue = []
def bfs(land, oils, visited):
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
cnt = 0
columns = set()
while len(queue) > 0:
x, y = queue.pop(0)
cnt += 1
visited[x][y] = True
columns.add(y)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx < len(land) and ny >= 0 and ny < len(land[0]):
if visited[nx][ny] == False and land[nx][ny] == 1:
visited[nx][ny] = True
queue.append([nx, ny])
for col in columns:
oils[col] += cnt
def solution(land):
answer = 0
xLen = len(land)
yLen = len(land[0])
visited = [[False for _ in range(yLen)] for _ in range(xLen)]
oils = [0 for _ in range(yLen)]
for i in range(xLen):
for j in range(yLen):
if visited[i][j] == False and land[i][j] == 1:
queue.append([i, j])
bfs(land, oils, visited)
answer = max(oils)
return answer
'Algorithm > Programmers' 카테고리의 다른 글
[Programmers] Lv.2 _ [PCCP 기출문제] 3번 / 충돌 위험 찾기 (0) | 2025.01.06 |
---|---|
[Programmers] Lv.2 _ [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 (0) | 2025.01.05 |
[Programmers] Lv.1 _ 가장 많이 받은 선물 (1) | 2024.06.11 |