[Ch.02 - Array] 10. 봉우리

10. 봉우리

 

설명

지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다.

각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요.

격자의 가장자리는 0으로 초기화 되었다고 가정한다.

만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.

입력

첫 줄에 자연수 N이 주어진다.(2<=N<=50)

두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.

출력

봉우리의 개수를 출력하세요.

예시 입력 1 

5
5 3 7 2 3
3 7 1 6 1
7 2 5 3 4
4 3 6 4 1
8 7 3 5 2

예시 출력 1

10

---

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int[][] arr =new int[n+2][n+2];
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        arr[i][j]=in.nextInt();
      }
    }
    System.out.println(solution(n, arr));
  }
  static int solution(int n, int[][]arr){
    int answer=0;
    int[][] dis = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    for(int i=1; i<=n;i++){
      e: for(int j=1;j<=n;j++){
        for(int k=0;k<4;k++){
          if(arr[i][j]<=arr[i+dis[k][0]][j+dis[k][1]])
            continue e;
        }
        answer++;
      }
    }
    return answer;
  }
}

 

import java.util.Scanner;
  
public class Main {
  public int solution(int[][] arr,int n){
    int answer=0;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        if(arr[i][j]>arr[i+1][j]&&arr[i][j]>arr[i][j+1]&&arr[i][j]>arr[i-1][j]&&arr[i][j]>arr[i][j-1])
          answer++;
      }
    }
   return answer;
  }
  public static void main(String[] args){
    Main T = new Main();
    Scanner kb=new Scanner(System.in);
    int n = kb.nextInt();
    int[][] arr = new int[n+2][n+2];
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        arr[i][j]=kb.nextInt();
      }
    }
    System.out.println(T.solution(arr,n));
  }
}

 

import java.util.*;
  
public class Main {
  public int solution(int[][] arr,int n){
    int answer=0;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        if(arr[i][j]<=arr[i+1][j])
          continue;
        if(arr[i][j]<=arr[i][j+1])
          continue;
        if(arr[i][j]<=arr[i-1][j])
          continue;
        if(arr[i][j]<=arr[i][j-1])
          continue;
        
          answer++;
      }
    }
    return answer;
  }
  public static void main(String[] args){
    Main T = new Main();
    Scanner kb=new Scanner(System.in);
    int n = kb.nextInt();
    int[][] arr = new int[n+2][n+2];
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        arr[i][j]=kb.nextInt();
      }
    }
    System.out.println(T.solution(arr,n));
  }
}

 

+) list와 Math.max이용

import java.util.*;
  
public class Main {
  public int solution(int n,int[][] arr){
    int answer=0;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        ArrayList<Integer> list = new ArrayList<>();
        list.add(arr[i-1][j]);
        list.add(arr[i][j-1]);
        list.add(arr[i][j+1]);
        list.add(arr[i+1][j]);
        int max=Integer.MIN_VALUE;
        for(int x:list) 
        	max=Math.max(x,max);
        
        if(arr[i][j]>max) answer++;
      }
    }
    return answer;
  }
  public static void main(String[] args){
    Main T = new Main();
    Scanner kb=new Scanner(System.in);
    int n = kb.nextInt();    
    int[][] arr = new int[n+2][n+2];
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
      arr[i][j]=kb.nextInt();
      }
    }
    System.out.println(T.solution(n,arr));
  }
}

 

 

+) 세련된 풀이

import java.util.*;

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

	public int solution(int n, int[][] arr) {
		int answer = 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)
					answer++;
			}
		}
		return answer;
	}

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

 

 

---

봉우리 체크 방법

1. flag 이용

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

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)
            answer++;
    }
}

 

if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] >= arr[i][j]) {

범위 체크를 하는 이유 : 배열을 선언할 때, 가장자리부분을 0으로 초기화하지 않고, 그대로 [n][n]배열로 만들었기 때문에

 

2. continue 이용

int[][] dis = {{1,0}, {0,1}, {-1,0}, {0,-1}};
for(int i=1; i<=n;i++){
  e: for(int j=1;j<=n;j++){
    for(int k=0;k<4;k++){
      if(arr[i][j]<=arr[i+dis[k][0]][j+dis[k][1]])
        continue e;
    }
    answer++;
  }
}

범위 체크를 안하는 이유 : 가장자리를 0으로 초기화하는 효과를 처리하기 위해, [n+2][n+2]로 선언했기 때문에

 

 

---

+) 범위체크를 하지 않고, flag를 이용한 풀이

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int[][] arr = new int[n+2][n+2];
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        arr[i][j]=in.nextInt();
      }
    }
    System.out.println(solution(n, arr));
  }
  static int solution(int n, int[][]arr){
    int answer=0;
    int[][] dis= {{0,1},{1,0},{-1,0},{0,-1}};
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        boolean flag=true;
        for(int k=0;k<4;k++){
          if(arr[i][j]<=arr[i+dis[k][0]][j+dis[k][1]]){
            flag=false;
            break;
          }
        }
        if(flag) answer++;
      }
    }
    return answer;
  }
}

 

import java.util.*;
class Pos{
    public int x,y;
  
  Pos(int x, int y){
    this.x=x;
    this.y=y;
  }
  public boolean validCheck(int width, int height){
    if(x>=width || x<0){
      return false;
    }
    if(y>=height || y<0){
      return false;
    }
    return true;
  }
}
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int[][] arr = new int[n][n];
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
      arr[i][j]=in.nextInt();
      }
    }
    System.out.println(solution(n,arr));
  }
  static int solution(int n, int[][]arr){
    int answer=0;
    final int[][] check = {{0,1},{1,0},{0,-1},{-1,0}};
    for(int i=0;i<n;i++){
      e: for(int j=0;j<n;j++){
        Pos s = new Pos(i,j);
        for(int k=0;k<4;k++){
          Pos ns = new Pos(i+check[k][0], j+check[k][1]);
    if(ns.validCheck(n,n)==true &&  arr[i][j]<=arr[ns.x][ns.y])
            continue e;   
        }
        answer++;
      }
    }
    return answer;
  }
}

---

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int answer=0;
    int n = in.nextInt();
    int[][] arr=new int[n+2][n+2];
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        arr[i][j]=in.nextInt();
      }
    }

    int[][] dirs={{1,0},{0,1},{-1,0},{0,-1}};
    for(int i=1;i<=n;i++){
      e: for(int j=1;j<=n;j++){
        for(int[] dir:dirs){
          int newi=i+dir[0];
          int newj=j+dir[1];
          if(arr[i][j]<=arr[newi][newj]) continue e;
        }
        answer++;
      }
    }
    System.out.println(answer);
  }
}