안녕하세요! 저녁으로 김치찌개를 먹을 예정인 GCOCO입니다!
잡설 한 COOKIE🍪
아웅...... 오늘은 헬스장에 가서 가슴운동을 하고왔습니다!
친구와 함께 같이 운동을 가자고 권유했지만 친구는 '아니 어제도 갔는데 뭘 또 감? 너나 가셈!'
이라고 말해주더군요...
하지만 나 GCOCO 아주 조금씩 성장하는 남자.
바로 운동하러 다녀왔습니다!
하지만 요즘 운동 할 때 어떤것의 문제인지 오른쪽 어깨에 부하가 더 많이 걸리고 동작시 불편함을 느낍니다!
시간을 내어 정형외과에 한 번 다녀와봐야겠습니다 ^_^
자, 이전의 포스팅에서 다뤘던 문제를 BFS로 한 번 같이 풀어보시죠!
문제
문제는 다음과 같습니다.
- 길이가 n인 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
이 지도를 가지고 연결된 집의 수와 단지를 세려고 한다. - 연결된 집이란 상 하 좌 우로 연결된 것을 말한다. 대각선상의 경우는 연결된 것이 아니다.
- 지도를 입력하고, 단지의 수의 수와 각 단지에 속하는 집의 수를 오름차순으로 출력하시오.
입력은 다음과 같이 주어집니다!
5
10101
01010
10101
01010
10101해당하는 출력은 다음과 같습니다.
13
1
1
1
1
1
1
1
1
1
1
1
1
1풀이
또 다른 이전의 포스팅에서 같이 BFS를 공부한 적이 있었죠?
이때 공부를 해 둔것이, 이번 풀이에 많은 도움이 되었습니다!
코드를 같이 보자구요~
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int dx[4] = { 0,0,-1,1};
int dy[4] = { -1,1,0,0};
int bfs(pair<int,int> &start,vector<vector<bool>> &visited,vector<vector<int>> &v,int &count,int &n){
if(visited[start.first][start.second])
return 0;
queue<pair<int,int>> q;
q.push(start);
visited[start.first][start.second]=true;
count++;
while(!q.empty()){
int row = q.front().first;
int col = q.front().second;
q.pop();
for(int i=0;i<4;i++){
int nx = row+dx[i];
int ny = col+dy[i];
//범위 내의 값이고
if(0<=nx && nx<n && 0<=ny && ny<n){
if(!visited[nx][ny] && v[nx][ny]){
visited[nx][ny]=true;
count++;
q.push(make_pair(nx,ny));
}
}
}
}
return count;
}
int main(void) {
int n;
cin >> n;//n입력
vector<vector<int>> v(n, vector<int>(n, 0));//지도 만들기
vector<vector<bool>> visited(n, vector<bool>(n, false));//방문표시
vector<int> answer;//답을 담을 vector answer
//지도 입력
for (int i = 0; i < n; i++) {
string tmp;
cin >> tmp;
for (int j = 0; j < n; j++) {
v[i][j] = tmp[j] - '0';
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int count =0;
if(v[i][j]){
pair<int,int> start = make_pair(i,j);
bfs(start,visited,v,count,n);
}
if(count)
answer.emplace_back(count);
}
}
//answer 정렬
sort(answer.begin(),answer.end());
cout<<answer.size()<<endl;
for (auto i : answer)
cout << i << endl;
return 0;
}제 풀이의 step은 다음과 같습니다.
- 지도를 입력받는다.
- 지도를 돌며 v[i][j]==1일 경우 좌표를 bfs에 넘긴다.
- return값이 양수일 경우 answer에 담는다.
BFS 함수를 짚어보겠습니다.
- 좌표가 방문한 지점이라면 return 0;
- 아닐 경우 q에 push, 방문 표기, count 값 1 증가
- q가 빌 때까지, q에 있는 좌표를 꺼내어 for에서 탐색 시작
- for문 내에서, 범위 내의 값이고, 방문하지 않았으며, 집이 있는곳(v[nx][ny]==1)이라면
- 방문을 표기하고 갯수 증가 및 q에 추가.
- q가 빌 때까지 반복
즉 시작점에서 조건에 맞는 인접점들을 찾아가며 확장한다고 생각하시면 되겠습니다!
개선
하지만 제가 처음 작성한 코드는, 넘기는 인자들도 많고 중복된 검사들도 한다는 것을 알게 되었습니다!
이를 GPT를 이용해 개선해봅시다!
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int bfs(pair<int,int> start, vector<vector<int>>& v, vector<vector<bool>>& visited) {
int count = 0;
queue<pair<int,int>> q;
q.push(start);
visited[start.first][start.second] = true;
while (!q.empty()) {
int row = q.front().first;
int col = q.front().second;
q.pop();
count++;
for (int i = 0; i < 4; i++) {
int nx = row + dx[i];
int ny = col + dy[i];
if (0<= nx && nx < v.size() && 0<=ny && ny < v[0].size()) {
if (!visited[nx][ny] && v[nx][ny]) {
visited[nx][ny] = true;
q.push(make_pair(nx, ny));
}
}
}
}
return count;
}
int main(void) {
int n;
cin >> n;
vector<vector<int>> v(n, vector<int>(n, 0));
vector<vector<bool>> visited(n, vector<bool>(n, false));
vector<int> answer;
for (int i = 0; i < n; i++) {
string tmp;
cin >> tmp;
for (int j = 0; j < n; j++) {
v[i][j] = tmp[j] - '0';
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (v[i][j] && !visited[i][j]) {
answer.push_back(bfs(make_pair(i, j), v, visited));
}
}
}
sort(answer.begin(), answer.end());
cout << answer.size() << endl;
for (auto i : answer)
cout << i << endl;
return 0;
}
제가 작성했던 코드와 비교해 보자면, 우선 BFS로 넘기는 인자의 갯수가 줄었습니다!
좀 더 한눈에 알아볼 수 있게 되었습니다.
또한 중복된 검사를 없애고 while문 안에서 첫번째로 q가 pop된 이후 숫자를 셈을 알 수 있습니다.
main문에선 집이 있으면서, 방문하지 않은 경우를 조건문으로 bfs를 실행하고, 이의 return값을 answer에 담고 있습니다.
개선된 코드가 좀 더 명료히 이해하기 쉬운것 같습니다!
좋은 피드백입니다.
항상 느끼는 것이지만 한 분야의 고수가 되는 길은 정말로 멀고 험난한 것 같습니다.
'그럼에도 불구하고'
나아가는 GCOCO가 되도록 하겠습니다.
이상으로 포스팅 마치겠습니다!
