알고리즘 문제
[백준] 4963번 섬의 개수
feelcoding
2020. 2. 6. 21:55
728x90
4963번: 섬의 개수
문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는
www.acmicpc.net
왼쪽 오른쪽 위 아래 뿐만 아니라 대각선까지 되는 DFS, BFS 문제는 처음 봤다. 하지만 푸는 방법은 똑같으니 쉽게 풀 수 있었다.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int main() {
while (true) {
int w, h;
cin >> w >> h;
if (w == 0 && h == 0) break;
vector<vector<int>> v(h);
vector<vector<bool>> visited(h);
for (int i = 0; i < h; i++) {
v[i] = vector<int>(w);
visited[i] = vector<bool>(w);
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> v[i][j];
}
}
int count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (v[i][j] == 1 && !visited[i][j]) {
count++;
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
if (!visited[cur.first][cur.second]) {
visited[cur.first][cur.second] = true;
if (cur.first + 1 < h && cur.second + 1 < w && !visited[cur.first + 1][cur.second + 1] && v[cur.first + 1][cur.second + 1] == 1) {
q.push(make_pair(cur.first + 1, cur.second + 1));
}
if (cur.first + 1 < h && cur.second - 1 >= 0 && !visited[cur.first + 1][cur.second - 1] && v[cur.first + 1][cur.second - 1] == 1) {
q.push(make_pair(cur.first + 1, cur.second - 1));
}
if (cur.first - 1 >= 0 && cur.second + 1 < w && !visited[cur.first - 1][cur.second + 1] && v[cur.first - 1][cur.second + 1] == 1) {
q.push(make_pair(cur.first - 1, cur.second + 1));
}
if (cur.first - 1 >= 0 && cur.second - 1 >= 0 && !visited[cur.first - 1][cur.second - 1] && v[cur.first - 1][cur.second - 1] == 1) {
q.push(make_pair(cur.first - 1, cur.second - 1));
}
if (cur.first + 1 < h && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 1) {
q.push(make_pair(cur.first + 1, cur.second));
}
if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 1) {
q.push(make_pair(cur.first - 1, cur.second));
}
if (cur.second + 1 < w && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 1) {
q.push(make_pair(cur.first, cur.second + 1));
}
if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 1) {
q.push(make_pair(cur.first, cur.second - 1));
}
}
}
}
}
}
cout << count << endl;
}
return 0;
}728x90