[BOJ알고리즘, C++]#2468_안전 영역, 그래프 탐색, DFS, BFS, 미로 탐색

2024. 2. 21. 21:31· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 2. 전형적인 미로 찾기 + 조건 추가 문제
  4. #3. 코드

 

#1. 문제

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

 


 

#2. 풀이

 

1. 그래프 탐색

 

[자료구조]#6_그래프

#0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와

webddevys.tistory.com

 

그래프의 모든 정점을 탐색하는 방법은 두 가지입니다. 먼저, DFS(깊이 우선 탐색)은 출발 정점으로부터 더 이상 확장할 수 없는 단말 노드까지 먼저 탐색하는 방법입니다. DFS는 일반적으로 재귀 호출 혹은 스택을 활용하여 구현합니다. 다음으로, BFS(너비 우선 탐색)은 현재 정점과 인접한 정점들을 우선 탐색하는 방법입니다. BFS는 일반적으로 큐를 활용하여 구현합니다.

 

2. 전형적인 미로 찾기 + 조건 추가 문제

 

  1. BFS를 수행하는 그래프 탐색을 구현합니다.
  2. 이때, 기준 높이를 인자로 추가적으로 전달하여, 해당 기준 높이 보다 높이 값이 높은 영역들을 카운트해 줍니다.

 


 

#3. 코드

 

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

typedef pair<int, int> p;

int N, res;
vector<vector<int>> heights;
vector<vector<bool>> visited;

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

void bfs(p start, int h)
{
    queue<p> q;

    visited[start.first][start.second] = true;
    q.push(start);

    while (!q.empty())
    {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (ny < 0 || ny >= N || nx < 0 || nx >= N || visited[ny][nx] || heights[ny][nx] <= h)
                continue;

            q.push({ny, nx});
            visited[ny][nx] = true;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    heights.resize(N, vector<int>(N));

    int maxHeight = -1;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> heights[i][j];
            maxHeight = max(maxHeight, heights[i][j]);
        }
    }

    for (int h = 0; h <= maxHeight; ++h)
    {
        visited.clear();
        visited.resize(N, vector<bool>(N, false));
        int cnt = 0;
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                if (!visited[i][j] && heights[i][j] > h)
                {
                    bfs({i, j}, h);
                    cnt++;
                }
            }
        }
        res = max(res, cnt);
    }

    cout << res;

    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#1697_숨바꼭질, 그래프 탐색, BFS  (0) 2024.02.21
[BOJ알고리즘, C++]#11724_연결 요소의 개수, 그래프, DFS, 깊이 우선 탐색  (1) 2024.02.21
[BOJ알고리즘, C++]#2178_미로 탐색, 그래프, BFS, DFS  (0) 2024.02.21
[BOJ알고리즘, C++]#14567_선수 과목(Prerequisite), 위상 정렬, 비순환 유향 그래프, DAG  (0) 2024.02.21
[BOJ알고리즘, C++]#2056_작업, 위상 정렬, 비순환 유향 그래프, DAG  (1) 2024.02.20
  1. #1. 문제
  2. #2. 풀이
  3. 2. 전형적인 미로 찾기 + 조건 추가 문제
  4. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#1697_숨바꼭질, 그래프 탐색, BFS
  • [BOJ알고리즘, C++]#11724_연결 요소의 개수, 그래프, DFS, 깊이 우선 탐색
  • [BOJ알고리즘, C++]#2178_미로 탐색, 그래프, BFS, DFS
  • [BOJ알고리즘, C++]#14567_선수 과목(Prerequisite), 위상 정렬, 비순환 유향 그래프, DAG
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • stl
  • dfs
  • 개발
  • 그래프
  • Unreal Blueprint
  • C++
  • 디자인 패턴
  • unreal
  • 정렬
  • 기술 질문
  • 최단 경로
  • 트리
  • BOJ
  • programmers
  • 우선순위 큐
  • set
  • BFS
  • Effective C++
  • 알고리즘
  • DP

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#2468_안전 영역, 그래프 탐색, DFS, BFS, 미로 탐색
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.