밤하늘 사진에서 별 세기

2026-11-03 5 분 소요

문제

N×N 크기의 흑백 밤하늘 사진이 있다. 각 픽셀에는 밝기 값이 쓰여 있다. 어떤 픽셀이 상하좌우 네 이웃 픽셀보다 모두 밝으면 그 픽셀을 별로 본다. 사진 바깥은 밝기 0(완전한 어둠)으로 가정한다. 사진에 별이 몇 개인지 센다.

2 ≤ N ≤ 50, 밝기는 1 이상 100 이하의 정수
입력: 첫 줄에 N, 둘째 줄부터 N줄에 걸쳐 N개의 밝기 값
출력: 별의 개수

입력                출력
                 13
2 6 1 3
5 2 7 2
3 8 2 5
7 1 4 1
2 5 3 6

예를 들어 왼쪽 위 4는 오른쪽 2, 아래 1보다 밝고 위와 왼쪽은 사진 바깥(0)이므로 별이다. 가운데 8은 네 이웃 2, 1, 3, 2보다 모두 밝아 별이다. 오른쪽 위 1은 왼쪽 6보다 어두워 별이 아니다.

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비의 1119번 문제를 소재와 예제만 바꿔 재구성했다.

공통 코드

아래 시도들은 입력을 읽는 부분과 방향 상수를 공유한다. 각 시도에서는 별을 세는 부분만 보여준다.

import java.util.Scanner;

public class Main {
    // d번째 이웃 = (i + DI[d], j + DJ[d]) — 순서대로 위, 아래, 왼쪽, 오른쪽
    static final int[] DI = {-1, 1, 0, 0};
    static final int[] DJ = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] sky = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                sky[i][j] = sc.nextInt();

        int count = 0;
        // ... 별을 세는 부분 (각 시도 참고)
        System.out.println(count);
    }
}

sky[i][j]에서 i는 행(위→아래), j는 열(왼쪽→오른쪽)이다. DI, DJ는 현재 칸에서 이웃 칸으로 갈 때 행과 열에 각각 더할 값이다. 예를 들어 d = 0이면 (i - 1, j), 곧 바로 위 칸이다.

시도 1 — 네 방향을 그대로 비교

접근

“상하좌우보다 밝으면 별”을 조건식 하나로 옮겼다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int b = sky[i][j];
        if (b > sky[i - 1][j] && b > sky[i + 1][j]
                && b > sky[i][j - 1] && b > sky[i][j + 1]) {
            count++;
        }
    }
}

결과

실패 — 실행 중 예외.

i = 0에서 sky[-1][j]를 읽는 순간 ArrayIndexOutOfBoundsException. 맨 윗줄, 맨 아랫줄, 양쪽 끝 열 — 가장자리 전부가 예외 지점이다.

분석

문제의 “사진 바깥은 0”이라는 조건을 코드에 옮기지 않았다. 배열은 바깥을 모른다. 바깥으로 나가는 인덱스를 읽기 전에 막아야 한다.

시도 2 — 방향마다 범위 체크

접근

이웃이 사진 바깥이면 배열을 읽지 않고 0을 쓰도록, 방향마다 삼항 조건을 덧댔다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int b = sky[i][j];
        int up    = (i > 0)     ? sky[i - 1][j] : 0;
        int down  = (i < n - 1) ? sky[i + 1][j] : 0;
        int left  = (j > 0)     ? sky[i][j - 1] : 0;
        int right = (j < n - 1) ? sky[i][j + 1] : 0;
        if (b > up && b > down && b > left && b > right) {
            count++;
        }
    }
}

결과

성공 — 정답 13.

복잡도: 시간 O(N²), 공간 O(N²). N²개의 칸마다 이웃 4개를 비교한다.

예외 없이 가장자리까지 정확히 센다.

분석

바깥 좌표를 읽기 전에 막았으니 예외는 사라졌고, 0으로 대체한 덕에 “바깥은 0”이라는 조건도 정확히 반영됐다.

다만 같은 비교가 삼항 네 줄과 조건식 한 줄, 모두 다섯 자리에 흩어져 있다. 대각선까지 포함해 8방향으로 바꾸거나 >를 >=로 바꾸려면 흩어진 자리를 전부 찾아 고쳐야 한다. 이 시점에서 “방향을 데이터로 빼야겠다”는 생각이 들었다.

시도 3 — 방향 배열 + 플래그 (채택)

접근

