백준 2667번 단지번호붙이기
설명
BFS를 이용하여 기본적으로 풀었다.
queue에 넣어줄때와, 처음에 각각 count를 이용하여 가구 수를 구하였으며
main문에서 graph에서 1 이지만 아직 방문하지 않은곳이 있다면 houseCnt++ 후 들어가도록 설계했다
소스 코드
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int dx[] = { -1,1,0,0 };
bool visited[26][26];
int dy[] = { 0,0,1,-1 };
int graph[26][26];
int cnt = 0;
int k;
int houseCnt = 0;
int houseNum[10000];
void bfs(int start,int now) {
queue<pair<int, int>> q;
visited[start][now] = true;
q.push({ start,now });
houseNum[houseCnt]++;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (graph[ny][nx] == 0) continue;
if (nx < 0 || nx >= k || ny < 0 || ny >= k) continue;
if (!visited[ny][nx]) {
q.push({ ny,nx });
visited[ny][nx] = true;
houseNum[houseCnt]++;
}
}
}
}
int main()
{
cin >> k;
for (int y = 0; y < k; y++) {
for (int x = 0; x < k; x++) {
scanf("%1d", &graph[y][x]);
}
}
for (int y = 0; y < k; y++) {
for (int x = 0; x < k; x++) {
if (visited[y][x] == false && graph[y][x] == 1) {
houseCnt++;
bfs(y,x);
}
}
}
cout << houseCnt << endl;
sort(houseNum + 1, houseNum + houseCnt+1);
for (int i = 1; i <= houseCnt; i++) {
cout << houseNum[i] << endl;
}
return 0;
}
Author And Source
이 문제에 관하여(백준 2667번 단지번호붙이기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@trevor522/백준-2667번-단지번호붙이기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int dx[] = { -1,1,0,0 };
bool visited[26][26];
int dy[] = { 0,0,1,-1 };
int graph[26][26];
int cnt = 0;
int k;
int houseCnt = 0;
int houseNum[10000];
void bfs(int start,int now) {
queue<pair<int, int>> q;
visited[start][now] = true;
q.push({ start,now });
houseNum[houseCnt]++;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (graph[ny][nx] == 0) continue;
if (nx < 0 || nx >= k || ny < 0 || ny >= k) continue;
if (!visited[ny][nx]) {
q.push({ ny,nx });
visited[ny][nx] = true;
houseNum[houseCnt]++;
}
}
}
}
int main()
{
cin >> k;
for (int y = 0; y < k; y++) {
for (int x = 0; x < k; x++) {
scanf("%1d", &graph[y][x]);
}
}
for (int y = 0; y < k; y++) {
for (int x = 0; x < k; x++) {
if (visited[y][x] == false && graph[y][x] == 1) {
houseCnt++;
bfs(y,x);
}
}
}
cout << houseCnt << endl;
sort(houseNum + 1, houseNum + houseCnt+1);
for (int i = 1; i <= houseCnt; i++) {
cout << houseNum[i] << endl;
}
return 0;
}
Author And Source
이 문제에 관하여(백준 2667번 단지번호붙이기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@trevor522/백준-2667번-단지번호붙이기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)