[문제풀이/프로그래머스] 석유 시추(feat. BFS)

 

들어가며

알고리즘 문제 중 최단 경로 탐색이라던지, 노드를 구성해서 탐색해야하는 문제들이 꽤나 있습니다. 대표적인 탐색 알고리즘으로는 Binary Search, 깊이우선탐색(DFS, Depth First Search), 너비우선탐색(BFS, Breadth First Search) 등이 있습니다. 특히 많이 헷갈리는 경우가 DFS를 사용해야 하는가 BFS를 사용해야하는가 입니다. 오늘은 BFS 위주로 설명을 드릴 예정인데, 대표적으로 최단 경로 탐색, 최소 횟수 탐색, 방문 가능한 모든 노드 탐색 등 이전 상태를 기억하지 않은 상태로 특정 경로를 탐색할 때 BFS를 사용합니다. BFS는 탐색 깊이를 자연스럽게 카운팅 가능한 장점이 있습니다.

bfs 동작 방식(출처: wikimedia)

 

특징

구분	BFS	DFS
탐색 방식	가까운 노드부터 탐색	한 경로를 끝까지 탐색
자료구조	큐(Queue)	스택(Stack) 또는 재귀
최단 경로	O (가중치 동일 시)	X
메모리 사용량	큼 (큐에 많은 노드 보관)	적음 (경로 기반 탐색)
적합한 문제 유형	최단 거리, 최소 횟수	모든 경우 탐색, 경로 추적

 

기본적인 BFS의 코드는 다음과 같습니다. queue를 사용하며 시작 노드를 삽입 후 인접한 노드들을 순차로 순회하면서 queue에 push합니다. 한 차례(레벨)가 끝나면 queue에서 노드를 pop하게 되면 인접한 노드들부터 순회하게 됩니다.

# python
def bfs(graph:Dict, start:int): # Dict 자료형 형태로 준다. key는 노드, value는 인접노드를 가리킨다.
    visited = {i:False for i in graph.keys()} # 방문 배열. visited[node] = True이면 node는 방문이 끝난 상태이다.
    queue = [start]
    visited[start] = True
    while queue: # 큐가 빌 때까지 반복
        current = queue.pop(0) #queue에서 노드를 하나 빼 온다. 이 노드를 current라고 하자.
        for nxt in graph[current]: # current의 인접 노드들을 확인한다. 이 각각의 노드를 nxt라고 하자.
            if not visited[nxt]: # 만일 nxt에 방문하지 않았다면
                #nxt 방문
                queue.append(nxt)
                visited[nxt] = True

 

 

문제풀이

백준 1260

먼저 간단한 BFS 풀이 문제를 보겠습니다. 백준 1260문제입니다(링크).

 

풀이 과정은 입력받은 정점과 간선을 통해 그래프를 구성하고 앞서 살펴봤던 bfs함수를 실행하면 됩니다.

// 백준 1260: DFS와 BFS
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<vector<int>> relations;
vector<bool> visited;
queue<int> q;
int N, M;

void dfs(int key)
{
    printf("%d ", key+1);
    if (!visited[key])
        visited[key] = true;
    else
        return;

    for (const auto r : relations[key])
    {
        if (!visited[r])
            dfs(r);
    }
}

