백준 2468번 - 안전영역

문제 개요

 

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

2468번: 안전 영역

모든 문제가 다 그런건 아니지만 영역이 분할되어 해당 영역의 개수를 구하는 문제는

 

일반적으로 DFS(Depth-First Search)

 

또는 BFS(Breadth-First Search)알고리즘을 사용한다.

 

위와 같은 matrix 가 존재할 때,

 

높이들 중에 가장 작은 숫자는 2이고 가장 큰 숫자는 9이다.

숫자가 1~9 일때 물에 잠기는 지점들을

 

각각 카운트 해서 가장 최대값을 구하는 것이다.

 

이유는 문제의 노트의 써져있는대로 아무지역도 물에 잠기지 않을 수 있기 때문이다.

 

만약 높이가 3일때 잠겨지는 영역을 제외한 영역들이

 

최대값이 된다면 해당 최대값이 답이 되는 논리이다.

 

예를들어, 위의 배열을 가지고 높이가 4정도의 비가 내렸을때 어떤 지역이 침수되는지 알아보자.

4 이하의 영역은 모두 침수되어야 하므로 침수되지 않는 구역은

 

위와 같고 구역의 개수는총 다섯개가 나오고 있다.

 

 

로직이 어떤식으로 작동하는지 아래의 그림을 보고 이해해보자.

 

1) 첫번째로 행렬의 1행1열로 가줘서 숫자를 비교해준다 6은 4보다 큰 수이므로 영역을 생성하는 동시에 포함시킨다.

2) 6을 기점으로 왼쪽과 윗쪽은 행열의 범위를 벗어나는 곳이므로 무시해준다.

3) 6을 기점으로 오른쪽의 숫자가 8이므로 범위에 포함시켜준다.

4) 6을 기점으로 아래쪽에는 3이 있다. 3은 4보다 작은 수이므로 영역에 포함시키지 않는다.

5 ) 방문한 영역은 별도의 매트릭스에서 관리해준다.(빨간색이 방문한 영역)

 

 

 

1) 2는 4보다 작은 수이므로 건너 뛴다.

2) 6은 4보다 큰 수이므로 영역을 생성하는 동시에 포함시켜준다.

3) 6을 기점으로 위쪽은 영역밖이므로 무시해준다.

4) 왼쪽과 오른쪽 아래쪽은 모두 4 이하이므로 영역에 포함시키지 않는다.

5) 방문배열에 표시해준다.

 

위와 같은 형식으로 모든 배열을 탐색하면서 영역을 찾아주면 된다.

 

그리고 주의해야할 경우는 아래와 같다.

 

 

특정 높이일때 잠기지 않는 최대의 영역을 구해야 하기 때문에

물이 최소 몇부터 몇까지 잠기는지 생각해야한다. 

 

위의 논리대로 코드를 쳐보면 아래와 같다.

 

코드 구현

DFS 알고리즘 적용

 

1. JAVA - 재귀함수 적용

import java.io.*;
import java.util.*;

public class Main {
    
    static int N;
    static int[][] map;
    static int[][] visited;
    static int maxCnt = 0;
    static int maxHeight;
    static int[] dr = {1,0,-1,0};
    static int[] dc = {0,1,0,-1};
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        N = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        visited = new int[N][N];
        
        for (int i = 0; i < N; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
            int rowIndex = 0;
            
            while(stk.hasMoreTokens()){
                int height = Integer.parseInt(stk.nextToken());
                map[i][rowIndex++] = height;
                maxHeight = Math.max(height, maxHeight);
            }
        }
        
        for (int i = 0; i <= maxHeight; i++) {
            
            int cnt = 0;
            
            for (int j = 0; j < N*N; j++) {
                int row = j / N;
                int col = j % N;
 
                if (map[row][col] > i && visited[row][col] == 0) { 
                    dfs(row, col, i);
                    cnt++;                                  
                }
            }

            maxCnt = Math.max(maxCnt, cnt);
            visited = new int[N][N];
        }

