백준 14397 - 해변 (자바 - 그래프)

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

14397번: 해변

 

* 문제 요약

단위 정육각형으로 이루어져 있는 지도가 주어졌을 때, 해변의 길이를 구하는 프로그램을 작성하시오.

해변은 정육각형의 변 중에서 한쪽은 물인데, 한쪽은 땅인 곳을 의미한다.

* 입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 <= N, M <= 50)

둘째 줄부터 N개의 줄에 지도가 주어진다. '.' 은 물, '#' 은 땅이다.

 

* 출력

첫째 줄에 해변의 길이를 출력한다.

 

* 예시

 

* 해결 과정

처음엔 2차원 배열의 모양만 생각하고 좌표를 8각으로 잡아놓고 DFS 탐색을 수행했다가 잘 안되서 결국 풀이를 찾아본 문제.

풀이를 보고도 단위 정육각형으로 구성된 지도에서 홀수 줄, 짝수 줄을 구분하여 탐색 좌표를 조금씩 다르게 해주어야 한다는 것이 잘 이해가 가지 않다가, 육각형들이 위에서 아래로 지그재그 형태로 내려간다고 생각을 해보니 그제서야 좌표가 서로 다르게 적용되는게 이해가 되었다.

위, 아래 방향을 정석적으로 위, 아래 방향으로 잡을게 아니라 지그재그 형태로 육각형들이 붙어서 내려올 때 현재 줄이 홀수 줄이냐 짝수줄이냐에 따라 자신의 위, 아래에 있는 육각형과 접해있는 변의 위치가 달라지게 되기 때문에 홀수 줄, 짝수 줄에 따라서 위, 아래로 접하는 변이 있는 방향은 2차원 배열상에서도 위, 아래에 해당하는 좌표로 설정해주어야 한다.((-1, 0), (1, 0))

 

- 홀수 줄일경우 좌표 : odd[6][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, -1 }, { 1, -1 } };
- 짝수 줄일경우 좌표 : even[6][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 1 }, { 1, 1 } };

 

위와 같이 odd, even 배열의 인덱스 별로 6방향의 좌표를 설정해준 다음 DFS(깊이 우선탐색) 방식으로 그래프를 탐색해준다.

1. 이중 반복문을 통해 2차원 배열에서 boolean 타입으로 만들어진 visited 배열상에서 방문 표시가 되어있지 않은 인덱스를 탐색한 경우 dfs(int i, int j) 메소드를 호출한다.

2. dfs(int i, int j) 메소드는 다음과 같이 동작한다.

  - 2차원 배열에서 (i, j) 인덱스의 값이 '#' 인 경우 다음과 같이 조건문을 수행한다.

    - visited 배열에서 현재 (i, j) 인덱스 값을 true 로 초기화하여 방문 표시를 해준다.

    - ((i + 1) % 2 == 1) 조건을 만족하는 경우. 즉, 현재 행에서 1을 더한 값을 2로 나눴을 때 나머지가 1인 경우(홀수 줄인경우) 다음과 같이 반복문을 수행한다.

      -> 홀수 줄일경우 육각형의 각 변이 바라보는 좌표가 저장된 배열 odd 의 각 행에서 0번째 열에 있는값과 i 를 더해 새로운 인덱스 di 를 만들고, 1번째 열에 있는값과 j 를 더해 새로운 인덱스 dj 를 만들어준다.

      -> di, dj 값이 기존 2차원 배열의 크기를 벗어나면 아무 로직도 수행하지 않는다.

      -> 그렇지 않은 경우 2차원 배열에서 (di, dj) 인덱스의 값이 '.' 인 경우 (i, j) 인덱스와 (di, dj) 인덱스는 서로 '#', '.' 로 맞닿아 있으므로 해변에 해당된다. 그렇기 때문에 해변의 갯수를 표현하는 변수 count 의 값을 1 늘려준다.

      -> (di, dj) 인덱스의 값이 '#' 이고 visited 배열에서 (di, dj) 인덱스에 아직 방문하지 않은 경우 dfs() 메소드에 (di, dj) 인덱스를 넘겨주는 것으로 재귀호출을 해준다.

    - ((i + 1) % 2 == 0) 조건을 만족하는 경우. 즉, 현재 행에서 1을 더한 값을 2로 나눴을 때 나머지가 0인 경우(짝수 줄인경우) 반복문에서 (i, j) 인덱스 각각에 odd 배열의 값들을 더해줘야 하는 홀수 줄의 경우와 달리 even 배열의 0번째, 1번째 열을 더해서 새로운 인덱스 (di, dj) 를 만들어준다.

    - 그외의 로직은 홀수 줄일때와 동일하다.