void bfs(int start)
{
    q.push(start);
    visited[start] = true;

    while (!q.empty())
    {
        int current = q.front();
        printf("%d ", current + 1);
        q.pop();

        for (int next : relations[current])
        {
            if (!visited[next])
            {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int start;
    cin >> N >> M >> start;
    relations.resize(N);
    visited = vector<bool>(N, false);

    for (int i = 0; i < M; i++)
    {
        int f, s;
        cin >> f >> s;
        relations[f-1].push_back(s-1);
        relations[s-1].push_back(f-1);
    }

    for (auto& r : relations)
        sort(r.begin(), r.end());

    dfs(start - 1);
    visited.clear();
    visited.resize(N);
    printf("\n");
    bfs(start - 1);
}

재귀를 활용한 dfs도 같이 있으니 참고하시면 좋을 것 같습니다.

 

프로그래머스 석유 시추

다음은 응용 문제입니다. 프로그래머스 석유 시추 문제입니다(링크). PCCP 기출문제네요.

입출력 예

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
[[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]]	16

첫번째 예제는 위 그림이고 두 번째 예제는 아래 그림입니다.

 

Level 3에 가까운 Level 2문제라고 생각합니다. 우선 Simple BFS에서는 노드지만 격자 모양에서는 x,y좌표가 따로 있기도 합니다. 대표적으로 미로찾기, 길찾기 문제에서는 격자 모양의 문제가 많이 나오기도 합니다.
문제 접근의 핵심은 BFS를 활용하여 모든 석유덩어리들의 합한 값(maxOil)을 구성해 놓는 것입니다.

먼저 첫번째 행부터 오른쪽으로 순회하면서 석유를 만났고, 방문하지 않지 않았던 노드들에 대해서 bfs를 진행하는 것이 첫 번째입니다.

#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

int n, m;
vector<vector<bool>> visited;
int maxOil;

int solution(vector<vector<int>> land) {
    n = land.size();
    m = land[0].size();
    visited.resize(n, vector<bool>(m, false));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (land[i][j] == 1 && !visited[i][j]) {
                maxOil = 0;
                bfs(i, j, land);
                ...

다음으로 bfs함수를 보겠습니다.

// C++
...
int n, m;
vector<vector<bool>> visited;
int maxOil;
set<int> visitedColumns;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void bfs(int i, int j, const vector<vector<int>>& land) {
    visited[i][j] = true;
    queue<pair<int, int>> q;
    q.push(make_pair(i, j));
    
    while(!q.empty()) {
        auto current = q.front();
        maxOil++;
        //printf("[%d,%d] %d\n", current.first, current.second, maxOil);
        visitedColumns.insert(current.second);
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            const int ci = current.first + dx[i];
            const int cj = current.second + dy[i];
            
            if (ci < 0 || ci >= n || cj < 0 || cj >= m)
                continue;
            
            if (land[ci][cj] == 1 && !visited[ci][cj]) {
                q.push(make_pair(ci, cj));
                visited[ci][cj] = true;
            }
        }
    }
}

석유시추 문제의 bfs에서 인접한 노드는 해당 노드의 왼쪽/오른쪽/위쪽/아래쪽 4방향입니다. 따라서 bfs함수에서도 dx,dy를 이용해서 네 방향에 대한 탐색을 시작합니다. current i와 current j가 더이상 갈 수 없는 경우를 제외하고, 방문하지 않은 석유땅을 모두 탐색합니다. 탐색 할때마다 maxOil값을 늘려서 석유 덩어리의 합을 구해냅니다.

전체 코드 입니다.

#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

int n, m;
vector<vector<bool>> visited;
int maxOil;
set<int> visitedColumns;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void bfs(int i, int j, const vector<vector<int>>& land) {
    visited[i][j] = true;
    queue<pair<int, int>> q;
    q.push(make_pair(i, j));
    
    while(!q.empty()) {
        auto current = q.front();
        maxOil++;
        //printf("[%d,%d] %d\n", current.first, current.second, maxOil);
        visitedColumns.insert(current.second);
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            const int ci = current.first + dx[i];
            const int cj = current.second + dy[i];
            
            if (ci < 0 || ci >= n || cj < 0 || cj >= m)
                continue;
            
            if (land[ci][cj] == 1 && !visited[ci][cj]) {
                q.push(make_pair(ci, cj));
                visited[ci][cj] = true;
            }
        }  
    } 
}

int solution(vector<vector<int>> land) {
    n = land.size();
    m = land[0].size();
    visited.resize(n, vector<bool>(m, false));
    vector<int> oilColumns(m, 0);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (land[i][j] == 1 && !visited[i][j]) {
                maxOil = 0;
                visitedColumns.clear();
                bfs(i, j, land);
                
                for (const auto& v : visitedColumns) {
                    oilColumns[v] += maxOil;
                }
                //printf("\n");
            }
        }
    }
            
    return *max_element(oilColumns.begin(), oilColumns.end());
}

bfs를 진행하기 전에 전역변수인 maxOil과 visitedColumns를 초기화 시켜줍니다. 문제에서 시추관(열 방향)이 추출할 수 있는 최대 석유량을 물어봤기 때문에 탐색한 Column을 저장하는 visitedColumns와 Column별 시추 가능한 Oil을 기록할 수 있는 oilColumns로 구성합니다. oilColumns의 최대값이 정답입니다.

 

BFS의 주요 특징입니다.

항목	설명
탐색 순서	시작 노드 → 인접 노드 → 인접 노드의 인접 노드 (계층적 탐색)
자료구조	큐(Queue)를 사용
시간 복잡도	O(V + E) (V: 정점 수, E: 간선 수)
공간 복잡도	O(V) (방문 여부 및 큐 저장용 메모리)
탐색 결과	최단 경로(가중치가 동일할 경우)를 찾을 수 있음
그래프 형태	인접 리스트, 인접 행렬 모두 가능
재귀 사용 여부	일반적으로 반복문 기반 (DFS는 재귀 기반인 경우 많음)