BOJ
BOJ 1926 그림 - DFS
@떠니
2019. 4. 6. 00:22
https://www.acmicpc.net/problem/1926
- BFS DFS 모두 가능하지만 DFS를 이용하여 풀었다
- 그림의 갯수는 cnt를 이용하여 출력할 수 있지만 가장 큰 그림의 크기를 구하기 위해 ans[502*502]를 선언했다.
- 아직도 DFS가 헷갈려 ㅠㅠ
#include <iostream>
#include <cstdio>
using namespace std;
int board[502][502];
int visited[502][502];
int n, m; // 1st input
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int ans[502*502]={0};
void dfs(int x, int y, int cnt){
visited[x][y] = cnt; // 방문했다고 표시
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<n && nx>=0 && ny<m && ny>=0){
if(board[nx][ny]==1 && visited[nx][ny]==0){
dfs(nx, ny, cnt);
}
}
}
}
int main(){
//입력 처리
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++){
scanf("%d", &board[i][j]); //2nd input
visited[i][j]=0; // 방문 배열 초기화.
}
int cnt=0;
//DFS 처리
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(board[i][j]==1 && visited[i][j]==0) {
dfs(i, j, ++cnt);
}
}
}
printf("%d\n", cnt); //1st output
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
ans[visited[i][j]] += 1; //2nd output
}
}
int result = 0;
for(int i=1; i<502*502; i++){
result = max(result, ans[i]);
}
printf("%d", result);
}