        bw.write(maxCnt + "");
        bw.close();
        br.close();
    }
    
    static void dfs(int row, int col, int height) {
        
        visited[row][col] = 1;
        
        for (int i = 0; i < 4; i++) {
            int newRow = row + dr[i];
            int newCol = col + dc[i];
            
            if (newRow >= 0 && newCol >= 0 && newRow < N && newCol < N && map[newRow][newCol] > height && visited[newRow][newCol] == 0) {
                dfs(newRow, newCol, height);
            }
        }
    }
}

 

 

2. JAVA - Stack 자료구조 적용

import java.io.*;
import java.util.*;

public class Main {
    
    static int N, minH, maxH, maxCnt;
    static int[][] map;
    static boolean[][] visited;
    static int dr[] = {0,1,0,-1};
    static int dc[] = {1,0,-1,0};
    
    static class Pair {
        int row,col;

        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
            int index = 0;

            while(stk.hasMoreTokens()) {
                int curH = Integer.parseInt(stk.nextToken());
                minH = Math.min(minH, curH);
                maxH = Math.max(maxH, curH);

                map[i][index++] = curH;
            }
        }
        
        for (int h = minH-1; h < maxH; h++) {
            
            int cnt = 0;
            
            for (int i = 0; i < N*N; i++) {
                int curR = i / N;
                int curC = i % N;

                if (map[curR][curC] > h && !visited[curR][curC]) {
                    dfs(curR, curC, h);
                    cnt++;
                }
            }

            maxCnt = Math.max(maxCnt, cnt);
            visited = new boolean[N][N];
        }
        
        bw.write(maxCnt + "");
        bw.close();
        br.close();
    }

    static void dfs(int row, int col, int height) {
        
        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(row, col));
        visited[row][col] = true;

        while(!stack.isEmpty()) {
            int curR = stack.peek().row;
            int curC = stack.peek().col;
            stack.pop();

            for (int i = 0; i < 4; i++) {
                int newR = curR + dr[i];
                int newC = curC + dc[i];

                if (newR >= 0 && newC >= 0 && newR < N && newC < N && !visited[newR][newC] && map[newR][newC] > height) {
                    stack.push(new Pair(newR, newC));
                    visited[newR][newC] = true;
                }
            }
        }
    }
}

 

 

3. C++ - 재귀함수 적용

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int N;
int map[100][100];
bool visited[100][100];
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};
int max_cnt;
int min_cnt;
int max_h;

void dfs(int r, int c, int h)
{   
    visited[r][c] = true;

    for (int i = 0; i < 4; i++)
    {
        int new_r = r + dr[i];
        int new_c = c + dc[i];

        if (new_r >= 0 && new_c >= 0 && new_r < N && new_c < N && map[new_r][new_c] > h && !visited[new_r][new_c])
        {
            dfs(new_r, new_c, h);
        }
    }
}

int main()
{
    cin >> N;
    
    for (int i = 0; i < N*N; i++)
    {
        int input_h; cin >> input_h;

        max_h = max(max_h, input_h);
        min_cnt = min(min_cnt, input_h);
        map[i/N][i%N] = input_h;
    }
    

    for (int i = min_cnt-1; i < max_h; i++)
    {
        int cnt = 0;

        for (int j = 0; j < N*N; j++)
        {
            int r = j/N;
            int c = j%N;

            if (map[r][c] > i && !visited[r][c])
            {
                dfs(r,c,i);
                cnt++;    
            }
        }

        max_cnt = max(cnt, max_cnt);
        memset(visited, false, sizeof(visited));
    }

    cout << max_cnt << endl;
    
    return 0;
}

 

4. C++ - Stack 자료구조 적용

#include <iostream>
#include <algorithm>
#include <utility>
#include <stack>
#include <cstring>

using namespace std;

int N;
int map[100][100];
bool visited[100][100];
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};
int max_cnt;
int min_h;
int max_h;

void dfs(int r, int c, int h)
{
    stack<pair<int,int>> stack;
    stack.push(make_pair(r,c));
    visited[r][c] = true;
    
    while(!stack.empty())
    {
        auto [cur_r, cur_c] = stack.top();
        stack.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int new_r = cur_r + dr[i];
            int new_c = cur_c + dc[i];

            if (new_r >= 0 && new_c >= 0 && new_r < N && new_c < N && map[new_r][new_c] > h && !visited[new_r][new_c])
            {
                stack.push(make_pair(new_r, new_c));
                visited[new_r][new_c] = true;
            }
        }
    }
}

