[SWEA] 13732. 정사각형 판정(Java, D3)

문제

N×N 크기의 격자판이 있다. 각각의 격자는 비어 있거나(‘.’), 막혀 있다(‘#’).

이때, 막혀 있는 칸들이 하나의 정사각형을 이루는지를 판단하는 프로그램을 작성하라.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 격자판의 크기 N (1≤N≤20 이 주어진다. 다음 N개의 줄은 격자판의 배치를 나타내며, 각 줄에는 ‘.’ 또는 ‘#’로만 이루어진 길이가 N인 문자열이 주어진다. 모든 격자판에는 최소 1개 이상의 ‘#’ 칸이 있음이 보장된다.

 

 

입출력 예

 

풀이

1. # 정보 모으기

1. # 개수: 정사각형 한변의 길이를 구하기 위해 
2. # 처음 시작 좌표: 해당 좌표를 기준으로 정사각형 확인할 거임 

 

2. 정사각형 확인하기 

1. # 시작 좌표에서 정사각형의 마지막 좌표가 주어진 격자판 안에 존재할 경우에만 작업 진행
2. # 시작 좌표에서 정사각형의 크기만큼 #가 모두 채워져 있는지 확인 
3. #일 경우, 1번에서 구한 #의 개수에서 -1 진행 
4. #이 아닐 경우 for문 빠져나옴

 

3. 결과값 설정하기

• 2번에서 설정한 #의 개수가 0 이면 yes 출력
• 그 이유는 #의 개수가 0이면 주어진 모든 #이 정사각형을 구성하고 있다고 판단

 

 

 

 

코드

		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();

		for (int tc = 1; tc < 1 + t; tc++) {
			String result = "no";
			int n = sc.nextInt();
			char[][] chSQ = new char[n][n];

			int a = 0, b = 0;
			int shepCount = 0; // # 개수
			boolean start = false, end = false;

			// 입력값 저장
			for (int i = 0; i < n; i++) {
				String str = sc.next();
				for (int j = 0; j < n; j++) {
					char ch = str.charAt(j);
					chSQ[i][j] = ch;
					if (ch == '#') {
						if (!start) {
							a = i;
							b = j;
							start = true;
						}
						shepCount++;
					}
				}
			}

			int len = (int) Math.sqrt(shepCount) - 1;
			if (a + len < n && b + len < n) {
				for (int i = a; i <= a + len; i++) {
					for (int j = b; j <= b + len; j++) {
						if (chSQ[i][j] != '#') {
							end = false;
							break;
						} else {
							shepCount--;
						}
					}
				}
			}

			if (shepCount == 0) {
				result = "yes";
			}

			System.out.println("#" + tc + " " + result);

 

SWEA 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX8BAN1qTwoDFARO

SW Expert Academy