[BOJ - JAVA] 1025 - 제곱수 찾기(브루트포스)

# 주소

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

1025번: 제곱수 찾기

# 문제

# 문제 해설 및 코드 리뷰

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

public class Main {
    static int n, m;
    static char[][] arr = new char[10][10];
    static int max = -1;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0; i < n; i++){
            String str = scan.next();
            for(int j = 0; j < m; j++){
                arr[i][j] = str.charAt(j);
            }
        }
        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++){
                        int val = 0;
                        if(dx == 0 && dy == 0){
                            continue;
                        }
                        int nowX = i;
                        int nowY = j;
                        while(nowX >= 0 && nowX < n && nowY >= 0 && nowY < m){
                            val = 10 * val + (arr[nowX][nowY] - '0');
                            if(check(val)){
                                max = Math.max(max, val);
                            }
                            nowX += dx;
                            nowY += dy;
                        }
                    }
                }
            }
        }
        System.out.println(max);
    }
    static boolean check(int x){
        int t = (int)Math.sqrt(x);
        if(t * t == x)
            return true;
        return false;
    }
}

4중 for문을 써서 구현해야 합니다.

문제를 이해하려해도 도저히 이해가 안가더라고요.

좀 이해하기 쉽게 설명을 해주시지 백준님.. ㅠ 설명이 한 번 업데이트 되었다 하는데 계속 읽어도 뭔 소리지 싶어서 다른 블로그 보고 이해했습니다.

등차수열대로 행, 열이 선택된다는 얘기였는데 값을 등차수열로 매기는 줄 알았거든요 ㅋㅋㅋ..

한 번 살펴보겠습니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 0; i < n; i++){
    String str = scan.next();
    for(int j = 0; j < m; j++){
        arr[i][j] = str.charAt(j);
    }
}

i와 j를 입력받습니다만 입력할 때 값들은 띄어쓰기 없이 입력되기 때문에 따로 값을 끊어서 저장해주어야 합니다. 그러므로 String str에 값을 제일 처음 입력받고 m의 크기만큼 arr[i][j]에 넣어주도록 합니다.

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++){

4중 for문입니다.

이 dx와 dy는 등차수열을 이룰 행과 열입니다.

3번째의 for문과 4번째의 for문에서 -n과 -m부터 탐색해야하는 이유는, arr의 탐색을 정방향으로도 해보고 역방향으로도 탐색해봐야 하기 때문에 그렇습니다.

문제 예제를 보면 순서대로도 입력받아보고 거꾸로도 입력받는 경우가 나오잖아요.

예를 들어 4 5 6도 456, 654 이런식으로 말이지요.

그렇기 때문에 -n과 -m부터 탐색해야만 하는 것입니다.

그런데 이런 의문이 드실 수도 있습니다.

 

for(int dx = -n; ~ )이게 아니라 for(int dx = -n + 1; dx < n; i++)가 되어야 하는 것 아닐까??? 

하는 의문도 드실거라 생각합니다.

당연히 그럴 수 있지요.

대부분의 인덱스의 크기가 n만큼이기 때문에 n만큼 더하거나 빼면 인덱스가 초과하니까요.

맞습니다.

하지만 반은 맞고 반은 틀렸습니다.

이런 반례를 줘볼게요.

 

10 1

1 1

이렇게 입력되면 출력은 얼마가 나와야 할까요?

10입니다.

눈치가 빠른 분들은 눈치채셨겠지만 10만 답이 되려면 오로지 10만 탐색해야합니다.

그런데 세번째, 네번째 for문에서 시작점을 -n+1, -m+1로 잡으면 10과 1을 같이 탐색해버리게 됩니다.

이해 가셨나요?

결국 10만 선택되게 하기 위해서는 불가피하게 탐색 필터를 -n까지 더 확장시켜야 된다는 것입니다.

(이해 안되시면 댓글남겨주세요.)

그럼 코드를 다시 살펴봅시다.

int val = 0;
if(dx == 0 && dy == 0){
    continue;
}

val = 0으로 지정하고 dx와 dy가 0이 되면 탐색하지 않습니다.

왜냐하면 행과 열이 등차수열로 이루어져야 하는데 0이 dx,dy일 경우 무한루프에 빠져버리기 때문입니다.

int nowX = i;
int nowY = j;

nowX와 nowY는 i와 j라고 하겠습니다.

현재의 i와 j를 뜻합니다.

while(nowX >= 0 && nowX < n && nowY >= 0 && nowY < m){

bfs문의 탐색 예외처리구문과 비슷하죠?

nowX와 nowY가 0과 n,m사이일때만 탐색하도록 합시다.

val = 10 * val + (arr[nowX][nowY] - '0');
if(check(val)){
    max = Math.max(max, val);
}

val값은 10 x val한 것에다가 현재의 arr값을 더해주면서 val값을 완성할 것입니다.

그리고 val은 check()메서드로 검증을 할텐데, check()함수는 

    static boolean check(int x){
        int t = (int)Math.sqrt(x);
        if(t * t == x)
            return true;
        return false;
    }

이렇게 구성됩니다.

파라미터로 가지고온 val값을 제곱근을 씌우고 정수로 변환한 것을 t에 담은 뒤 t * t == x이면 true를, 아니면 false를 내보냅니다.

그리고 그렇게 판별한 boolean값으로 

val = 10 * val + (arr[nowX][nowY] - '0');
if(check(val)){
    max = Math.max(max, val);
}
nowX += dx;
nowY += dy;

max에 값을 싣을지 말지를 결정하고 계속해서 nowX에 dx, nowY에 dy를 더하면서 while문을 반복합니다.

 

감사합니다.