석유 시추

📖 PCCP 기출문제 > [PCCP 기출문제] 2번 / 석유 시추

📖What I thought

1. 격자 모양의 땅? BFS 각
2. 석유 덩어리를 일단 찾아야 해 → BFS로 찾을 수 있음
   • 이 때 각 석유 덩어리의 크기도 체크하자
3. 근데 시추관이 수직으로 하나만 뚫을 수 있어…
4. 그러면?? 해당 열을 뚫으면 가질 수 있는 석유 덩어리 크기를 체크해놔야 해
5. 그걸 어떻게 알지…
6. 덩어리마다 포함되어 있는 열을 기록해두고 덩어리 크기 정해지면 해당 열들에 덩어리 크기만큼 추가

📖풀이

📎BFS

from collections import deque
 
# bfs
def bfs(land, x, y, visited, oil):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    queue = deque([(x, y)])
    visited[x][y] = True
    col = set() # 해당 덩어리에 속하는 열
    size = 0 # 덩어리 크기
    
    while queue:
        x, y = queue.popleft()
        col.add(y+1)
        size += 1
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            
            # 각 좌표 범위 내 and 석유 있는 칸 and 아직 방문하지 않은 칸
            if 0 <= nx < len(land) and 0<= ny < len(land[0]) and land[nx][ny] and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True
    
    # 각 열에 석유량 추가
    for c in col:
        oil[c] += size
 
# main
def solution(land):
    n = len(land) # 세로 길이 (행)
    m = len(land[0]) # 가로 길이 (열)
    
    oil = [0 for _ in range(m+1)] # 각 열마다 뽑을 수 있는 석유량
    
    visited = [[False for _ in range(m)] for _ in range(n)]
    
    # bfs 탐색
    for i in range(n):
        for j in range(m):
            # 1 수행 == 1 덩어리
            if land[i][j] and not visited[i][j]:
                bfs(land, i, j, visited, oil)
    
    return max(oil) # 최대 석유량

• 한 덩어리에 i번 째 열에 속한 석유가 여러 번 있을 수 있으므로 각 열은 set에 저장

📖What I learned

1. 다른 사람들을 보니까 visited를 땅 크기만큼으로 해서 T/F를 체크한 게 아니라 그냥 빈 리스트를 visited로 두고 방문하면 해당 위치를 append하고 in으로 체크하네??? 이러면 탐색 순서도 알 수 있어서 더 좋은 듯
2. 중복 제거 == Set

📖관련 지식

📎Set

📎BFS(Breadth-First Search)