๋ฌด๋ํ ๊ทธ๋ํ ํ์ ๋ฌธ์ ์ด๊ณ BFS, DFS๋ก ํ ์ ์๋๋ฐ ๋๋ BFS๋ก ํ์ด๋ณด์๋ค.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
const int MAX = 501;
int map[MAX][MAX]={0,}; // ์
๋ ฅ๊ฐ ์ ์ฅ
int visited[MAX][MAX]={0,};
int dy[] = {-1, 0, 1, 0}; // ์๊ณ๋ฐฉํฅ
int dx[] = {0, 1, 0, -1}; // ์๊ณ๋ฐฉํฅ
queue<pair<int,int>> q; // BFS ์ฌ์ฉ ํ
vector<int> v; // ๊ทธ๋ฆผ ๊ฐ์ ์ ์ฅ ๋ฒกํฐ
int s = 1; // ๊ทธ๋ฆผ ๋์ด
void bfs(int y, int x){
visited[y][x] = true;
q.push(make_pair(y,x));
while(!q.empty()){
y = q.front().first;
x = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny<0 || nx<0 || ny>=n || nx >=m) continue;
if(map[ny][nx] == 1 && visited[ny][nx]==0){
visited[ny][nx]=true;
s++; // ๊ทธ๋ฆผ ๋์ด ์นด์ดํธํด์ฃผ๊ธฐ
q.push(make_pair(ny,nx));
}
}
}
}
// ๋ฒกํฐ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ ์ํด~
bool compare(int i, int j){
return i > j;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> map[i][j];
}
}
int cnt = 0; // connected component ๊ฐ์
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(map[i][j]==1 && visited[i][j]==0){
bfs(i,j);
v.push_back(s);
cnt++;
s = 1; // ์ด๊ธฐํ ํด์ฃผ๊ธฐ~
}
}
}
sort(v.begin(), v.end(), compare); //๋ฒกํฐ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
cout << cnt << endl;
if(cnt == 0){
cout << 0 << endl;
}
else{
cout << v[0] << endl;
}
}
๋ฌด๋ํ ๊ทธ๋ํ ํ์ ๋ฌธ์ ์ด๊ณ BFS, DFS๋ก ํ ์ ์๋๋ฐ ๋๋ DFS๋ก ํ์ด๋ณด์๋ค.
์ง๋์ ์ ๋ณด๋ฅผ ๋ด์ 2์ฐจ์ ๋ฐฐ์ด map
, ๋ฐฉ๋ฌธํ๋์ง ํ๋จํ๊ธฐ ์ํ visited
2์ฐจ์ ๋ฐฐ์ด, ๊ทธ๋ฆฌ๊ณ ๋ต์ ์ถ๋ ฅํ๊ธฐ ์ํ resVec
๋ฒกํฐ๋ฅผ ์ ์ธํ๋ค.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int map[25][25];
int visited[25][25];
vector<int> resVec;
int dy[4] = {-1, 0, 1, 0}; // ์๊ณ๋ฐฉํฅ
int dx[4] = {0, 1, 0, -1}; // ์๊ณ๋ฐฉํฅ
int n, cnt;
void dfs(int y, int x){
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny > =n || nx > =n) continue;
if(visited[ny][nx] == 0 && map[ny][nx] == 1){
// ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ง์ด ์๋ค๋ฉด
visited[ny][nx] == 1; // ๋ฐฉ๋ฌธ ํ์
cnt += 1;
dfs(ny,nx); // ์ฌ๊ท
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int res = 0;
cin >> n;
string str;
for (int i = 0; i < n; i++){
cin >> str;
for(int j = 0; j <str.length(); j++){
visited[i][j] = 0; // ์ด๊ธฐํ
if(str[j] == '1'){
map[i][j] = 1;
}
else map[i][j] = 0;
}
}
for (int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(map[i][j] == 1 && visited[i][j] == 0){
visited[i][j] = 1;
cnt = 1; //์ฒ์์ ์์์ ์ ํฌํจํ๋ฏ๋ก 1๋ก ์ด๊ธฐํํ๋ค
dfs(i,j); // ์์
resVec.push_back(cnt);
res++; // ๋จ์ง ๊ทธ๋ฃน 1๊ฐ ํ์ ๋๋จ
}
}
}
sort(resVec.begin(), resVec.end()); //์ค๋ฆ์ฐจ์ ์ ๋ ฌ
cout << res << "\n"; // ๋จ์ง ๊ฐ์
for(int i = 0; i < resVec.size(); i++){
cout << resVec[i] << "\n";
}
return 0;
}
๋ฌธ์ ๋งํฌ
์ต์, ์ต๋, ์๊ฑฐ๋, ์๊ฑฐ๋ ๋ฐ๋ก๋ฅผ ์ฒดํฌํด์ค์ผ ํ๋ค.
#include<bits/stdc++.h>
using namespace std;
int a[101][101], visited[101][101], n, ret = 1; // ๋น๊ฐ ์์ฌ ๋๋ ์๊ฐํด์ ret์ 1๋ก ์ด๊ธฐํ๋ฅผ ํด์ค์ผ ํ๋ค.
int dy[4]={-1,0,1,0}, dx[4]={0,1,0,-1};
void dfs(int y, int x, int d)
{
visited[y][x]=1;
for(int i=0; i<4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
if(!visited[ny][nx] && a[ny][nx] > d)
dfs(ny, nx, d);
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin >> a[i][j];
}
}
// depth ๊ฒํ
for(int d=1; d<101; d++)
{
// ํ
์คํธ์ผ์ด์ค๋ง๋ค ์ด๊ธฐํํด์ค์ผ ํ๋ค
fill(&visited[0][0], &visited[0][0]+ 101*101, 0);
int cnt = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(a[i][j] > d && !visited[i][j])
{
dfs(i, j, d);
cnt++;
}
}
}
ret = max(ret, cnt);
}
cout << ret << '\n';
return 0;
}
๋ฌธ์ ๋งํฌ
๋ฌธ์ ์์ ์ฃผ์ด์ง ์ฌ๊ฐํ์ ๊ธฐ๋ฐ์ผ๋ก ์์ญ์ ๋ง๋ค๊ณ ๋๋จธ์ง ์์ญ์ ์ฌ์ด์ฆ๋ฅผ ๊ตฌํด ๋ฒกํฐ์ ๋ด์์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํด์ ์ถ๋ ฅํ๋ฉด ๋๋ค.
#include<bits/stdc++.h>
using namespace std;
#define y1 aaaa
int a[104][104], m,n,k,x1,x2, y1,y2, visited[104][104];
const int dy[4]={-1,0,1,0};
const int dx[4]={0,1,0,-1};
vector<int> ret;
int dfs(int y, int x) // int ๋ฐํ dfs ๋ฅผ ๋ง๋๋ ๊ฒ์ด ํต์ฌ์ด๋ค
{
visited[y][x]=1;
int ret = 1;
for(int i=0; i<4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(ny<0 || ny>= m || nx<0 || nx>=n || visited[ny][nx]==1) continue;
if(a[ny][nx]==1) continue;
ret += dfs(ny, nx);
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> m >> n >> k;
for(int i=0; i<k; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
for(int x = x1; x < x2; x++)
{
for(int y = y1; y < y2; y++)
{
a[y][x] = 1;
}
}
}
// ๋๋จธ์ง ์์ญ์ผ๋ก๋ถํฐ connected component ์ป์ด์ค๊ธฐ
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
if(a[i][j] != 1 && visited[i][j]==0)
{
ret.push_back(dfs(i,j));
}
}
}
sort(ret.begin(), ret.end());
cout << ret.size() << '\n';
for(int a : ret) cout << a << " ";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n,m,j,l,r,temp,ret;
int main()
{
cin >> n >> m >> j;
l=1;
for(int i=0; i<j; i++)
{
r=l+m-1; // ์๋ก ์ ์
cin >> temp;
if(temp>=l && temp<=r) continue; // ์ฌ๊ณผ๊ฐ ๋ฐ๊ตฌ๋์ ๊ฑธ์น๋ฉด continue
else
{
// l ์์
if(temp<l)
{
ret+= (l-temp);
l=temp;
}
else
{
l+=(temp-r);
ret+=(temp-r);
}
}
}
cout << ret << '\n';
return 0;
}
๋ฌธ์ ๋งํฌ
๋ฌธ์๋ฅผ ๊ฒฐ๊ตญ intํ ๋ฐฐ์ด๋ก ๋ง๋๋ ๋ฌธ์ ์ด๋ค
int a = 0, cnt = 1;
cout << a = cnt++ << endl; // a ๋ 1 ์ด๋ค. cnt ๋ 1์ด๋ค
cout << cnt << endl; // cnt ๊ฐ ์ฌ๊ธฐ์ 2๊ฐ ๋๋ค
int a = 0, cnt = 1;
cout << a = ++cnt << endl; // a ๋ 2 ์ด๋ค. cnt ๋ 2์ด๋ค
์์ ์์๋ฅผ ํท๊ฐ๋ฆฌ์ง ์๋๋ก!!
#include<bits/stdc++.h>
using namespace std;
int n,m,a[104][104]; // H,W,C์ ๋ณด
string s;
int main()
{
cin >> n >> m;
for(int i=0; i<n; i++)
{
cin >> s;
for(int j=0; j<m; j++)
{
if(s[j]=='.') a[i][j] = -1;
else a[i][j] = 0;
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(a[i][j]==0){
int cnt = 1;
while(a[i][j+1] == -1)
{
a[i][j+1]=cnt++;
j++;
}
}
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++) cout << a[i][j] << " ";
cout << '\n';
}
return 0;
}