깊이 우선 탐색(Depth First Search)
- BFS와 다르게 Stack을 활용하여 인접한 노드 중 하나를 사용하고 나머지는 Stack에 저장하여 인접한 노드가 더이상 없을 경우 Stack 되어 있는 노드를 꺼내어 순회하는 방식
[알고리즘]
1) 최초 지점을 Stack에 넣는다.
2) Stack에서 먼저 하나씩 꺼내옴(꺼내온 객체는 바로 pop)
3) 꺼내온 데이터를 방문 했음을 표시(별도의 배열 사용)
4) 꺼내온 데이터에서 인접한 노드가 있다면 Stack에 push
5) Stack이 비어질 때까지 2~4를 반복
* BFS와 크게 다른 점은 Stack을 사용한다는 점만 다르고 나머지는 거의 비슷하다.
- 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.
[문제풀이]
1) 전체 배열을 순회
2) 방문하지 않고 데이터가 '1'인 부분에서 DFS 알고리즘을 수행
2-1) 해당 지점을 Stack에 넣는다.
2-2) Stack에서 하나씩 꺼내옴(꺼내온 객체는 바로 pop)
2-3) 꺼내온 데이터를 방문 했음을 표시(별도의 배열 사용)하고 갯수를 따로 저장(별도의 vector 사용)
2-4) 꺼내온 데이터에서 인접한 노드가 있다면 Stack에 push
2-5) Stack이 비어질 때까지 2~4를 반복
3) 별도의 vector에 저장된 갯수를 정렬
4) vector의 사이즈와 가장 많은 갯수를 출력
[*주의 사항]
1) 문제에서 최대 사이즈는 500이었지만 최대 사이즈를 500이 아닌 502로 해야 에러가 발생하지 않음
2) 그림이 하나도 없을 경우를 예외처리 해야함
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#include <vector>
#define MAX 502
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// 변수
int inputHeight, inputWidth;
char arr[MAX][MAX];
bool visited[MAX][MAX];
fill(&visited[0][0], &visited[MAX-1][MAX-1], false);
cin >> inputHeight >> inputWidth;
for(int idxY = 0; idxY < inputHeight; idxY++)
{
for (int idxX = 0; idxX < inputWidth; idxX++)
{
cin >> arr[idxY][idxX];
}
}
vector<int> result;
stack<pair<int, int>> st;
// 전체 순회
for (int idxY = 0; idxY < inputHeight; idxY++)
{
for (int idxX = 0; idxX < inputWidth; idxX++)
{
if (!visited[idxY][idxX] && arr[idxY][idxX] == '1')
{
int curSize = 0;
st.push(make_pair(idxY, idxX));
while (!st.empty())
{
pair<int, int> front = st.top();
int y = front.first;
int x = front.second;
st.pop();
// 인접한 노드 확인
if (!visited[y][x])
{
visited[y][x] = true;
curSize++;
if (y > 0 & arr[y - 1][x] == '1' && visited[y - 1][x] == false)
{
st.push(make_pair(y - 1, x));
}
if (x > 0 & arr[y][x - 1] == '1' && visited[y][x - 1] == false)
{
st.push(make_pair(y, x - 1));
}
if (y < inputHeight - 1 & arr[y + 1][x] == '1' && visited[y + 1][x] == false)
{
st.push(make_pair(y + 1, x));
}
if (x < inputWidth & arr[y][x + 1] == '1' && visited[y][x + 1] == false)
{
st.push(make_pair(y, x + 1));
}
}
}
result.push_back(curSize);
}
}
}
// 사이즈가 0인 경우 예외처리
if (result.size() == 0)
{
cout << 0 << endl << 0;
}
else
{
// 정렬
sort(result.begin(), result.begin() + result.size());
cout << result.size() << endl << result.back();
}
return 0;
}
