[BOJ] 1025. 제곱수 찾기.java

박원준·2025년 10월 14일

🔢 백준 1025 — 제곱수 찾기 (Java)

문제 유형: 브루트포스, 구현
난이도: 🟨 골드5

📌 문제 개요

N×M 숫자 표에서 임의의 시작점 (i, j)과 행/열 공차 (dx, dy)를 정해,
해당 방향으로 이동하며 이어 붙인 수들 중 제곱수의 최댓값을 구하는 문제입니다.
이때 (dx, dy)는 0,0 동시에 될 수 없고, 음수/양수/대각/역방향 모두 허용됩니다.

💡 핵심 아이디어

모든 시작점 (i, j) 에서
가능한 모든 방향 (dx, dy) 로
격자를 벗어날 때까지 숫자를 이어 붙여 정수 t를 만들고
t가 정수 제곱수인지 확인합니다.
제곱수라면 결과를 갱신합니다.

문제의 입력 크기(N, M ≤ 9)가 매우 작아 완전탐색으로 충분합니다.

🧠 구현 (Java)

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 n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }

        int result = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int dx = -n; dx < n; dx++) { // 행 공차
                    for (int dy = -m; dy < m; dy++) { // 열 공차
                        if (dx == 0 && dy == 0) continue;

                        int t = 0;
                        int nx = i, ny = j;
                        while (0 <= nx && nx < n && 0 <= ny && ny < m) {
                            t = 10 * t + arr[nx][ny];

                            int sqrt = (int) Math.sqrt(t);
                            if (sqrt * sqrt == t) {
                                result = Math.max(result, t);
                            }

                            nx += dx;
                            ny += dy;
                        }
                    }
                }
            }
        }

        System.out.println(result);
    }
}