Code up 4024 호수의 수 구하기

  Ex) 주어진 지도를 분석하여 호수의 개수를 구하는 프로그램을 작성하시오.

 

  - 다음은 어느 호수 지역의 지도를 간략하게 표현한 것이다. 지도는 'L'또는 '.'으로 이루어 진다.

  - 'L'이 의미하는 것은 호수 영역이고 '.'은 호수 이외의 영역을 의미한다.

  - 단, 호수가 상, 하, 좌, 우, 대각선으로 이어진 것은 하나의 호수로 간주한다.

 

L . . . . . . . . L . .

. L . . . . . . . L L .

L L . . . . . . . . L .

. L . . . . . . . . . L

. . L . . . . . . . . L

. . . . . . L . . . . .

. . . . . L . L . . . .

. . . . L . L . L . . .

. . . . . L . L . . . .

. . . . . . L . . . . L

 

  - 위의 경우 호수는 아래 그림과 같이 4개가 존재한다. 상, 하, 좌, 우, 대각선이 연결되어 있으면 하나의 호수로 볼 수 있기 때문이다.

  - 첫째 줄에 두 정수 W, H가 주어진다. (단, 4 <= W, H <= 100)

  - 지도: 직사각형, W:너비, H: 지도의 높이 

  - 두 번째 줄부터 H + 1번째 줄까지 각 줄 마다 'L'또는 '.'가 W개 공백으로 구분하여 주어진다.

 

  Sol)

<hide/>
import java.util.Scanner;

public class Lake {
    static int MAX_COUNT = 201;
    static char[][] AdjMat = new char[MAX_COUNT][MAX_COUNT];
    static int[][] Visited = new int[MAX_COUNT][MAX_COUNT];
    static int Width = 0;
    static int Height = 0;
    static int[][] DirMat = new int[][]{{-1, -1}, {-1, 1}, {1, -1}, {1, 1}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int result = 0;

    public static void DFS(int _row, int _col) {

        Visited[_row][_col] = 1;

        for (int i = 0; i < 8; ++i) {  // 대각선 방향 네 가지 경우
            int nextRow = _row + DirMat[i][0];
            int nextCol = _col + DirMat[i][1];
            if (Visited[nextRow][nextCol] == 1 ||
                    nextRow <= 0 || nextRow > Height ||
                    nextCol <= 0 || nextCol > Width) {
                continue;
            }
            if (AdjMat[nextRow][nextCol] == 'L') {
                System.out.printf("(%d, %d) -> (%d, %d)%n", _row, _col, nextRow, nextCol);
                DFS(nextRow, nextCol);
            }
        }
    }
        public static void main (String[]args){

            Scanner scan = new Scanner(System.in);
            Width = scan.nextInt();
            Height = scan.nextInt();

            for (int i = 1; i <= Height; ++i) {
                for (int j = 1; j <= Width; ++j) {
                    AdjMat[i][j] = scan.next().charAt(0);
                }
            }
// 인접행렬 확인
//            for (int i = 1; i <= Height; ++i) {
//                for (int j = 1; j <= Width; ++j) {
//                    System.out.print(AdjMat[i][j] + " ");
//                }
//                System.out.println();
//            }

            for (int i = 1; i <= Height; ++i) {
                for (int j = 1; j <= Width; ++j) {
                    if (AdjMat[i][j] == 'L' && Visited[i][j] == 0) {
                        DFS(i, j);
                        ++result;
                    }
                }
            }
            System.out.println(result);
        }
}

  ※ 지도의 너비와 높이에 대한 제한이 있다. (W >= 4, H <= 100)

    -> MAX_COUNT를 띄어쓰기까지 고려하여 크게 250으로 잡으면 컴파일에러 없이 정상 작동한다.

    -> 너비와 높이를 낮게 잡으면 "ArrayIndexOutOfBoundsException"이 발생하므로 주의한다.

  - 방향은 상, 하, 좌, 우, 대각선 네 방향까지 총 8군데로 이동 가능하다.

  - 인접행렬을 먼저 scan하여 모두 저장하고나서 새로운 for문에서 DFS를 실행한다.

 

  Note) 입출력 예시

<hide/>
[입력]
12 10
L . . . . . . . . L . .
. L . . . . . . . L L .
L L . . . . . . . . L .
. L . . . . . . . . . L
. . L . . . . . . . . L
. . . . . . L . . . . .
. . . . . L . L . . . .
. . . . L . L . L . . .
. . . . . L . L . . . .
. . . . . . L . . . . L


[출력]
(1, 1) -> (2, 2)
(2, 2) -> (3, 1)
(3, 1) -> (4, 2)
(4, 2) -> (5, 3)
(4, 2) -> (3, 2)
(1, 10) -> (2, 11)
(2, 11) -> (3, 11)
(3, 11) -> (2, 10)
(3, 11) -> (4, 12)
(4, 12) -> (5, 12)
(6, 7) -> (7, 6)
(7, 6) -> (8, 5)
(8, 5) -> (9, 6)
(9, 6) -> (8, 7)
(8, 7) -> (7, 8)
(7, 8) -> (8, 9)
(8, 9) -> (9, 8)
(9, 8) -> (10, 7)
4

 

출처: https://codeup.kr/problem.php?id=4024