글 읽기 - 이 문제를 DFS나 BFS 방식으로 어떻게 접근하나요?

zaq7351 4년 전 0

맞았습니다가 뜨긴 떴는데.. 제가 구현했던 DFS나 BFS는 리스트 배열 방식으로 구현해본적밖에 없어서 잘 모르겠습니다...

이 문제를 DFS나 BFS방식으로 접근하려면 어떻게 해야하나요..?

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct Building{
	int building;
	bool visit;
};

Building building[25][25];
int N;

int cnt;
int arr_cnt[313];
char input[26];

void f(int row,int col, int _cnt) {
	if (row<0 || row>=N || col<0 || col>=N || building[row][col].building == 0 || building[row][col].visit == true)
		return;
	arr_cnt[_cnt - 1]++;
	building[row][col].visit = true;
	f(row - 1, col, _cnt);
	f(row, col - 1, _cnt);
	f(row, col + 1, _cnt);
	f(row + 1, col, _cnt);
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", input);
		for (int j = 0; j < N; j++) {
			building[i][j].building = input[j] - '0';
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (building[i][j].building == 1 && building[i][j].visit == false) {
				cnt++;
				f(i, j, cnt);
			}
		}
	}
	printf("%d\n", cnt);

	sort(arr_cnt, arr_cnt + cnt);
	for (int i = 0; i < cnt; i++) {
		printf("%d\n", arr_cnt[i]);
	}
}

djm03178 4년 전 0

지금 하신 게 완전한 DFS 입니다.

zaq7351 4년 전 0

아항 감사합니다..

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

문제

문제

출처

ICPC

이 문제를 DFS나 BFS 방식으로 어떻게 접근하나요?

zaq7351 4년 전 0

djm03178 4년 전 0

zaq7351 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말