[백준] 1025 제곱수 찾기 - 완전탐색 + 아이디어 JAVA

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

1025번: 제곱수 찾기

코드설명

브루트포스를 활용한 문제입니다.

 

문제에 대한 이해가 쉽지 않으므로, 입력예시를 통해 문제이해 관련하여 설명해보았습니다.

 

입력예시

2 3
123
456

위의 입력예시를 두고 설명해보겠습니다.

(0,0) 부터 시작합니다. 여기서 행의 등차는 -2 부터 2까지입니다. ( -2 부터 2까지인 이유는 3일때 -2를 통해 1로 이동하기 때문 )

열의 등차는 -3 부터 3 까지 입니다.

 

1. (0,0)에서는 처음에 (-2, -3)으로 시작합니다. 둘다 음수이기에 무시합니다. 여기서 음수인경우는 모두 무시하기 위해 바로 행의 등차가 0, 열의 등차가 0 인경우로 이동하겠습니다.
2. 행의 등차와 열의 등차가 둘다 (0, 0)인 경우에는 움직이지 않았으므로 continue 처리합니다. ( continue 처리 안할경우 0,0에서 움직이지 않아서 계속해서 무한루프를 돕니다. )
3. 이제 드디어 행의 등차가 1 이고, 열의 등차가 0 인경우입니다. (0, 0) 은 1 입니다. 해당 값을 now값에 넣어서 now = 1 이 됩니다. 그리고 1 의 제곱근은 1 이기에 result값은 1 로 갱신됩니다.
4. 이제 (0, 0) -> (1,0) 으로 이동합니다. now = 1 * 10 으로 now = 10 이 되고, (1,0) 의 값인 2 가 now 에 더해져서 now = 12 가 됩니다. now 는 완전 제곱수가 아니기에 해당 사항은 result값이 변경이 되지 않습니다.
5. 이제 (0,0) -> (1,0 ) -> (2,0 ) 으로 이동해서 같은 로직을 반복합니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N, M;
	public static int[][] map;
	public static String S, T;
	public static int result = -1;
    public static void main(String[] args) 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 int[N][M];
    	for(int i=0;i<N;i++) {
    		String s = br.readLine();
    		for(int j=0;j<M;j++) {
    			map[i][j] = Integer.parseInt(String.valueOf(s.charAt(j)));	
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			for(int di =-N; di<N;di++){ //행의 등차값 ( 행의 등차값은 -N ~ +N 까지 ) 
    				for(int dj = -M; dj<M;dj++) { //열의 등차값 ( 열의 등차값은 -M ~ +M 까지 )
    					
    					if(di == 0 && dj == 0) { //둘다 움직이지 않을떄
    						continue;
    					}
    					
    					int nI = i;
    					int nJ = j;
    					int now = 0;
    					while( nI >= 0 && nI < N && nJ >= 0 && nJ < M) {
    						//자리수 10의 자리수 씩 체크하기 위해 로직처리
    						now *= 10;
    						now += map[nI][nJ];
    						
    						//제곱근인지 판별
    						int sqrt_check = (int) Math.sqrt( (double) now);
    						if( sqrt_check * sqrt_check == now) result = Math.max(result, now);
    						
    						nI += di;
    						nJ += dj;
    					}
    					
    				}
    			}
    		}
    	}
    	System.out.println(result);
    	
    	
    }
    
    
}