문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
어떻게 풀 것이냐!
과정을 생략하고 코드만 보고싶으신 분은 맨 아래로
DFS문제이지만 그래프가 아니라 좌표기반으로 되어있다. 일단 입력받는 것 부터가 힘들겠는걸...?
❗ 배열이 좌표로 주어지면 배열을 +2 size만큼 더 생성해주기
항상 좌표 문제는 입력받은 좌표보다 +2 만큼 배열을 만들어 주는게 좋다고 생각한다. 좌표를 탐색할 때 위, 아래, 오른쪽, 왼쪽을 탐색하다 보면 배열의 범위를 벗어날 때가 많고, 런타임에러가 일어나거나 쓰레기값을 가져오기 때문이다. 그걸 방지하려면 많은 IF문을 사용해서 범위를 확인해줘야 하는데 그게 귀찮다.
‼️ 좌표 기반으로 DFS를 사용하자. X,Y를 저장할 수 있는 Stack이 필요하다.
DFS는 Stack, BFS는 Queue를 사용한다. 연결되어 있는 블록을 찾는데는 DFS나 BFS나 둘다 상관 없지만, 나는 DFS가 더 쉽다고 생각해서 DFS를 사용해서 풀었다. X,Y를 Stack에 저장하기 위해 Pair를 사용했다. Pair는 <utility> 안에 있다.
⁉️ 기본 생각 : 주어진 좌표에서 블록들을 찾아 다른 배열에 표시해 놓으면 되겠다!
주어진 지도에서 연속된 블록들을 DFS를 통해서 검사하는 과정에서 다른 지도에 표시를 해놓고, 주어진 지도에 모든 좌표를 검사 완료 했으면 다른지도를 보면서 단지의 갯수와 단지 안의 집의 갯수를 검사하자!
준비물 : x,y를 저장할 수 있는 Stack, 주어진 지도, 다른 지도 ⇒ Stack, arr[][], checked[][]
좋아 가보자. 👟
기본 입출력 정의
#include <iostream>
#include <stack>
#include <utility>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
int arr[t+2][t+2];
int checked[t+2][t+2];
int cnt = 1;
//dfs에 필요한 stack
stack<pair<int,int>> s;
//정보를 저장하는 vector
vector<int> v;
for(int i=0;i<t+2;i++){
fill_n(arr[i],t+2,0);
fill_n(checked[i],t+2,0);
}
for(int i=1;i<t+1;i++){
string a; cin>>a;
for(int j=0;j<a.size();j++){
arr[i][j+1] = a[j] - '0';
}
}
for(int i=0;i<t+2;i++){
for(int j=0;j<t+2;j++){
cout<<arr[i][j];
}
cout<<'\n';
}
cout<<"\n";
}입력은 잘 받아진다. 🙂
0으로 둘러쌓여진 것을 볼 수 있다. 저 0이 어떤 완충재 역할을 해줄 것이다.
DFS사용하기
원래는 dfs함수를 만들어서 사용하고 싶엇는데 2차원 배열을 함수로 어떻게 전달해야할 지 몰라 그냥 main문에 다 때려 박았다. ㅇㅇ
주어진 지도(arr[][]) 을 모두 검사해야하기 때문에 2중 포문 을 돌아준다.
이때! i=1부터, i<t+1까지 돌아야한다! 배열의 크기를 +2만큼 추가해줬으니까!
arr[i][j]가 1이면 이제 연결된 블록이 있는지 탐색을 시작한다.
처음에는 DFS를 끝내고 checked를 검사하면서 답을 낼려고 햇는데 생각을 해보니 그냥 DFS하는 과정에 Vector에 count를 한 것을 넣어주면 되겠더라.
for(int i=1;i<t+1;i++){
for(int j=1;j<t+1;j++){
if(arr[i][j] == 0) continue;
else{
//arr[i][j]가 숫자일 때
if(checked[i][j] == 0){
//방문한 적 없는 곳이라면 탐색 시작.
s.push(make_pair(i,j));
int chk = 0;
while(!s.empty()){
pair<int,int> p = s.top();
s.pop();
int x = p.first;
int y = p.second;
if(checked[x][y] != 0) continue;
checked[x][y] = cnt;
chk++;
//상하좌우를 검사하고, 있다면 stack에 넣어준다.
if(arr[x+1][y] != 0) s.push(make_pair(x+1,y));
if(arr[x][y+1] != 0) s.push(make_pair(x,y+1));
if(arr[x-1][y] != 0) s.push(make_pair(x-1,y));
if(arr[x][y-1] != 0) s.push(make_pair(x,y-1));
}
v.push_back(chk);
chk = 0;
cnt++;
}else{
continue;
}
}
}
}하고 나서 정답 출력.
sort(v.begin(),v.end(),less<int>());
cout<<v.size()<<"\n";
for(int i=0;i<v.size();i++){
cout<<v[i]<<"\n";
}좋다.
제출
<algorithm>을 include안해줘서 컴파일 에러가 떴지만
그래도 정답이다 😂
😎FULL CODE💯
#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
int arr[t+2][t+2];
int checked[t+2][t+2];
int cnt = 1;
stack<pair<int,int>> s;
vector<int> v;
for(int i=0;i<t+2;i++){
fill_n(arr[i],t+2,0);
fill_n(checked[i],t+2,0);
}
for(int i=1;i<t+1;i++){
string a; cin>>a;
for(int j=0;j<a.size();j++){
arr[i][j+1] = a[j] - '0';
}
}
for(int i=1;i<t+1;i++){
for(int j=1;j<t+1;j++){
if(arr[i][j] == 0) continue;
else{
//arr[i][j]가 숫자일 때
if(checked[i][j] == 0){
//방문한 적 없는 곳이라면
s.push(make_pair(i,j));
int chk = 0;
while(!s.empty()){
pair<int,int> p = s.top();
s.pop();
int x = p.first;
int y = p.second;
if(checked[x][y] != 0) continue;
checked[x][y] = cnt;
chk++;
if(arr[x+1][y] != 0) s.push(make_pair(x+1,y));
if(arr[x][y+1] != 0) s.push(make_pair(x,y+1));
if(arr[x-1][y] != 0) s.push(make_pair(x-1,y));
if(arr[x][y-1] != 0) s.push(make_pair(x,y-1));
}
v.push_back(chk);
chk = 0;
cnt++;
}else{
continue;
}
}
}
}
// for(int i=0;i<t+2;i++){
// for(int j=0;j<t+2;j++){
// cout<<arr[i][j];
// }
// cout<<'\n';
// }
// cout<<"\n";
//
// for(int i=0;i<t+2;i++){
// for(int j=0;j<t+2;j++){
// cout<<checked[i][j];
// }
// cout<<'\n';
// }
sort(v.begin(),v.end(),less<int>());
cout<<v.size()<<"\n";
for(int i=0;i<v.size();i++){
cout<<v[i]<<"\n";
}
}비고
어제 풀었는데 오늘 정리를 하려고 하니까 정리가 잘 안된다.
생각의 흐름에 구멍이 생기더라 😢
다음부터는 하나씩 정리를 할 때는 꼭 문제를 풀면서 의식의 흐름에 따라 정리를 할 수 있도록 해야겠다.
