문제 개요
오늘의 코딩 테스트 문제는 '석유 시추'다. 2차원 배열로 표현된 땅에서 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾는 문제다. BFS 알고리즘을 활용해 연결된 석유 덩어리를 찾고, 각 열에서 얻을 수 있는 최대 석유량을 계산해야 한다.
문제 분석
핵심 포인트:
1.
시추관은 열 단위로 설치된다
2.
연결된 석유 덩어리는 하나의 단위로 취급된다
3.
0은 빈 땅, 1은 석유가 있는 땅을 의미한다
이 문제의 핵심은 효율적으로 연결된 석유 덩어리를 찾고, 각 열에서 얻을 수 있는 석유량을 계산하는 것이다.
해결 방법
접근 방식:
1.
BFS로 모든 석유 덩어리의 크기를 계산한다
2.
각 열에 걸치는 덩어리들의 크기 합을 구한다
3.
최대값을 찾는다
알고리즘: BFS (Breadth-First Search)
•
연결된 석유 덩어리를 효율적으로 탐색할 수 있다
•
시간 복잡도: O(N*M), N은 행의 수, M은 열의 수
데이터 구조:
•
Queue: BFS 구현에 사용
•
Map: 각 덩어리의 ID와 크기를 저장
•
Set: 각 열에 걸친 고유한 덩어리 ID를 저장
코드
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;
vector<pair<int,int>> dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int solution(vector<vector<int>> land) {
int answer = 0;
int id = 1; // 구분자
map<int, int> m_size; // id:크기
queue<pair<int,int>> q;
for (int n=0; n<land.size(); n++)
{
for (int m=0; m<land[0].size(); m++)
{
if (land[n][m]==1)
{
int size=0, nn, nm;
id++;
q.push({n, m});
land[n][m] = id;
while (!q.empty())
{
for (auto d: dir)
{
int nn = q.front().first + d.first;
int nm = q.front().second + d.second;
if (!(nn<0 || nn>=land.size() || nm<0 || nm>=land[0].size()))
{
if (land[nn][nm]==1)
{
q.push({nn, nm});
land[nn][nm] = id;
}
}
}
size++;
q.pop();
}
m_size[id] = size;
}
}
}
for (int m=0; m<land[0].size(); m++)
{
int acc = 0;
set<int> temp;
for (int n = 0; n<land.size(); n++)
temp.insert(land[n][m]);
for (auto t: temp)
acc += m_size[t];
answer = max(answer, acc);
}
return answer;
}
C++
복사
구현 과정 및 최적화
1.
BFS로 연결된 석유 덩어리를 탐색하며 각 덩어리에 고유 ID를 부여했다
2.
Map을 사용해 덩어리 ID와 크기를 저장했다
3.
각 열을 순회하며 Set으로 중복 없이 덩어리 ID를 수집했다
4.
수집된 ID를 기반으로 해당 열의 총 석유량을 계산했다
최적화 포인트:
•
Set을 사용해 중복 계산을 방지했다
•
전체 땅을 한 번만 순회하여 시간 복잡도를 O(N*M)으로 유지했다
회고
오늘 학습 포인트:
1.
BFS를 활용한 연결 요소 탐색
2.
Set과 Map을 이용한 효율적인 데이터 관리
개선할 점:
•
코드가 다소 길고 지저분하다. 함수 분리나 매크로 사용으로 가독성을 높일 수 있을 것 같다
•
변수 명명이 직관적이지 않아 수정이 필요하다
이번 문제를 통해 BFS의 실제 적용 방법과 효율적인 데이터 구조 사용의 중요성을 다시 한번 깨달았다. 코딩 테스트 준비에 있어 알고리즘 자체의 이해도 중요하지만, 실제 문제에 적용하는 능력을 기르는 것이 더 중요하다는 걸 느꼈다.
