반응형
안녕하세요. 모각코 4일차입니다.
오늘은 프로그래머스에서 bfs 문제를 풀었습니다.
문제는 이름은 [PCCP 기출문제 2번] / 석유 시추입니다.
https://school.programmers.co.kr/learn/courses/30/lessons/250136
입출력 양식입니다.
2차원 배열의 land 가 받아지면 가장 많이 시추된 석유 덩어리의 양을 result 로 반환합니다.
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
시추관을 넣어서 가장 많은 석유를 추출할 수 있는 방법을 찾는 문제입니다.
당연히 bfs 일 것이라고 생각했고, bfs로 풀었습니다.
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(land, x, y, visited):
q = deque()
q.append((x, y))
visited[x][y] = -1
v = 1
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= len(land) or nx < 0 or ny >= len(land[i]) or ny < 0:
continue
if land[nx][ny] == 1 and visited[nx][ny] != -1:
v += 1
visited[nx][ny] = -1
q.append((nx, ny))
return v
def solution(land):
answer = [0 for _ in range(len(land[0]))]
for i in range(len(land[0])):
visited = [[0 for _ in range(len(land[0]))] for _ in range(len(land))]
for j in range(len(land)):
if land[j][i] == 1 and visited[j][i] != -1:
answer[i] += bfs(land, j, i, visited)
return max(answer)
로직은 맞는 것 같았으나 시간 초과가 났습니다.
아마 visited 가 반복문을 돌릴 때마다 계속 초기화를 해주어서 그런게 아닐까 생각했습니다. (이렇게 되면 모든 경우에서 bfs를 돌린다.)
하지만 visited를 반복문 전에 초기화 한 이유는 bfs를 수행하기 전에 이 석유 덩어리가 이미 bfs를 실행한 상태인 걸 저 코드로는 알 수 없었기 때문입니다.
삽질을 하다가 bfs를 한 번 돌렸을 때의 최소 y축의 길이와 최대 y축의 길이를 알면 모든 값에 석유 덩어리의 값을 추가면 되겠다고 생각했습니다.
따라서, bfs 사이에 min_y 와 max_y를 두어서 문제를 해결했습니다.
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(land, x, y, visited, answer):
q = deque()
q.append((x, y))
visited[x][y] = -1
v = 1
max_y = y
min_y = y
while q:
x, y = q.popleft()
max_y = max(y, max_y)
min_y = min(y, min_y)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= len(land) or nx < 0 or ny >= len(land[i]) or ny < 0:
continue
if land[nx][ny] == 1 and visited[nx][ny] != -1:
v += 1
visited[nx][ny] = -1
q.append((nx, ny))
for i in range(min_y, max_y + 1):
answer[i] += v
return min_y, max_y, v
def solution(land):
answer = [0 for _ in range(len(land[0]))]
visited = [[0 for _ in range(len(land[0]))] for _ in range(len(land))]
for i in range(len(land[0])):
for j in range(len(land)):
if land[j][i] == 1 and visited[j][i] != -1:
bfs(land, j, i, visited, answer)
return max(answer)
반응형
'2024 겨울 모각코 - 내 장점은 algorithm' 카테고리의 다른 글
[모각코 / 240209] 알고리즘 문제 풀이 (백준 - 그리디 부수기) (2) | 2024.02.13 |
---|---|
[모각코 / 240202] 알고리즘 문제 풀이 (백준 - 그리디 부수기) (1) | 2024.02.04 |
[모각코 / 240119] 알고리즘 문제 풀이 (프로그래머스 - 스택/큐) (1) | 2024.01.22 |
[모각코 / 240112] 알고리즘 문제 풀이 (코드트리 - 백트래킹) (0) | 2024.01.17 |
[모각코 / 240105] 알고리즘 문제 풀이 (코드트리 - 시뮬레이션) (1) | 2024.01.11 |