[BOJ/백준][Gold4] 2234 : 성곽 (C++)

www.acmicpc.net/problem/2234

2234번: 성곽

 

 

[난이도] Gold4

[유형] DFS

 

[풀이]

1. DFS를 돌면서 각 방이 어떤 그룹에 속하는지 나누면서 각 그룹에 몇개의
   방이 있는지를 체크한다.
2. 모든 방을 순회하면서 동,서,남,북 방향을 체크해 다른 그룹이 있으면
   현재 방의 개수 + 현재 체크중인 인접한 방의 개수를 더해 답을
   갱신해준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,map[50][50],g,grp[2501],mxR,mxS;
int visit[50][50];
int dy[4] = {0,-1,0,1};
int dx[4] = {-1,0,1,0};
int dfs(int y,int x){
    visit[y][x] = g;
    int ret = 1;
    for(int i=0;i<4;i++){
        if((map[y][x] & (1<<i))==0){
            int ny = y+dy[i], nx = x+dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m || visit[ny][nx]) continue;
            ret+=dfs(ny,nx);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&map[i][j]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visit[i][j]){
                g++;
                grp[g] = dfs(i,j);
                mxR = max(mxR,grp[g]);
            }
        }
    }
    for(int y=0;y<n;y++){
        for(int x=0;x<m;x++){
            for(int i=0;i<4;i++){
                if((map[y][x] & (1<<i))>0){
                    int ny = y+dy[i], nx = x+dx[i];
                    if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                    if(visit[ny][nx] != visit[y][x]) mxS = max(mxS,grp[visit[ny][nx]]+grp[visit[y][x]]);
                }
            }
        }
    }
    printf("%d\n%d\n%d",g,mxR,mxS);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2234.cpp