백준 2468번 JAVA 정리

2468번: 안전 영역

문제를 이해하는데 꽤나 걸렸다. kt에이블 인적성 검사할 때도 그렇고 주말에 2개의 코테를 보고 나니 독해력이 정말 부족하구나 라는 점을 느껴서 책을 간간히 읽어야겠다는 생각이 들었다

1	2	2
3	3	2
1	1	3

배열의 원소는 어떤 지역의 높이 정보를 나타낸다.

문제에서 알고 싶은 것은 비가 올 경우 안전한 영역은 몇 개인지 알고 싶은 것이다.

 

비가 1만큼 오면 높이가 1인 지점이 물에 잠기고 2만큼 오면 높이가 1,2인 지점이 잠긴다고 가정한다.

비가 0만큼 올경우 안전 구역은 모든 지역이 안전하므로 안전한 영역의 개수는 1이다.

 

비가 1만큼 올경우 1인 지점이 물에 잠기게 된다. 그러면 높이가 2 이상인 지점만 남게 되는데 이때 역시 안전한 영역의 개수는 1개이다.

X	2	2
3	3	2
X	X	3

안전한 영역의 개수를 파악하는 것은 바둑의 집?을 셀 때와 비슷하다고 생각하면 이해하기가 편하다.

상하좌우에 안전한 영역이 인접해 있다면 그 모든 것을 한 개로 묶어서 하나로 세면된다. 안전한 영역이 대각선에 있다면 같이 묶어서 셈을 하지 않는다.

 

비가 2만큼 올경우 2인 지점이 물에 잠기게 된다. 이러면 역시 높이가 2 이하인 지점은 모두 물에 잠기게 되고 높이가 3 이상인 지점만 안전하게 된다. 이때 안전한 영역의 개수는 2개가 된다.

X	X	X
3(1)	3(1)	X
X	X	3(2)

3 옆에 소괄호로 안전한 영역의 묶음을 표현해 줬다.

 

이렇게 0부터 최대 높이값까지 탐색을 하면서 어떤 높이의 비가 왔을 때 안전한 영역이 가장 많은지 즉 BFS함수가 어떤 비의 높이 값에서

가장 많이 호출되는지 파악하면 된다.

 

풀이

for(int i =0;i<=max;++i)
{
    int safeArea = 0;
    visited = new boolean[n][n];
    for(int t = 0;t<n;++t)
    {
        for(int x = 0;x<n;++x)
        {
            if(map[t][x]>i&&visited[t][x]==false)
            {
                visited[t][x] = true;
                bfs(i,t,x);
                ++safeArea;
            }
        }
    }
    answer = Math.max(safeArea,answer);
}

0~배열의 원소 최댓값까지 탐색을 시작한다. 현재 코드에서 i는 비가 오는 높이라고 생각하면 된다.

map의 특정 원소가 i보다 크다면 물에 잠기지 않는 높이 이기 때문에 안전한 영역이 된다. 그리고 아직 탐색하지 않은 원소라면 bfs함수를 호출해 준다. 이때 비가 오는 높이 인 i, x좌표, y좌표를 변수로 넘겨준다.

 

bfs함수가 호출되었다는 것은 해당 원소와 인접한 모든 안전한 높이를 탐색했다는 의미가 되기 때문에 안전한 영역을 파악하고 있는

safeArea 변수의 값을 증가시켜준다.

마지막으로 최댓값을 구해야 하기 때문에 Math.max함수로 값을 비교해 answer에 담아준다.

 

public static void bfs(int waterAmount,int x,int y)
{
Queue<Node>queue = new LinkedList<>();
queue.offer(new Node(x,y));

while(!queue.isEmpty())
{
    Node node = queue.poll();
    for(int i =0;i<4;++i)
    {
        int tempX = node.x + xMove[i];
        int tempY = node.y + yMove[i];

        if(tempX<0||tempY<0||tempX>=n||tempY>=n)
        {
            continue;
        } else if (visited[tempX][tempY] || map[tempX][tempY]<=waterAmount) {
            continue;
        }else{
            queue.offer(new Node(tempX,tempY));
            visited[tempX][tempY] = true;
        }
    }
}
}

bfs함수는 특별한 부분이 없다. 살짝 다른 점이라면 map [tempX][tempY] <=waterAmount 조건을 줘서 인접한 값이 비의 양보다 작거나 같지 않은지 (작거나 같다면 안전하지 않은 영역이라는 것을 의미한다) 파악하는 로직 정도만 추가되었다.

 

import java.util.*;

public class Main{
    static int[][] map;
    static boolean[][] visited;
    static int max;
    static int[] xMove = {1,-1,0,0};
    static int[] yMove = {0,0,1,-1};
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new int[n][n];
//        visited = new boolean[n][n];
        int answer = 0;

        for(int i  =0;i<n;++i)
            for(int t =0;t<n;++t)
            {
                int x = sc.nextInt();
                map[i][t] = x;
                max = Math.max(max,x);
            }
        for(int i =0;i<=max;++i)
        {
            int safeArea = 0;
            visited = new boolean[n][n];
            for(int t = 0;t<n;++t)
            {
                for(int x = 0;x<n;++x)
                {
                    if(map[t][x]>i&&visited[t][x]==false)
                    {
                        visited[t][x] = true;
                        bfs(i,t,x);
                        ++safeArea;
                    }
                }
            }
            answer = Math.max(safeArea,answer);
        }
        System.out.println(answer);
    }

    public static void bfs(int waterAmount,int x,int y)
        {
        Queue<Node>queue = new LinkedList<>();
        queue.offer(new Node(x,y));
        
        while(!queue.isEmpty())
        {
            Node node = queue.poll();
            for(int i =0;i<4;++i)
            {
                int tempX = node.x + xMove[i];
                int tempY = node.y + yMove[i];
                
                if(tempX<0||tempY<0||tempX>=n||tempY>=n)
                {
                    continue;
                } else if (visited[tempX][tempY] || map[tempX][tempY]<=waterAmount) {
                    continue;
                }else{
                    queue.offer(new Node(tempX,tempY));
                    visited[tempX][tempY] = true;
                }
            }
        }
    }

}


class Node
{
    int x;
    int y;
    public Node(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}

---

어제는 토스 코테를 오늘은 kt에이블스쿨 코테를 보았다.

토스 코테는 쉽다고 사람들이 하였는데 아직 공부가 많이 부족해서 그런지 1,2 문제 밖에 풀지 못하였고 서술형은 그냥 말도 안 되게 어려웠다. Map이라던가 Hash 자료구조를 이용해 푸는 문제가 많이 나왔고 문자열을 다루는 문제가 많아서 어려웠다. 그래도 저번과는 다르게 손이라도 댈 수가 있어서 조금은 늘었구나 싶었지만 조오금 많이 아쉬웠다!

 

kt에이블스쿨 코테는 토스보다는 쉬웠지만 역시 문자열을 다루는 문제가 많아서 많이 어려웠다. 그리고 프로그래머스에서 하다 보니

백준과는 다르게 주어지는 변수의 형태가 달라서 주어지는 입력값을 다루는 게 조금 어려웠다. 백준에서 코테틀을 조금 잡고

프로그래머스로 넘어가야 하나 생각이 든다.