[Baekjoon 14397] 해변 - JAVA

[Silver IV] 해변 - 14397

문제 링크

성능 요약

메모리: 14216 KB, 시간: 128 ms

분류

그래프 이론, 그래프 탐색, 구현

문제 설명

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

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

입력

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

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

출력

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

문제 풀이

지도와 정육각형의 구조에 대한 개념을 이해해야 한다.

1. 주어진 지도에는 단위 정육각형들이 격자 형태로 배열되어 있다.
2. 이 정육각형들의 변 중에서 한 쪽은 물이고, 한 쪽은 땅이 된다.
3. 해변은 정육각형의 변 중에서 물과 땅이 교차하는 부분을 의미한다.

로직은 아래와 같다.

1. 각 정육각형의 모서리와 변에서 땅과 물이 교차하는 부분을 해변으로 간주한다.
2. 지도를 순회하며 각 정육각형의 모서리와 변에 대해 교차 여부를 확인하고 해변의 길이를 누적시킨다.

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

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

        int numRows = Integer.parseInt(st.nextToken());
        int numCols = Integer.parseInt(st.nextToken());
        int totalBeachLength = 0;

        char previousTile, currentTile;
        String[] hexagonRows = new String[2];
        String currentRow;

        for (int i = 0; i < numRows; i++) {
            currentRow = hexagonRows[i % 2] = br.readLine();
            previousTile = ' ';

            // Check alternating tiles for different types (water vs. land)
            for (int j = 0; i > 0 && j < 2 * numCols; j++) {
                currentTile = hexagonRows[j % 2].charAt(j / 2);
                if ((previousTile ^ currentTile) == 13) {
                    totalBeachLength++;
                }
                previousTile = currentTile; 
            }

            // Count transitions in the same row
            for (int j = 1; j < currentRow.length(); j++) {
                if (currentRow.charAt(j) != currentRow.charAt(j - 1)) {
                    totalBeachLength++;
                }
            }
        }

        System.out.println(totalBeachLength);
    }
}

코드 풀이

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

        int numRows = Integer.parseInt(st.nextToken());
        int numCols = Integer.parseInt(st.nextToken());
        int totalBeachLength = 0;

        char previousTile, currentTile;
        String[] hexagonRows = new String[2];
        String currentRow;
    }
}

• numRows: 해안 지도의 행(row)을 저장하는 변수
• numCols: 해안 지도의 열(column)을 저장하는 변수
• totalBeachLength: 해안 라인의 총 길이를 저장하는 변수
• previousTile: 이전 타일의 상태를 저장하는 변수로, 물인지 땅인지를 비교하기 위해 사용
• currentTile: 현재 타일의 상태를 저장하는 변수로, 이전 타일과 비교하여 물과 땅의 경계를 판단
• hexagonRows: 이중 버퍼링을 위한 문자열 배열로, 현재 행과 그 이전 행의 타일 데이터를 저장
• currentRow: 현재 행의 타일 데이터를 저장하는 문자열 변수

for (int i = 0; i < numRows; i++) {
    currentRow = hexagonRows[i % 2] = br.readLine();
    previousTile = ' ';

    for (int j = 0; i > 0 && j < 2 * numCols; j++) {
        currentTile = hexagonRows[j % 2].charAt(j / 2);
        if ((previousTile ^ currentTile) == 13) {
            totalBeachLength++;
        }
        previousTile = currentTile; 
    }

    for (int j = 1; j < currentRow.length(); j++) {
        if (currentRow.charAt(j) != currentRow.charAt(j - 1)) {
            totalBeachLength++;
        }
    }
}

• currentRow: 현재 처리 중인 행의 타일 데이터를 저장하는 문자열
• 첫 번째 for문에서는 각 행을 처리한다.
  현재 행 데이터를 읽어 currentRow에 저장하고, 현재 행과 이전 행의 데이터를 hexagonRows 배열에 저장하고, previousTile 변수를 초기화
• 두 번째 for문은 현재 행의 열(column)을 처리한다.
  짝수 번째 열과 홀수 번째 열의 타일을 번갈아가며 비교하여 물과 땅의 경계를 찾아 totalBeachLength를 증가시킨다.
• 세 번째 for문은 같은 행 내에서 인접한 타일들을 비교하여 타일의 변화가 있는 경우 totalBeachLength를 증가시킨다.

System.out.println(totalBeachLength);

• 최종적으로 계산된 총 해안 라인 길이인 totalBeachLength를 출력한다.