[백준] 16924 십자가 찾기 자바(Java)

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

16924번: 십자가 찾기

 

문제

이 알고리즘의 목적은 주어진 문자 격자에서 모든 별 모양의 패턴을 찾고 각 패턴의 크기와 위치를 출력하는 것이다.

입력은 표준 입력 스트림에서 읽히고 첫 번째 줄에 두 개의 정수 N과 M으로 구성되며, 각각 문자 그리드를 나타내는 길이 M의 N 줄로 구성된다. 문자 '*'는 별 모양의 패턴의 일부를 나타냅니다.

출력은 표준 출력 스트림으로 인쇄되며, 발견된 별 모양 패턴의 수를 나타내는 첫 번째 줄의 정수 k와 그다음 줄의 행 인덱스, 열 인덱스 및 별 모양 패턴의 크기를 나타내는 세 개의 정수 i, j 및 s를 포함하는 k 라인으로 구성됩니다.

 

알고리즘은 다음과 같이 작동합니다.

입력을 읽고 빈 배열 목록을 초기화하여 보관합니다.

격자 안의 모든 세포에 대해 반복하며, 각각의 세포가 별 모양의 패턴의 일부인지 확인한다.

패턴의 일부인 경우 중첩 루프를 사용하여 패턴 크기를 확인하고 visited 2차 배열을 방문으로 표시합니다.

 

2단계 이후에 방문하지 않았으면 -1을 출력하고 종료합니다.

패턴 배열 목록에서 반복하고 위에서 설명한 대로 출력 형식을 지정하여 답을 인쇄합니다.

 

코드

package main.iyk2h;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
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 N = Integer.parseInt(st.nextToken()); // 행
        int M = Integer.parseInt(st.nextToken()); // 열

        char[][] inputArr = new char[N][M]; // 입력 배열
        boolean[][] visited = new boolean[N][M]; // 방문 여부 배열
        ArrayList<ArrayList<Integer>> answerList = new ArrayList<>(); // 결과를 저장할 리스트

        // 입력 받기
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                inputArr[i][j] = line.charAt(j);
            }
        }

        // 주어진 배열을 탐색하면서 4방향으로 '*'인 도형을 찾기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int size = 0; // '*'를 중심으로 얼마나 큰 도형인지 저장할 변수
                if (inputArr[i][j] == '*') {
                    for (int k = 1; ; k++) {
                        // 현재 위치에서 k만큼 떨어진 위치에 '*'가 있는지 확인
                        if (i - k >= 0 && j-k >=0 && i + k < N && j + k < M) {
                            if (inputArr[i - k][j] == '*' && inputArr[i + k][j] == '*'
                                    && inputArr[i][j - k] == '*' && inputArr[i][j + k] == '*') {
                                // 4방향에 모두 '*'가 있다면 크기를 업데이트
                                size = k;
                            } else {
                                // '*'가 아닌 문자가 하나라도 있으면 종료
                                break;
                            }
                        } else {
                            // 범위를 벗어나면 종료
                            break;
                        }
                    }
                }

                // '*'를 중심으로 size 크기의 도형이 있다면 결과 리스트에 추가하고 방문 처리하기
                if (size > 0) {
                    visited[i][j] = true; // 중심점 방문 처리

                    // 4방향에 있는 '*'도 방문 처리하기
                    for (int k = size; k > 0; k--) {
                        // 결과 리스트에 추가
	                    answerList.add(new ArrayList<>(Arrays.asList(i+1, j+1, k)));
                    
                        visited[i + k][j] = true;
                        visited[i - k][j] = true;
                        visited[i][j + k] = true;
                        visited[i][j - k] = true;
                    }
                }
            }
        }

        // 입력 배열을 전부 방문했는지 확인
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 방문하지 않았는데 '*'이 남아 있다면 종료
                if (inputArr[i][j] == '*' && !visited[i][j]) {
                    System.out.println(-1);
                    return;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(answerList.size()).append("\n");

        
        for (ArrayList<Integer> inList : answerList) {
            sb.append(inList.get(0)).append(" ").append(inList.get(1)).append(" ")
                    .append(inList.get(2)).append("\n");
        }

        System.out.println(sb);
    }
}