[프로그래머스/Lv2] 석유시추 - Python

https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

 

 

처음엔 그냥 bfs 하면서 최댓값 찾기로 풀었다.

1. 모든 열 순회 하면서 땅 파기

2. 석유 나오면 deque에 append

3. 그 deque 빌 때까지 bfs하며 석유 += 1

4. 최댓값 갱신

 

# 실패 코드

# 시간초과

from collections import deque

def dig(i, n, m, land):
    oil = 0

    q = deque([])

    visited = [[False] * m for _ in range(n)]

    for d in range(n):

        if land[d][i]:
            visited[d][i] = True
            q.append((d, i))
            oil += 1

    while q:
        r, c = q.popleft()

        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + di, c + dj

            if 0 <= nr < n and 0 <= nc < m and land[nr][nc] and not visited[nr][nc]:
                visited[nr][nc] = True
                oil += 1
                q.append((nr, nc))

    return oil


def solution(land):
    answer = 0

    n = len(land)  # 세로
    m = len(land[0])  # 가로

    for i in range(m):
        answer = max(answer, dig(i, n, m, land))
        if answer == 250000:
            break

    return answer

 

 

대박 그랬더니 효율성 빵점맞았다 총점 60점..

 

 

 

그래서 땅의 모든 구간을 한번씩만 방문할 수 있는 방법을 생각했다.

모든 땅 순회하면서 방문 안 한 곳의 석유 덩어리를 찾으려고 했다.

 

1. (0, 0) 부터 (n-1, m-1)까지 순회하며 방문 안한 곳의 석유 찾기

2. 석유 찾았으면 그 부분 bfs

3. 그 석유를 너비우선탐색할 동안 방문한 열 집합에 추가하기

3. bfs 끝났으면 방문한 열을 순회하며 최종 oil[해당열]에 그 석유 덩어리의 석유량 추가하기

 

# 성공 코드

from collections import deque

def dig(i, j, n, m, land):
    global oil, visited

    q = deque([(i, j)])

    visited_column = {j}  # 이 구역을 bfs하면서 방문한 열 집합
    cur_oil = 1  # 이 구역의 석유량

    while q:
        r, c = q.popleft()

        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + di, c + dj

            if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc] and land[nr][nc]:
                visited_column.add(nc)  # 방문한 열 추가
                q.append((nr, nc))
                visited[nr][nc] = True
                cur_oil += 1

    # 방문한 열 순회하면서 oil (각 열을 뚫으면 발견할 수 있는 석유량) 추가해줌
    for v in list(visited_column):
        oil[v] += cur_oil


def solution(land):
    global oil, visited

    n = len(land)  # 세로
    m = len(land[0])  # 가로

    oil = [0] * m  # 각 열마다 파면 나오는 오일량

    visited = [[False] * m for _ in range(n)]

    # 모든 땅 한번씨만 방문해서 석유 체크 bfs
    for i in range(n):
        for j in range(m):

            if land[i][j] and not visited[i][j]:
                visited[i][j] = True
                dig(i, j, n, m, land)

    answer = max(oil)

    return answer

 

 

그동안 풀었던 bfs 문제는 다 비슷했는데 이런 유형은 처음 풀어봐서 재밌었다