int main()
{
    cin >> N;

    for (int i = 0; i < N*N; i++)
    {
        int h; cin >> h;
        max_h = max(h,max_h);
        min_h = min(h,min_h);

        map[i/N][i%N] = h;
    }

    for (int h = min_h-1; h < max_h; h++)
    {
        int cnt = 0;

        for (int i = 0; i < N*N; i++)
        {
            int cur_r = i / N;
            int cur_c = i % N;

            if (map[cur_r][cur_c] > h && !visited[cur_r][cur_c])
            {
                dfs(cur_r, cur_c, h);
                cnt++;
            }    
        }
        
        max_cnt = max(cnt, max_cnt);
        memset(visited, false, sizeof(visited));
    }
    
    cout << max_cnt << endl;

    return 0;
}

 

5. Python - 재귀함수 적용

import sys

# 재귀 호출 깊이 제한 설정
sys.setrecursionlimit(100000) 

input = sys.stdin.readline

dr = [0,1,0,-1]
dc = [1,0,-1,0]

N = int(input())

max_cnt = 0
min_h = 0
max_h = 0
visited = [[0] * N for _ in range(N)]
safety_map = []


def dfs(row,col,h):
    visited[row][col] = 1
    
    for i in range(4):
        new_r = row + dr[i]
        new_c = col + dc[i]

        if (new_r >= 0 and new_c >= 0 and new_r < N and new_c < N and visited[new_r][new_c] == 0 and safety_map[new_r][new_c] > h):
            dfs(new_r, new_c, h)
    

for i in range(N):
    numbers = list(map(int, input().split()))
    
    for j in range(len(numbers)):
        min_h = min(numbers[j], min_h)
        max_h = max(numbers[j], max_h)
    
    safety_map.append(numbers)



for h in range(min_h-1, max_h):
    
    cur_cnt = 0

    for i in range(N*N):
        row = i // N
        col = i % N

        if (safety_map[row][col] > h and visited[row][col] == 0):
            dfs(row,col,h)
            cur_cnt += 1

    visited = [[0] * N for _ in range(N)]
    max_cnt = max(max_cnt, cur_cnt)

print(max_cnt)

 

 

6. Python - Stack 자료구조 적용

import sys
input = sys.stdin.readline

dr = [0,1,0,-1]
dc = [1,0,-1,0]

N = int(input())

max_cnt = 0
min_h = 0
max_h = 0
visited = [[0] * N for _ in range(N)]
safety_map = []


def dfs(row, col, h):
    stack = [(row,col)]
    visited[row][col] = 1
    
    while stack:

        row,col = stack.pop()

        for i in range(0,4):
            new_r = row + dr[i]
            new_c = col + dc[i]

            if (new_r >= 0 and new_c >= 0 and new_r < N and new_c < N and visited[new_r][new_c] == 0 and safety_map[new_r][new_c] > h):
                stack.append((new_r,new_c))
                visited[new_r][new_c] = 1    

for i in range(N):
    numbers = list(map(int, input().split()))
    
    for j in range(len(numbers)):
        min_h = min(numbers[j], min_h)
        max_h = max(numbers[j], max_h)
    
    safety_map.append(numbers)


for h in range(min_h-1, max_h):
    
    cur_cnt = 0

    for i in range(N*N):
        row = i // N
        col = i % N

        if (safety_map[row][col] > h and visited[row][col] == 0):
            dfs(row,col,h)
            cur_cnt += 1

    visited = [[0] * N for _ in range(N)]
    max_cnt = max(max_cnt, cur_cnt)

print(max_cnt)

 

 

BFS 알고리즘 적용

 

1. JAVA

import java.io.*;
import java.util.*;

public class Main {

    static int N, maxCnt, minH, maxH;
    static int[][] map;
    static boolean[][] visited;
    static int dr[] = {0,1,0,-1};
    static int dc[] = {1,0,-1,0};

    static class Pair {
        public int row, col;

        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
            int index = 0;

            while(stk.hasMoreTokens()) {
                int height = Integer.parseInt(stk.nextToken());
                maxH = Math.max(height, maxH);
                minH = Math.min(height, minH);

                map[i][index++] = height;
            }
        }
        
