https://www.acmicpc.net/problem/1012
๋ฌธ์
์ฐจ์ธ๋ ์๋์ธ ํ๋๋ ๊ฐ์๋ ๊ณ ๋ญ์ง์์ ์ ๊ธฐ๋ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๊ธฐ๋ก ํ์๋ค. ๋์ฝ์ ์ฐ์ง ์๊ณ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๋ ค๋ฉด ๋ฐฐ์ถ๋ฅผ ํด์ถฉ์ผ๋ก๋ถํฐ ๋ณดํธํ๋ ๊ฒ์ด ์ค์ํ๊ธฐ ๋๋ฌธ์, ํ๋๋ ํด์ถฉ ๋ฐฉ์ง์ ํจ๊ณผ์ ์ธ ๋ฐฐ์ถํฐ์ง๋ ์ด๋ฅผ ๊ตฌ์ ํ๊ธฐ๋ก ๊ฒฐ์ฌํ๋ค. ์ด ์ง๋ ์ด๋ ๋ฐฐ์ถ๊ทผ์ฒ์ ์์ํ๋ฉฐ ํด์ถฉ์ ์ก์ ๋จน์์ผ๋ก์จ ๋ฐฐ์ถ๋ฅผ ๋ณดํธํ๋ค. ํนํ, ์ด๋ค ๋ฐฐ์ถ์ ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ํ ๋ง๋ฆฌ๋ผ๋ ์ด๊ณ ์์ผ๋ฉด ์ด ์ง๋ ์ด๋ ์ธ์ ํ ๋ค๋ฅธ ๋ฐฐ์ถ๋ก ์ด๋ํ ์ ์์ด, ๊ทธ ๋ฐฐ์ถ๋ค ์ญ์ ํด์ถฉ์ผ๋ก๋ถํฐ ๋ณดํธ๋ฐ์ ์ ์๋ค. ํ ๋ฐฐ์ถ์ ์ํ์ข์ฐ ๋ค ๋ฐฉํฅ์ ๋ค๋ฅธ ๋ฐฐ์ถ๊ฐ ์์นํ ๊ฒฝ์ฐ์ ์๋ก ์ธ์ ํด์๋ ๊ฒ์ด๋ค.
ํ๋๊ฐ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๋ ๋ ์ ๊ณ ๋ฅด์ง ๋ชปํด์ ๋ฐฐ์ถ๋ฅผ ๊ตฐ๋ฐ๊ตฐ๋ฐ ์ฌ์ด ๋์๋ค. ๋ฐฐ์ถ๋ค์ด ๋ชจ์ฌ์๋ ๊ณณ์๋ ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ํ ๋ง๋ฆฌ๋ง ์์ผ๋ฉด ๋๋ฏ๋ก ์๋ก ์ธ์ ํด์๋ ๋ฐฐ์ถ๋ค์ด ๋ช ๊ตฐ๋ฐ์ ํผ์ ธ์๋์ง ์กฐ์ฌํ๋ฉด ์ด ๋ช ๋ง๋ฆฌ์ ์ง๋ ์ด๊ฐ ํ์ํ์ง ์ ์ ์๋ค. ์๋ฅผ ๋ค์ด ๋ฐฐ์ถ๋ฐญ์ด ์๋์ ๊ฐ์ด ๊ตฌ์ฑ๋์ด ์์ผ๋ฉด ์ต์ 5๋ง๋ฆฌ์ ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ํ์ํ๋ค. 0์ ๋ฐฐ์ถ๊ฐ ์ฌ์ด์ ธ ์์ง ์์ ๋ ์ด๊ณ , 1์ ๋ฐฐ์ถ๊ฐ ์ฌ์ด์ ธ ์๋ ๋ ์ ๋ํ๋ธ๋ค.
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
์ ๋ ฅ
์ ๋ ฅ์ ์ฒซ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ทธ ๋ค์ ์ค๋ถํฐ ๊ฐ๊ฐ์ ํ ์คํธ ์ผ์ด์ค์ ๋ํด ์ฒซ์งธ ์ค์๋ ๋ฐฐ์ถ๋ฅผ ์ฌ์ ๋ฐฐ์ถ๋ฐญ์ ๊ฐ๋ก๊ธธ์ด M(1 ≤ M ≤ 50)๊ณผ ์ธ๋ก๊ธธ์ด N(1 ≤ N ≤ 50), ๊ทธ๋ฆฌ๊ณ ๋ฐฐ์ถ๊ฐ ์ฌ์ด์ ธ ์๋ ์์น์ ๊ฐ์ K(1 ≤ K ≤ 2500)์ด ์ฃผ์ด์ง๋ค. ๊ทธ ๋ค์ K์ค์๋ ๋ฐฐ์ถ์ ์์น X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)๊ฐ ์ฃผ์ด์ง๋ค. ๋ ๋ฐฐ์ถ์ ์์น๊ฐ ๊ฐ์ ๊ฒฝ์ฐ๋ ์๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด ํ์ํ ์ต์์ ๋ฐฐ์ถํฐ์ง๋ ์ด ๋ง๋ฆฌ ์๋ฅผ ์ถ๋ ฅํ๋ค.
์ค๋ฒ2
๋จ์ํ bfs ๋ฌธ์ ์ด๊ธด ํ๋ฐ,,, ์ข ๋๋ฝ์ต๋๋ค
์๋๋ฉด x์ y๊ฐ ๋ฐ๋๊ฑฐ๋ ์ ^^
์ ๋ ฅ๋ฐ์๋ ๊ทธ๋ฅ ๋ฐ๋๋ก ๋ฐ๋๊ฒ ์ ์ผ ๊ฐ๋จํ๋ฏ
๋์ ํ์ด
#include <iostream>
#include <queue>
using namespace std;
int m;
int n;
int k;
int visited[50][50];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
bool canGo(int map[50][50],int x, int y){
if(x<0 || y<0 || x>=n ||y>=m) return false;
if(map[x][y] == 0) return false;
if(visited[x][y]) return false;
return true;
}
void bfs(int map[50][50], int x, int y){
queue<pair<int, int>> q;
q.push({x, y});
visited[x][y] = 1;
while(!q.empty()){
pair<int, int> a = q.front();
q.pop();
for (int i = 0; i < 4; ++i){
int nx = a.first + dx[i];
int ny = a.second + dy[i];
if(canGo(map, nx, ny)){
visited[nx][ny] = 1;
q.push({nx, ny});
}
}
}
}
int main(){
int t;
cin >> t;
int x, y;
for (int i = 0; i < t; ++i){
int cnt = 0;
int map[50][50] = {0,};
cin >> m >> n >> k;
for (int j = 0; j < k; ++j){
cin >> y >> x;
map[x][y] = 1;
}
for (int j = 0; j < n;++j){
for (int h = 0; h < m; ++h){
if (map[j][h] == 1 && visited[j][h] == 0){
bfs(map, j, h);
cnt++;
}
}
}
cout << cnt << "\n";
for (int j = 0; j < n;++j){
for (int h = 0; h < m; ++h){
visited[j][h] = 0;
}
}
}
}
'๐ ์๊ณ ๋ฆฌ์ฆ > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/BOJ] 2644 : ์ด์๊ณ์ฐ (๋ค์ต์คํธ๋ผ) (0) | 2023.05.18 |
---|---|
[C++/BOJ] 1325 : ํจ์จ์ ์ธ ํดํน (BFS/DFS) (1) | 2023.05.14 |
[C++/BOJ] 1417 : ๊ตญํ์์ ์ ๊ฑฐ (์๋ฃ๊ตฌ์กฐ) (1) | 2023.05.06 |
[C++/BOJ] 9012 : ๊ดํธ (์๋ฃ๊ตฌ์กฐ) (1) | 2023.05.06 |
[C++/BOJ] 11286 : ์ ๋๊ฐ ํ (์๋ฃ๊ตฌ์กฐ) (0) | 2023.05.02 |