6장 그래프 - (3) 그래프 탐색 문제 5

1. Term Project 9466번

2. 단지번호붙이기 2667번

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

int a[25][25]; // a[i][j] : (i,j) 집

int check[25][25]; // (i,j)를 방문안했으면 0, 했으면 단지번호

int ans[25 * 25];

int n;

int nextX[4] = { 0, 0, 1, -1 };

int nextY[4] = { 1, -1, 0 , 0 };

void bfs(int x, int y, int number) {

queue<pair<int, int>> q;

q.push(make_pair(x, y));

check[x][y] = number;

while (!q.empty()) {

x = q.front().first;

y = q.front().second;

q.pop();

for (int i = 0; i < 4; i++) {

int nx = x + nextX[i];

int ny = y + nextY[i];

if (nx >= 0 && nx < n && ny >= 0 && ny < n) {

if (a[nx][ny] == 1 && check[nx][ny] == 0) {

check[nx][ny] = number;

q.push(make_pair(nx, ny));

}

}

}

}

}

int main(void) {

cin >> n;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

scanf("%1d", &a[i][j]);

}

}

int number = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (a[i][j]==1 && check[i][j] == 0)

bfs(i, j, ++number);

}

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

ans[check[i][j]]++; 

}

}

cout << number << '\n';

sort(ans + 1, ans + number + 1);

for (int i = 1; i <= number; i++) {

printf("%d\n", ans[i]);

}

return 0;

}

3. 섬의 개수 4963번

#include <iostream>

#include <queue>

#include <cstring>

using namespace std;

int a[50][50];

int check[50][50];

int nextX[8] = { 0,0,1,-1,1,1,-1,-1 };

int nextY[8] = { 1,-1,0,0,1,-1,1,-1 };

int w,h;

void bfs(int x, int y, int cnt) {

queue<pair<int, int>> q;

q.push(make_pair(x, y));

check[x][y] = cnt;

while (!q.empty()) {

x = q.front().first;

y = q.front().second;

q.pop();

for (int i = 0; i < 8; i++) {

int nx = x + nextX[i];

int ny = y + nextY[i];

if (nx >= 0 && nx < h && ny >= 0 && ny < w) {

if (a[nx][ny] == 1 && check[nx][ny] == 0) {

check[nx][ny] = cnt;

q.push(make_pair(nx, ny));

}

}

}

}

}

int main(void) {

while (true) {

scanf("%d %d", &w, &h);

if (w == 0 && h == 0)

break;

for (int i = 0; i < h; i++) {

for (int j = 0; j < w; j++) {

scanf("%d", &a[i][j]);

check[i][j] = 0;

}

}

int cnt = 0;

for (int i = 0; i < h; i++) {

for (int j = 0; j < w; j++) {

if(a[i][j]==1 && check[i][j]==0)

bfs(i, j, ++cnt);

}

}

printf("%d\n", cnt);

}

return 0;

}

4. 미로 탐색 2178번

// 가중치가 1인 그래프의 시작점에서 각 정점까지의 최단 거리는 bfs로 풀 수 있다.

#include <iostream>

#include <queue>

using namespace std;

int a[101][101];

int dist[101][101];

bool check[101][101];

int n, m;

int nextX[4] = { 0,0,1,-1 };

int nextY[4] = { 1,-1,0,0 };

void bfs(int x, int y) {

queue<pair<int, int>> q;

q.push(make_pair(x, y));

check[x][y] = true;

while (!q.empty()) {

x = q.front().first;

y = q.front().second;

q.pop();

for (int i = 0; i < 4; i++) {

int nx = x + nextX[i];

int ny = y + nextY[i];

if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {

if (a[nx][ny] == 1 && check[nx][ny] == false) {

check[nx][ny] = true;

dist[nx][ny] = dist[x][y] + 1;

q.push(make_pair(nx, ny));

}

}

}

}

}

int main(void) {

cin >> n >> m;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {

scanf("%1d", &a[i][j]);

}

}

bfs(1, 1);

cout << dist[n][m]+1 << endl;

return 0;

}

5. 토마토 7576번

#include <iostream>

#include <queue>

using namespace std;

int a[1000][1000];

int dist[1000][1000];

int nextX[4] = { 0,0,1,-1 };

int nextY[4] = { 1,-1,0,0 };

int n, m;

int main(void) {

cin >> m >> n;

queue<pair<int, int>> q;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

scanf("%d", &a[i][j]);

dist[i][j] = -1;

if (a[i][j] == 1) {

dist[i][j] = 0;

q.push(make_pair(i, j));

}

}

}

while (!q.empty()) {

int x = q.front().first;

int y = q.front().second;

q.pop();

for (int i = 0; i < 4; i++) {

int nx = nextX[i] + x;

int ny = nextY[i] + y;

if (nx >= 0 && nx < n && ny >= 0 && ny < m) {

if (a[nx][ny] == 0 && dist[nx][ny] == -1) {

dist[nx][ny] = dist[x][y] + 1;

q.push(make_pair(nx, ny));

}

}

}

}

int ans = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (ans < dist[i][j]) {

ans = dist[i][j];

}

}

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (a[i][j] == 0 && dist[i][j] == -1)

ans = -1;

}

}

cout << ans << endl;

return 0;

}

6. 다리만들기 2146번 = 단지번호 붙이기 + 토마토

#include <iostream>

#include <queue>

using namespace std;

int a[100][100];

int dist[100][100];

int g[100][100];

int nextX[4] = { 0,0,1,-1 };

int nextY[4] = { 1,-1,0,0 };

int main(void) {

int n;

cin >> n;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

scanf("%d", &a[i][j]);

}

}

int cnt = 0;

// 그룹(섬 번호) 매기기(단지 번호붙이기 문제와 동일)

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (a[i][j] == 1 && g[i][j] == 0) {

cnt++;

queue <pair<int, int>> q;

q.push(make_pair(i, j));

g[i][j] = cnt;

while (!q.empty()) {

int x = q.front().first;

int y = q.front().second;

q.pop();

for (int k = 0; k < 4; k++) {

int nx = x + nextX[k];

int ny = y + nextY[k];

if (nx >= 0 && nx < n && ny >= 0 && ny < n) {

if (a[nx][ny]==1 && g[nx][ny] == 0) {

g[nx][ny] = cnt;

q.push(make_pair(nx, ny));

}

}

}

}

}

}

}

        // 각 섬 마다 다른 섬까지의 최단 거리 구하기(토마토 문제와 동일)

int ans = -1;

for (int l = 1; l <= cnt; l++) {

queue<pair<int, int>> q;

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++) {

dist[i][j] = -1;

if (g[i][j] == l) {

dist[i][j] = 0;

q.push(make_pair(i, j));

}

}

}

while (!q.empty()) {

int x = q.front().first;

int y = q.front().second;

q.pop();

for (int k = 0; k < 4; k++) {

int nx = x + nextX[k];

int ny = y + nextY[k];

if(nx>=0 && nx<n && ny>=0 && ny<n){

if (dist[nx][ny] == -1) {

dist[nx][ny] = dist[x][y] + 1;

q.push(make_pair(nx, ny));

}

}

}

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (a[i][j] == 1 && g[i][j] != l) {

if (ans==-1 || dist[i][j]-1 < ans) {

ans = dist[i][j] - 1;

}

}

}

}

}

cout << ans << endl;

return 0;

}