방향을 DI, DJ 배열로 분리했다. 그리고 조건을 뒤집어 “별이다 = 모든 이웃보다 밝다(>)” 대신 그 부정인 “별이 아니다 = 자신과 같거나 더 밝은 이웃(>=)이 하나라도 있다“를 플래그로 확인한다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        boolean isStar = true;
        for (int d = 0; d < DI.length; d++) {
            int ni = i + DI[d];
            int nj = j + DJ[d];
            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            if (sky[ni][nj] >= sky[i][j]) {
                isStar = false;
                break;
            }
        }
        if (isStar) count++;
    }
}

결과

성공 — 정답 13.

복잡도: 시간 O(N²), 공간 O(N²). 시도 2와 같다 — 방향 루프가 생겼지만 반복 횟수가 상수(4)다.

이웃이 사진 바깥이면 continue로 건너뛴다. 밝기가 1 이상이라 바깥의 0은 어차피 반례가 될 수 없으니 비교 자체를 생략해도 된다.
범위 안의 이웃이 자신과 같거나 더 밝으면 isStar = false 후 break — 남은 방향은 볼 필요가 없다.
네 방향을 다 통과하면 isStar가 true로 남고, 그때만 센다.

분석

시도 2의 b > up && b > down && b > left && b > right는 이웃이 네 개라는 사실이 식 안에 박혀 있다. 방향을 더하거나 빼려면 식을 다시 써야 한다.

이 식을 반복문으로 바꾸고 싶은데, 반복문은 한 번에 이웃 하나만 본다. 그래서 “지금까지 본 이웃은 전부 통과했나”를 다음 바퀴로 넘겨줄 변수가 필요하다 — 그게 플래그다. true로 시작해서, 자신과 같거나 더 밝은 이웃(반례)을 만나면 false로 바꾼다. “모두 ~이다”는 반례 하나면 거짓이니 그 자리에서 break해도 된다.

결과적으로 방향은 DI/DJ 데이터로, 비교는 루프 안의 한 줄로 분리된다. 8방향으로 늘려도 배열에 값만 더하면 되고, 조건을 바꿀 때 고칠 자리도 하나뿐이다. break로 일찍 끝나는 건 덤이다 — 시도 2의 &&도 첫 거짓에서 멈추므로 새로 얻은 이익은 아니다.

다른 방법 — 바깥을 0으로 패딩

범위 체크 자체를 없애고 싶다면 배열을 (N+2)×(N+2)로 잡아 테두리를 0으로 채우는 방법도 있다. Java는 new int[n+2][n+2]가 0으로 초기화되므로 안쪽 N×N에만 값을 채우면 된다.

int[][] sky = new int[n + 2][n + 2];
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        sky[i][j] = sc.nextInt();

int count = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        boolean isStar = true;
        for (int d = 0; d < DI.length; d++) {
            if (sky[i + DI[d]][j + DJ[d]] >= sky[i][j]) {
                isStar = false;
                break;
            }
        }
        if (isStar) count++;
    }
}

복잡도는 시간 O(N²), 공간 O(N²)로 같다(테두리 2행 2열은 상수 오버헤드). 범위 체크가 사라져 안쪽 루프가 한 줄 줄었지만, 모든 인덱스에 +1 오프셋이 따라붙어 디버깅할 때 “1부터 시작했지?”를 매번 다시 떠올려야 한다. 읽기 편한 쪽을 고르면 된다.

정리

시도	핵심	복잡도	결과
1. 그대로 비교	경계 조건을 코드에 안 옮김	—	예외
2. 방향별 범위 체크	바깥은 0으로 치환	O(N²)	정답, 수정 지점이 다섯 곳
3. 방향 배열 + 플래그 (채택)	방향은 데이터로, 비교는 루프로	O(N²)	정답, 수정 지점이 한 곳
다른 방법. 패딩	바깥을 실제 0으로 둠	O(N²)	범위 체크 제거, 오프셋 부담

채택: 시도 3. 정답과 복잡도는 시도 2와 같지만, 방향과 조건을 바꿀 때 고칠 자리가 한 곳이라 가장 읽기 쉽고 바꾸기 쉽다.

2차원 격자 문제에서 “바깥은 어떻게 취급하나”는 문제 조건의 일부다. 코드에 옮기지 않으면 가장자리에서 터진다.
같은 비교를 방향마다 반복하고 있다면 방향 배열 + 플래그로 접자. 방향 추가, 조건 변경이 한 자리에서 끝난다.

Twitter Facebook LinkedIn