[백준 2468] 안전 영역

문제설명

https://www.acmicpc.net/problem/2468

알고리즘

1. 그래프 입력(최대높이 저장)

2. 높이별로 반복해서 dfs 연산

3. 최대 높이 출력

코드

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

int graph [101][101]={0,};
bool visited[101][101]={0,};
int dx[4] ={1,-1,0,0};
int dy[4] ={0,0,1,-1};
int N;

void dfs(int x, int y, int height){

    visited[x][y]= true;
    for (int i = 0; i < 4; i++)
    {
        if(dx[i]+x >= N || dx[i]+x < 0 || dy[i]+y>=N || dy[i]+y <0)
            continue;
        if(visited[dx[i]+x][dy[i]+y]== false && graph[dx[i]+x][dy[i]+y] > height)
            dfs(dx[i]+x , dy[i]+y, height);
    }   
}

int main(){
    int count =0, max=1;
    cin>>N;
    for (int i = 0; i < N ; i++)//높이 입력 
    {
        int a;
        for (int j = 0; j < N; j++)
        {           
            cin>>a;
            graph[i][j] = a;
            if(max<a)
                max = a;
        }             
    }
    int answer = 0;
    for (int k = 0; k < max; k++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if(visited[i][j]== false && graph[i][j] > k){//현재 높이보다 높은 곳 방문
                    dfs(i,j,k);
                    count++;
                }                 
            }       
        }
        if(count > answer)//최대 높이 저장
            answer=count;
        fill(&visited[0][0], &visited[100][101] ,false);//방문 정보 초기화
        count=0;
    }
 
    cout<<answer<<endl;
    
    return 0;
}

고찰

이번 문제는 dfs 로 쉽게 해결 할 수 있었다

그 중에서 헷갈렸던 문법은 배열 초기화하는 함수였는데 자꾸 까먹는다