        for (int h = minH-1; h < maxH; h++) {
            
            int cnt = 0;
            
            for (int i = 0; i < N*N; i++) {
                int row = i / N;
                int col = i % N;

                if (map[row][col] > h && !visited[row][col]) {
                    bfs(row, col, h);
                    cnt++;
                }
            }
            
            maxCnt = Math.max(maxCnt, cnt);
            visited = new boolean[N][N];
        }


        bw.write(maxCnt + "");
        bw.close();
        br.close(); 
    }

    static void bfs(int row, int col, int height) {
        visited[row][col] = true;
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(row, col));

        while(!queue.isEmpty()) {

            int curR = queue.peek().row;
            int curC = queue.peek().col;
            queue.poll();

            for (int i = 0; i < 4; i++) {
                int newR = curR + dr[i];
                int newC = curC + dc[i];
                
                if (newR >= 0 && newC >= 0 && newR < N && newC < N && !visited[newR][newC] && map[newR][newC] > height) {
                    queue.add(new Pair(newR, newC));
                    visited[newR][newC] = true;
                }
            }
        }
    }
}

 

 

 

2. C++

 

#include <iostream>
#include <cstring>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

int N;
int map[100][100];
bool visited[100][100];
int max_cnt = 1;
int max_n;
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void bfs(int r, int c, int h)
{
    queue<pair<int, int>> map_q;
    map_q.push(make_pair(r,c));
    visited[r][c] = true;
    
    while (!map_q.empty())
    {
        auto [cur_r, cur_c] = map_q.front();
        map_q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int new_r = cur_r + dr[i];
            int new_c = cur_c + dc[i];

            if (new_r >= 0 && new_c >= 0 && new_r < N && new_c < N && map[new_r][new_c] > h && !visited[new_r][new_c])
            {
                map_q.push(make_pair(new_r, new_c));
                visited[new_r][new_c] = true;
            }
        }
    }
}


int main()
{
    cin >> N;

    for (int i = 0; i < N*N; i++)
    {
        int input_n; cin >> input_n;
        max_n = max(input_n, max_n);
        map[i/N][i%N] = input_n;
    }
    
    for (int i = 1; i <= max_n; i++)
    {
        int cnt = 0;

        for (int j = 0; j < N*N; j++)
        {
            int cur_r = j/N;
            int cur_c = j%N;

            if (map[cur_r][cur_c] > i && !visited[cur_r][cur_c])
            {
                bfs(cur_r, cur_c, i);
                cnt++;
            }    
        }

        max_cnt = max(cnt, max_cnt);
        memset(visited, false, sizeof(visited));
    }
    
    cout << max_cnt << endl;

    return 0;
}

 

 

3. Python

import sys
from queue import Queue

input = sys.stdin.readline

dr = [0,1,0,-1]
dc = [1,0,-1,0]

N = int(input())

max_cnt = 0
min_h = 0
max_h = 0
visited = [[0] * N for _ in range(N)]
safety_map = []


def bfs(row, col, h):
    
    visited[row][col] = 1
    queue = Queue()
    queue.put((row, col))

    while not queue.empty():

        cur_row, cur_col = queue.get()
        
        for i in range(0,4):
            new_r = cur_row + dr[i]
            new_c = cur_col + dc[i]

            if (new_r >= 0 and new_c >= 0 and new_r < N and new_c < N and visited[new_r][new_c] == 0 and safety_map[new_r][new_c] > h):
                queue.put((new_r,new_c))
                visited[new_r][new_c] = 1    


for i in range(N):
    numbers = list(map(int, input().split()))
    
    for j in range(len(numbers)):
        min_h = min(numbers[j], min_h)
        max_h = max(numbers[j], max_h)
    
    safety_map.append(numbers)


for h in range(min_h-1, max_h):
    
    cur_cnt = 0

    for i in range(N*N):
        row = i // N
        col = i % N
        
        if (safety_map[row][col] > h and visited[row][col] == 0):
            bfs(row,col,h)
            cur_cnt += 1

    visited = [[0] * N for _ in range(N)]
    max_cnt = max(max_cnt, cur_cnt)

print(max_cnt)