글 읽기 - 단지 번호 붙이기 BFS 문제

adngjun 5년 전 1

단지 번호 붙이기를 DFS 로풀고 BFS 로 한번 해결해보려고 하는데..답이 안나오네요.

혹시 해결가능하신 고수님들 답변좀 부탁드립니다.

미리 감사합니다

#include <stdio.h>
#include <iostream> 
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

int V, E, N;

int board[101][101];
int visit[101][101];
int result[101];

queue <int > q;
int answer;

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1};



bool chk(int x, int y){

	if (x < 0 || x >= N || y < 0 || y >= N)
		return false;
	else
		return true;

}
// 1번 노드와 관련 있는 친구들을 센다. bfs로 구현한다. 
void  bfs(int x, int y , int n ) {

	int temp;

	queue <pair<int, int >> q;
	q.push(make_pair(x, y));

	while (!q.empty()){

		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		board[y][x] = 0;

	//	if (visit[y][x] != 0) continue;

		visit[y][x] = n;
		result[n]++;

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

			int nx = dx[i] + x;
			int ny = dy[i] + y;


			if (chk(nx, ny) && board[ny][nx] == 1){
				board[ny][nx] = 0;
				q.push(make_pair(nx, ny));
				
			}
			
		}

	}
}

void dbg_print(){

	for (int i = 0; i < V; i++){
		for (int j = 0; j < V; j++){
			cout << visit[i][j] << " ";
		}
		cout << endl;
	}
}

int main() {

	freopen("input2.txt", "r", stdin); setbuf(stdout, NULL);
	cin >> N;

	memset(visit, 0, sizeof(visit));
	memset(result, 0, sizeof(result));

	for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
		scanf("%1d", &board[i][j]);
	
	int nn = 1;
	answer = 0;

	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			if (board[i][j] == 1){

				//board[i][j] = 0;
				bfs(j, i, nn);

				answer++;
				nn++;

			}
		}	
	}

	sort(result, result + answer +1);
	cout << answer << endl;
	//dbg_print();

	for (int i = 1; i <= answer; i++)
		cout << result[i]<< endl;	


	return 0;
}

djm03178 5년 전 1

https://www.acmicpc.net/board/...

adngjun 5년 전 0

넵 감사합니다..찾았네요..

도움 감사요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

단지 번호 붙이기 BFS 문제

adngjun 5년 전 1

djm03178 5년 전 1

adngjun 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말