[백준][Java] 14397 - 해변

목차

 

문제 정보

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

14397번: 해변

 

난이도 :  Silver 4

유형 : BFS, 그래프 탐색

---

문제 풀이

사각형을 다루는 일반적인 인접행렬과 달리 이 문제는 '육각형'이다.

 

그러므로 이동하는 방향이 6가지이며 또한 홀수, 짝수 줄마다 이동하는 방향이 다르다.

( 육각형들이 붙어 있지 않고 상하좌우로 정렬되어 있다고 생각해 보자)

 

홀수줄 : (-1,-1), (-1,0), (0,1),



그림처럼 짝수, 홀수줄마다 이동하는 방향이 다르다는 것을 알 수 있다.

 

기존  BFS 로직에 6가지 방향을 짝수, 홀수타입으로 나누고

현재 탐색하고 있는 육각형의 줄 위치가 짝수인지 홀수인지 판별하여 탐색하면 된다.

 

또한 탐색하고 있는 육지에서 다음 탐색하는 곳이 해변이면 결괏값을 1씩 증가시키면 되고 

육지라면 다시 큐에 넣어서 계속 진행하면 된다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/* author : DDing77 */

public class Main {
    private final int[][] dirOdd = {{-1, -1}, {-1, 0}, {0, 1}, {1, 0}, {1, -1}, {0, -1}};
    private final int[][] dirEven = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {0, -1}};
    private int N;
    private int M;
    private char[][] map;
    private boolean[][] isVisited;
    private int res;

    public void bfs(int x, int y) {
        Queue<Integer> que = new LinkedList<>();
        que.add(x);
        que.add(y);
        isVisited[x][y] = true;

        while (!que.isEmpty()) {
            int curX = que.poll();
            int curY = que.poll();

            for (int k = 0; k < 6; k++) {
                int nX;
                int nY;
                if ((curX + 1) % 2 == 1) {
                    nX = curX + dirOdd[k][0];
                    nY = curY + dirOdd[k][1];
                } else {
                    nX = curX + dirEven[k][0];
                    nY = curY + dirEven[k][1];
                }
                
                if (nX < 0 || nX >= N || nY < 0 || nY >= M) {
                    continue;
                }

                if (map[nX][nY] == '.') {
                    res++;
                    continue;
                }

                if (isVisited[nX][nY]) {
                    continue;
                }

                que.add(nX);
                que.add(nY);
                isVisited[nX][nY] = true;
            }
        }
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            map[i] = st.nextToken().toCharArray();
        }

        isVisited = new boolean[N][M];
        res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!isVisited[i][j] && map[i][j] == '#') {

                    bfs(i, j);
                }
            }
        }

        System.out.println(res);
    }

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