3. 스택으로 쌓인 dfs() 메소드 재귀 호출이 모두 종료되고 1에서 수행했던 이중반복문까지 모두 끝나고 나면 count 변수를 정답으로 출력해준다.

 

* 코드(DFS 재귀호출)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static boolean[][] visited;
    static char[][] beach;
    static int[][] odd = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, -1 }, { 1, -1 } };
    static int[][] even = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 1 }, { 1, 1 } };
    static int n, m;
    static int count = 0;

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        beach = new char[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            beach[i] = br.readLine().toCharArray();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    dfs(i, j);
                }
            }
        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private void dfs(int i, int j) {

        if (beach[i][j] == '#') {
            visited[i][j] = true;
            // 홀수 줄
            if ((i + 1) % 2 == 1) {
                for (int k = 0; k < 6; k++) {
                    int di = i + odd[k][0];
                    int dj = j + odd[k][1];
                    if (di < 0 || di >= n || dj < 0 || dj >= m) {
                        continue;
                    } else {
                        if (beach[di][dj] == '.') {
                            count++;
                        } else if (beach[di][dj] == '#' && !visited[di][dj]) {
                            dfs(di, dj);
                        }
                    }
                }
            }
            // 짝수 줄
            else if ((i + 1) % 2 == 0) {
                for (int k = 0; k < 6; k++) {
                    int di = i + even[k][0];
                    int dj = j + even[k][1];
                    if (di < 0 || di >= n || dj < 0 || dj >= m) {
                        continue;
                    } else {
                        if (beach[di][dj] == '.') {
                            count++;
                        } else if (beach[di][dj] == '#' && !visited[di][dj]) {
                            dfs(di, dj);
                        }
                    }
                }
            }
        }
    }
}

 

그런데 이중 반복문에서 visited 배열의 현재 인덱스 위치 방문여부를 확인한다는 점을 감안하여 dfs() 메소드 내부에서 (di, dj) 인덱스 값이 '#' 이고 (di, dj) 인덱스 위치를 방문하지 않았을 때 dfs() 메소드를 재귀호출 하는 코드를 삭제하고 다시 제출해봤더니 위의 코드와 마찬가지로 통과를 받는 것을 알 수 있었다.

아래는 dfs() 메소드 재귀 호출을 삭제하고 이중 반복문 만으로 방문하지 않은 위치를 발견했을 경우 해당 위치가 '#' 일 때 홀수 줄, 짝수 줄의 경우를 구분하여 해변의 갯수를 계산하는 코드이다.

 

* 코드(DFS 재귀호출을 하지 않는 경우)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static boolean[][] visited;
    static char[][] beach;
    static int[][] odd = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, -1 }, { 1, -1 } };
    static int[][] even = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 1 }, { 1, 1 } };
    static int n, m;
    static int count = 0;

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        beach = new char[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            beach[i] = br.readLine().toCharArray();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    dfs(i, j);
                }
            }
        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private void dfs(int i, int j) {

        if (beach[i][j] == '#') {
            visited[i][j] = true;
            // 홀수 줄
            if ((i + 1) % 2 == 1) {
                for (int k = 0; k < 6; k++) {
                    int di = i + odd[k][0];
                    int dj = j + odd[k][1];
                    if (di < 0 || di >= n || dj < 0 || dj >= m) {
                        continue;
                    } else {
                        if (beach[di][dj] == '.') {
                            count++;
                        }
                    }
                }
            }
            // 짝수 줄
            else if ((i + 1) % 2 == 0) {
                for (int k = 0; k < 6; k++) {
                    int di = i + even[k][0];
                    int dj = j + even[k][1];
                    if (di < 0 || di >= n || dj < 0 || dj >= m) {
                        continue;
                    } else {
                        if (beach[di][dj] == '.') {
                            count++;
                        }
                    }
                }
            }
        }
    }
}

 

2차원 배열에서 방문 여부, 현재 인덱스 위치의 값에 따라 인접해있는 주변의 적절한 인덱스 방향에 대한 탐색을 통해 답을 구했으므로 그래프 탐색 문제에 해당된다.