[JAVA] 봉우리 - Array(1, 2차원 배열)

 

public class INF0210 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] grid = new int[n+2][n+2];

        //0 채우기
        for (int i = 0; i <n; i++) {
            for (int j = 0; j < n; j++) {
                grid[0][j] = 0;
                grid[n-1][j] = 0;
                grid[i][0] = 0;
                grid[i][n-1] = 0;
            }
        }

        //중앙에 값 입력받기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i+1][j+1] = sc.nextInt();
            }
        }

        INF0210 inf = new INF0210();
        System.out.println(inf.solution(n, grid));
    }

    public int solution(int n, int[][] grid) {
        int answer = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if(grid[i][j] > grid[i-1][j] && grid[i][j] > grid[i+1][j] && grid[i][j] > grid[i][j-1] && grid[i][j] > grid[i][j+1]) {
                    answer++;
                }
            }
        }

        return answer;
    }
}

풀이

정석대로 가생이에 0 채우고

중앙에 값을 입력받아 상하좌우를 비교한 방식.

 

문제는 없지만 나중에 DFS, BFS 등 난이도 있는 문제를 하다 보면 영상처럼 경곗값 확인을 자주 하게 되는데,

나처럼 if문에 상하좌우 조건을 4개 걸 경우에 대각성까지 8방향을 탐색하는 문제가 나오면 8개의 조건을 걸어야 해 가독성에서 좋지 않다고 한다.

 

강의에 있는 코드를 이해해 보자.

 

public class INF0210T1 {
    public static void main(String[] args){
        INF0210T1 T = new INF0210T1();
        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));
    }

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

        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;
    }
}

풀이

1. 시계 방향에 대한 x, y 배열을 미리 만들어 놓는다. ex) 현재 좌표에서 x-1하면 상, y+1 하면 우, x+1하면 하, y-1하면 좌`int[] dy = {0, 1, 0, -1};`

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

 

2. 현재 좌표에서 배열을 더해 시계 방향대로 돌면서 비교한다.

` int nx = i+dx[k]; `

` int ny = j+dy[k]; `

 

3. 0에 대한 부분은 outOfRange 에러가 터지기 때문에 0에 좌표에 대한 조건을 건다.

`nx >= 0 && nx < n && ny >= 0 && ny < n`

 

`nx < n, ny < n`인 이유는 이차원 배열의 크기가 n*n 크기이면 행 인덱스 번호는 0번부터 n-1번까지 생기기 때문이다.

그래서 nx < n 일 때만 접근하도록 해주는 것이다.

만약 현재 지점이 arr[n-1][0] 지점이라고 한다면 이 지점에서 6시 방향(아래방향)을 탐색하게 되면 nx는 n이 될 수 있다.

 

 

4. 상, 하, 좌, 우 중에 나보다 크거나 같은 값이 있다면 루프를 더 이상 돌지 않아도 됨

` arr[nx][ny] >= arr[i][j] `

` flag = false; `

` break; `

 

 

---

인프런 - 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의에 나오는 알고리즘 문제입니다.