문제

https://www.acmicpc.net/problem/2468

코드

public class Main {
    static boolean[][] check;
    static int[][] arr;

    static int[] direc = {1, -1, 1, -1};

    static int number;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        number = Integer.parseInt(st.nextToken()); //배열크기

        check = new boolean[number][number];
        arr = new int[number][number];

        // 최대 높이 이상은 값이 동일할 것이기 때문에 최대 높이 저장
        int max_height = 0;
        for (int i = 0; i < number; i++) {
            StringTokenizer stt = new StringTokenizer(br.readLine());
            for (int j = 0; j < number; j++) {
                int height = Integer.parseInt(stt.nextToken());
                max_height = Math.max(height, max_height);
                arr[i][j] = height;
            }
        }

        int result = 0;
        int max_result = 0;

        // 최대 높이 까지만 실행
        for (int k = 0; k <= max_height; k++) {
            for (int i = 0; i < number; i++) {
                for (int j = 0; j < number; j++) {
                    if (arr[i][j] > k && !check[i][j]) {
                        dfs(i, j, k);
                        result++;
                    }
                }
            }
            max_result = Math.max(result, max_result);
            check = new boolean[number][number];
            result = 0;
        }

        System.out.println(max_result);
    }

    public static void dfs(int n1, int n2, int rain) {
        check[n1][n2] = true;
        int move;

        for (int i = 0; i < 4; i++) {
            if (i < 2) {
                move = n2 + direc[i];
            } else {
                move = n1 + direc[i];
            }
            if (move < 0 || move >= number) continue;
            if (i < 2) {
                if (arr[n1][move] > rain && !check[n1][move]) dfs(n1, move, rain);
            } else {
                if (arr[move][n2] > rain && !check[move][n2]) dfs(move, n2, rain);
            }
        }
    }
}

생각

문제 푸는 것은 30분 정도 걸렸고 8번정도 실패 했다. 크게 두 가지 실수를 했다.

첫 번째 실수

처음에 장마로 차오른 물의 높이가 안정해져 있어서 내 맘대로 문제를 해석해 배열의 크기가 물의 높이다 생각해서 그것으로 비교해서 했다. 공교롭게도 그렇게 했을 때 예시는 정답이 나온다.. 계속 실패가 떠서 문제 다시 읽고 고쳤다.
고치면서 최대 높이 이상 부터는 답이 같다는 생각을 해서 바로 최대 높이 까지 하는 것으로 코드를 짰다.

문제를 차근차근 잘 읽어야 된다는 교훈을 얻었다.

두 번째 실수

그럼에도 계속 실패가 뜨길래 대체 뭘까 하면서 코드를 찬찬히 계속 봤다

if (move < 0 || move >= number) continue;

이 부분에서 move <= 0 으로 해버려서 위치가 1부터 continue가 발생해서 틀린거였다. 공교롭게도 그렇게 했을 때 예시는 정답이 나온다..(2)
저런 부분은 적을 때 생각을 잘하면서 적어야 했는데 그냥 대충 쓰다가 호되게 당했다.

바꿔야할 부분

n1 n2 의 값을 한칸씩 변화시켜주는 코드는 어디서 본건 있어서 생각나는대로 짰는데 먼가 이상해서 정답을 맞추고 검색했더니...

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

이렇게 전역으로 선언한 다음

for(int i = 0; i < number; i++) {
	int n1 = x + dx[i];
	int n2 = y + dy[i];

	if(n1 < 0 || n2 < 0 || n1 > number-1 || n2 > number-1) continue;
    if(map[nx][ny] > height && !checked[nx][ny]) {
		dfs(n1, n2, height);
	}
}

이렇게 쓰는거였다.. 뭔가 짜면서도 계속 이상한 것 같더라니..
비교연산자를 하거나 같음이 없도록 통일하고 -1을 줘서 아예 실수를 예방하는거 좋아보이고
네이밍도 앞으로는 n1 n2가 아니라 nx ny로 바꿔서 구분해야겠다.