반응형
[문제]
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
[나의 풀이]
문제
1. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하시오.
입력
1. 지도의 크기 N을 입력 받는다.
2. N * N의 지도를 입력 받는다. 반복문
처리
1. 반복문을 돌려 이차원 배열의 값이 1이고 이차원 배열 bool 타입이 false일때 bfs함수를 실행시킨다.
2. bfs에서 해당 좌표값을 queue로 받은뒤 true로 바꿔주고 count+1한 후 while문을 돌린다.
2-1. while문에서는 좌표값을 꺼내주고 for문을 돌린다.for문을 돌릴때 4번 돌려 상하좌우로 움직였을때 1인 값이 있으면 true로 바꿔주고 push해준다. 또한 count+1해준다.
3. 카운트값을 다 구했으면 함수를 종료후 단지수를 늘려주고 카운트는 초기화 시킨다.
4. 다음 단지수의 배열에 또 찾아서 삽입하는 방식으로 사용한다.
출력
1. 단지수별로 몇개 카운트 됬는지 출력한다.
[소스 코드]
내 풀이)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> graph[25];
vector<int> danjiVec;
//이차원 배열로 받아야 한다.
bool isVisited[25][25] = {false};
int cnt = 0; //카운트할 단지수
int dx[4] = {1,-1,0,0}; // x
int dy[4] = {0,0,-1,1}; // y
int N = 0;
void bfs(int y, int x)
{
queue<pair<int, int>> que;
que.push({ y,x });
isVisited[y][x] = true;
cnt++;
while (!que.empty())
{
y = que.front().first;
x = que.front().second;
que.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= 0 && nx >= 0 && nx < N && ny < N && graph[ny][nx] == 1 && isVisited[ny][nx] == false)
{
isVisited[ny][nx] = true;
cnt++;
que.push({ ny,nx });
}
}
}
}
int main()
{
//
// 문제
// 1. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하시오.
// 입력
// 1. 지도의 크기 N을 입력 받는다.
// 2. N * N의 지도를 입력 받는다. 반복문
// 처리
// 1. 반복문을 돌려 이차원 배열의 값이 1이고 이차원 배열 bool 타입이 false일때 bfs함수를 실행시킨다.
// 2. bfs에서 해당 좌표값을 queue로 받은뒤 true로 바꿔주고 count+1한 후 while문을 돌린다.
// 2-1. while문에서는 좌표값을 꺼내주고 for문을 돌린다.for문을 돌릴때 4번 돌려 상하좌우로 움직였을때 1인 값이 있으면 true로 바꿔주고 push해준다. 또한 count+1해준다.
// 3. 카운트값을 다 구했으면 함수를 종료후 단지수를 늘려주고 카운트는 초기화 시킨다.
// 4. 다음 단지수의 배열에 또 찾아서 삽입하는 방식으로 사용한다.
// 출력
// 1. 단지수별로 몇개 카운트 됬는지 출력한다.
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
//인접 행렬로 구성됨
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
char map;
cin >> map;
int test = map - '0';
graph[i].push_back(test);
}
}
int danji = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (graph[i][j] == 1 && isVisited[i][j] == false)
{
bfs(i,j);
danjiVec.push_back(cnt);
cnt = 0;
}
}
}
cout << danjiVec.size() << "\n";
sort(danjiVec.begin(), danjiVec.end());
for (int element : danjiVec)
{
cout << element << "\n";
}
return 0;
}다른 풀이)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int map[25][25];
bool isVisited[25][25];
// 반환 값의 의미는 단지 내 집의 개수
int dfs(int r, int c)
{
isVisited[r][c] = true;
static const int dr[] = { -1, 1, 0, 0 };
static const int dc[] = { 0, 0, -1, 1 };
int houseCount = 1;
for (int i = 0; i < 4; ++i)
{
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 0 || nr >= N || nc < 0 || nc >= N)
continue;
if (isVisited[nr][nc] || map[nr][nc] == 0)
continue;
houseCount += dfs(nr, nc);
}
return houseCount;
}
int main()
{
// 1. N을 입력 받는다.
scanf("%d", &N);
// 2. 단지의 모습을 입력 받는다.
for (int r = 0; r < N; ++r)
{
for (int c = 0; c < N; ++c)
scanf("%1d", &map[r][c]);
}
// 3. 단지 수와 단지 내 집의 개수를 구한다.
int complexCount = 0;
vector<int> houseCounts;
for (int r = 0; r < N; ++r)
{
for (int c = 0; c < N; ++c)
{
// 집을 찾았고, 방문하지 않았다면?
if (map[r][c] == 1 && isVisited[r][c] == false)
{
int houseCount = dfs(r, c);
houseCounts.push_back(houseCount);
++complexCount;
}
}
}
sort(houseCounts.begin(), houseCounts.end());
// 4. 출력한다.
printf("%d\n", complexCount);
for (int houseCount : houseCounts)
printf("%d\n", houseCount);
}[피드백]
반응형