[모각코 / 240126] 알고리즘 문제 풀이 (프로그래머스 - bfs)

 

 

안녕하세요. 모각코 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)