Baek Joon _백준 1028> DP > #48 다이아몬드 광산

문제

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

1028번: 다이아몬드 광산

다이아몬드 광산은 0과 1로 이루어진 R행*C열 크기의 배열이다.

다이아몬드는 1로 이루어진 정사각형의 경계선을 45도 회전시킨 모양이다. 크기가 1, 2, 3인 다이아몬드 모양은 다음과 같이 생겼다.

다이아몬드 광산에서 가장 큰 다이아몬드의 크기를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다.

출력

첫째 줄에 다이아몬드 광산에서 가장 큰 다이아몬드의 크기를 출력한다. 만약 다이아몬드가 없을 때는 0을 출력한다.

 

 

2. 나의 풀이

 

1)

- 참고로 풀진 못하고 예외케이스를 찾지 못했다.

- 다 잘되는 데 왜 통과안되는지 모르겠다.

- 한 지점마다 남동쪽, 남서쪽 대각선의 길이를 알아낸뒤, 그 둘의 최솟값(s1)을 가지고 마름모의 가장 밑 꼭지점부터 시작하여

북동쪽 북서쪽 대각선의 길이의 최솟값(s2)과 비교후 s2 < s1이면 사각형이 성립되지 않는 것으로 본다.

import java.util.Scanner;
import java.lang.Math;

class Main {
	static int MAX_Y;
	static int MAX_X;
	static int [][] d = {};
	public static void main (String [] args){
		Scanner sc = new Scanner(System.in);
		MAX_Y = sc.nextInt();
		MAX_X = sc.nextInt();
		String str = "";
		int answer=0;
		int step = 0;
		d = new int [MAX_Y][MAX_X];
		for(int i=0;i<MAX_Y;i++){
			str = sc.next();
			for(int j=0;j<MAX_X;j++){
				d[i][j] = str.charAt(j) - '0';
			}
		}
		for(int i=0;i<MAX_Y;i++){
			for(int j=0;j<MAX_X;j++){
				 step = Math.min(findStep("SOUTH_EAST",i,j),findStep("SOUTH_WEST",i,j));
				 if(answer < step){
				 	if(Math.min(findStep("NORTH_EAST",i+step*2-2,j),findStep("NORTH_WEST",i+step*2-2,j))>=step){
						answer=step;
					}
				 }
			}
		}
		System.out.println(answer);
	}
	public static int findStep(String direction,int y,int x){
		int max_y = y;
		int max_x = x;
		int step=0;
		while(true){
			if(max_x <0 || max_y < 0  || max_y >= MAX_Y || max_x >= MAX_X){
				break;
			}
			if(d[max_y][max_x] == 0){
				break;
			}
			else{
				step++;
			}
			switch (direction){
				case "SOUTH_EAST":
					max_x++;
					max_y++;
					break;
				case "SOUTH_WEST":
					max_x--;
					max_y++;
					break;
				case "NORTH_EAST":
					max_x++;
					max_y--;
					break;
				case "NORTH_WEST":
					max_x--;
					max_y--;
					break;
			}
		}
		return step;
	}
}

 

 

2)

- 막무가내로 풀어보았다. (이것도 물론 fail..)

- 각 사각형의 꼭지점의 위치를 일일이 지정한다음 for 문으로 갯수를 찾아낸다.

import java.util.*;

class Main{
	public static void main(String [] args){
		int R;
		int C;
		Scanner sc = new Scanner(System.in);

	 	R = sc.nextInt();
	 	C = sc.nextInt();
	 	int [][] d = new int[R][C];
	 	int max = 0;
	 	String str="";
	 	boolean flag = true;
	 	boolean flag2 = true;

	 	//size0
	 	for(int i=0;i<d[0].length;i++){
	 		str = sc.next();
	 		for(int j=0;j<d.length;j++){
	 			 d[i][j]= str.charAt(j) - '0';
	 			 if(flag){
	 			 	if(d[i][j] == 1){
	 			 		flag = false;
	 			 		max = 1;
	 			 	}
	 			 }
	 		}
	 	}

	 	if(!flag){
	 		// size1
	 	for(int j=2;j<d.length-2;j++){
	 		for(int i=0;i<d[0].length-4;i++){
	 			if (d[i][j]+d[i+1][j-1]+d[i+2][j-2]+d[i+1][j+1]+d[i+2][j+2]+d[i+4][j]+d[i+3][j-1]+d[i+3][j+1] == 8){
	 				max = 3;
	 				flag2 = false;
	 				break;
	 			}
	 		}
	 	}
	 	// size2
	 	if(flag2){
		 		for(int j=1;j<d.length-1;j++){
		 		for(int i=0;i<d[0].length-2;i++){
		 			if (d[i][j]+d[i+1][j-1]+d[i+1][j+1]+d[i+2][j] == 4){
		 				max = 2;
		 				break;
		 			}
		 		}
		 	}
	 	}
	}	
	 	System.out.println(max);
}
}