Java 알고리즘 격자판 봉우리 개수

오늘은 배열을 이용하여 격자판의 봉우리 개수를 구하는 문제를 풀어보려고 합니다😀

 

Array 봉우리

 

개요

문제 내용

문제 예시

 

이번 문제는 이중 배열을 이용하는 방법과 각 격자에서 상하좌우를 확인하는 방법 총 2가지가 핵심이 될 것 같네요😊

 

Setting📙

public class Peak {
    public static void main(String[] args) {
        Peak T = new Peak();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][n];
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(T.solution(n, arr));
    }
}

입력으로는 첫 번째로 가로,세로 사이즈가 주어지고, 그다음으로 격자판이 주어집니다.

 

가로, 세로 길이는 n이라는 변수에 담고 이중 배열 arr을 int [n][n]으로 선언하였습니다. 이후에 이중 반복문을 이용하여 arr 배열에 값들을 넣어줍니다. 이후에 solution 함수에 사이즈와 격자판을 넘겨줍니다😄

 

Solution📘

public int solution(int n, int[][] arr){
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    int result = 0;

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            boolean flag = true;
            for(int k = 0; k < 4; ++k){
                int nx = i +dx[k];
                int ny = j +dy[k];
                if(nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] >= arr[i][j]) {
                    flag = false;
                    break;
                }
            }
            if(flag) result++;
        }
    }
    return result;
}

int dx와 int dy는 상하좌우를 확인할 때 사용합니다. result 변수는 봉우리의 갯수를 담기 위해 선언하였습니다.

 

이제 격자판을 이중 반복문을 통해 하나하나 탐색합니다. boolean 타입의 flag 변수는 해당 격자가 봉우리가 아닐 경우 false로 바꾸고 반복문을 종료시키는 역할을 합니다.

 

이중 반복문으로 격자를 찾고, 해당 격자 안에서 다시 한번 반복문을 4번 돌면서 상하좌우를 탐색합니다. nx는 next x로 다음 x좌표를 의미하고, ny는 next y로 다음 y좌표를 의미합니다.

 

위에서 선언한 dx와 dy를 반복문을 통해 더해보시면 12시 방향부터 시계방향으로 탐색하는 것을 알 수 있습니다. if 조건문은 상하좌우 4개의 격자가 현재 격자보다 높으면 봉우리가 될 수 없기 때문에 arr [nx][ny] >= arr [i][j] 코드가 들어가 있습니다.

 

또한, 격자판을 넘어가는 테두리 부분들을 제거하기 위해서 nx < n, ny < n 조건과 0 이상이어야 하는 조건이 들어가 있습니다. 봉우리의 모든 조건을 충족한 격자는 flag가 true로 남아있게 됩니다.

 

마지막으로 flag가 true인 격자를 만나면 result 값을 증가시킵니다.

 

Result📗

테스트 결과

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

 

마치며

배열을 통해 간단하게 봉우리 문제를 풀어보았습니다. 이 봉우리 문제는 DFS, BFS 탐색 알고리즘에도 응용되어 문제가 자주 나오기 때문에 풀이법을 잘 알아두시면 좋을 것 같아요😊