๋ฌธ์
๊ณผ๊ฑฐ์ c++๋ก ํ์ดํ์๋ ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ ๋ฌธ์ ๋ฅผ ํ์ด์ฌ์ผ๋ก ๋ค์ ํ์ด๋ณด์์ต๋๋ค. dfs ํ์ด์ฌ ํ์ด๋ฒ์ ์์ ์ตํ๊ณ ์๋ ์ค์ธ๋ฐ์. ํ์คํ c++์ ๋นํด ํํ๋ ฅ์ด ์ข๋ค๋ ๋ง์ด ์ค๊ฐ์ด ๋ฉ๋๋ค.
C++๊ณผ์ ๋น๊ต
c++์ ๊ฒฝ์ฐ์๋ dfs๋ vector ๋ฐฐ์ด๋ก, bfs๋ queue์ ์ฌ์ฉํ์ต๋๋ค. ๋ํ, queue๋ฅผ ์ฌ์ฉํ๋ ๋งํผ ํ์ด๋ฒ ์์ฒด๋ ๋ฏธ๋ฌํ๊ฒ ๋ฌ๋์๋๋ฐ์.
python์ ๊ฒฝ์ฐ์๋ dfs๋ list๋ก, bfs๋ deque(list๋ฅผ ์ฌ์ฉํ ์๋ ์์ง๋ง, pop(0)์ ์๊ฐ๋ณต์ก๋๊ฐ O(N)์ด๊ธฐ ๋๋ฌธ์, popleft์ ์๊ฐ๋ณต์ก๋๊ฐ O(1)์ด ๋์ค๋ deque๋ฅผ ์ฌ์ฉ)๋ก ํ๊ฒ ๋๋ฉฐ, ์๋ฃ๊ตฌ์กฐ๋ง ๋ค๋ฅผ ๋ฟ ํ์ด๊ฐ ๊ฑฐ์ ๊ฐ์์ง๊ฒ ๋ฉ๋๋ค. ๊ทธ๋งํผ ํ์ด ๋์ค dfs์์ bfs๋ก์ ์ ํ์ด ๋น ๋ฅผ ๊ฒ์ด๋ผ ์์์ด ๋ฉ๋๋ค.
ํ์ด
dfs, bfs ์ค ์์ ์ต์ ์ด๋ค ๊ฒ์ผ๋ก ํธ์ ๋ ์๊ด์๋ ๋ฌธ์ ์ ๋๋ค. ์ ๊ฒฝ์ฐ์๋ ์ง๋ ํ์ด ๋์ dfs๋ก ํ์์๊ธฐ ๋๋ฌธ์, ๋น๊ต๋ฅผ ์ํด dfs๋ก ํ์์ต๋๋ค.
ํฐ ํ์ ๋ฉ์ธ์์
- ๋ชจ๋ ๋ ธ๋๋ฅผ ์ํํ๋ฉฐ
- ์์ง ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฉฐ, ์ง์ด ์กด์ฌํ๋ ๋ ธ๋๋ฅผ ๋ง๋๋ฉด
- ๋จ์ง ์๋ฅผ ํ๋ ๋๋ฆฌ๊ณ , ํด๋น ๋จ์ง์ ์ง ๊ฐฏ์๋ฅผ 1๋ก ํ ๋นํด์ค ํ, ํด๋น ๋ ธ๋๋ฅผ ์์์ ์ผ๋ก dfs๋ฅผ ๋๋๋ค.
dfs์์๋, ๋ค์๊ณผ ๊ฐ์ ๋์์ ํฉ๋๋ค.
- ํด๋น ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ์์์ ํ์ํ๊ณ ,
- ์ด๋ ๊ฐ๋ฅํ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ๋ฉฐ dfs๋ฅผ ์ํํฉ๋๋ค. ์ด๋, ํด๋น ๋จ์ง์ ์ง ๊ฐฏ์๋ฅผ 1 ์ถ๊ฐํด์ค๋๋ค. ๋ํ ์ด๋ ๊ฐ๋ฅ์ ์กฐ๊ฑด์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- ์ ํฉํ ์ขํ๊ฐ์ผ ๊ฒ (0 ์ด์์ด๋ฉฐ, N๋ณด๋ค ์์์ผ ํฉ๋๋ค.)
- ์ง์ด ์กด์ฌํ ๊ฒ
- ๋ฐฉ๋ฌธํ ์ ์์ ๊ฒ
์ ๋ต ์ฝ๋๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ ๋ต์ฝ๋ (C++)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
using namespace std;
#define MAX 25
int MAP[MAX][MAX];
int DANJI[MAX*MAX];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int danji_cnt;
int n;
bool visited[MAX][MAX];
bool isInside(int x, int y)
{
return (x>=0 && x<n) && (y>=0 && y<n);
}
void dfs(int x, int y, int key)
{
DANJI[key]++;
visited[x][y] = true;
MAP[x][y] = key;
for(int i=0;i<4;i++)
{
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if(isInside(dx, dy) && (MAP[dx][dy] == 1))
{
if(!visited[dx][dy]) dfs(dx, dy, key);
}
}
}
void Solution(int n)
{
danji_cnt=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(MAP[i][j]==1)
{
if(!visited[i][j]) dfs(i, j, danji_cnt++);
}
}
}
}
int main()
{
cin >> n;
for(int i=0;i<n;i++)
{
DANJI[i]=0;
for(int j=0;j<n;j++)
{
scanf("%1d",&MAP[i][j]);
}
}
Solution(n);
danji_cnt--;
cout << danji_cnt << '\n';
sort(DANJI, DANJI+danji_cnt+1);
for(int i=1;i<=danji_cnt;i++)
{
cout << DANJI[i] << '\n';
}
if(DANJI[1]==0) cout << 0;
return 0;
}
์ ๋ต ์ฝ๋(Python)
N = int(input())
address = []
danjiCnt = 0
danjiArr = {}
for _ in range(N) :
address.append(list(map(int, input())))
visited = [[False]*N for _ in range(N)]
dir = [[-1,0],[1,0],[0,-1],[0,1]]
def isValidate(x,y) :
return x >= 0 and x < N and y >= 0 and y < N
def dfs(x, y) :
visited[y][x] = True
for i in range(len(dir)) :
nextX = x + dir[i][0]
nextY = y + dir[i][1]
if(isValidate(nextX, nextY) and address[nextY][nextX]==1 and visited[nextY][nextX]==False) :
danjiArr[danjiCnt]+=1
dfs(nextX, nextY)
for y in range(N) :
for x in range(N) :
if(visited[y][x]==False and address[y][x]==1) :
danjiCnt+=1
danjiArr[danjiCnt]=1
dfs(x,y)
arr = sorted(list(n for n in danjiArr.values()))
print(len(arr))
for n in arr : print(n)
๋ฉ๋ชจ๋ฆฌ, ์๋ ๋น๊ต
c++์ด ํ์คํ ๋ฉ๋ชจ๋ฆฌ๋, ์๊ฐ๋ ํจ์จ์ ์ธ ๊ฒ์ผ๋ก ํ์ธ๋ฉ๋๋ค.
๋ค๋ง ์ค์ ํ๋ก๊ทธ๋๋ฐ ํ ์คํธ์์ ๊ฐ ์ธ์ด์ ๋ง๋ ์๊ฐ ์ ํ๊ณผ ๋ฉ๋ชจ๋ฆฌ ์ ํ์ ๋ฐ๋ก ๋๊ธฐ ๋๋ฌธ์, ์ฝ๋ ๊ตฌํ๋ ฅ์ด ์ข๊ณ ๊ฐ๋ ์ฑ์ด ๋์ python์ ์์ผ๋ก๋ ์ญ ๋ฌธ์ ํ์ด์ ์ฌ์ฉํ ์์ ์ ๋๋ค. (ํนํ ๋ฌธ์์ด ํ์ฑ์ด ์๋์ ์ผ๋ก ํธํ๊ธฐ ๋๋ฌธ์โฆ)
1๋ ์ ์ฝ๋๋ฅผ ๋ค์ ๋ณด๋ ์ ์์ ๋ถ๋ถ๋ ๋ณด์ด๊ธด ํ์ง๋ง, ํจ์ ์ด๋ฆ์ด๋ ๋ณ์ ์ด๋ฆ์ด ๋์ฒด๋ก ๊ฐ์์ ๋๋์ต๋๋ค. danji๋ฅผ 1๋ ์ ์๋ danji๋ผ๊ณ ์ผ์๋ค๋โฆ ์กฐ๊ธ ๋ฏผ๋งํ๋ค์.