[SW13732] 정사각형 판정

SW Expert Academy- 정사각형 판정

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AX8BAN1qTwoDFARO&categoryId=AX8BAN1qTwoDFARO&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

문제 입력

5
3
...
.##
.##
4
#..#
....
....
#..#
5
.....
.###.
.###.
.###.
.....
1
#
3
#..
.##
.##

#1 yes
#2 no
#3 yes
#4 yes
#5 no

문제 풀이

import sys

sys.stdin = open('input.txt', 'rt')
T = int(input())  # 테스트 케이스


# 정사각형의 한 변 길이 구하기 (자연수의 제곱인지)
def isSqrt(n, x):
    for i in range(1, n + 1):
        if i * i == x:
            return i
    return 0


# 각 점들이 아래 행과 한 칸만 차이가 나는지
def check(l, idx):
	# 위 아래
    for i in range(l):
        if i + idx < l:
            if abs(loc[i][0] - loc[i + idx][0]) + abs(loc[i][1] - loc[i + idx][1]) != 1:
                return 0
	
    # 좌 우
    for i in range(0, l, idx):
        if abs(loc[i][0] - loc[i + 1][0]) + abs(loc[i][1] - loc[i + 1][1]) != 1:
            return 0
    return 1


# 테스트 케이스 수행
for i in range(T):
    n = int(input())  # 격자판의 크기
    mp = [input() for _ in range(n)]  # 격자판맵
    loc = []  # # 위치 저장

    # '#' 의 인덱스 찾기
    for x in range(n):
        for y in range(n):
            if mp[x][y] == '#':
                loc.append([x, y])

    # 만약 갯수가 자연수의 제곱이라면 - 갯수는 곧 넓이 이므로
    idx = isSqrt(n, len(loc))
    if idx == 1:
        print(f'#{i + 1} yes')
    elif idx and check(len(loc), idx):
        print(f'#{i + 1} yes')
    else:
        print(f'#{i + 1} no')

우선 # 의 인덱스를 다 찾아봅니다.
해당 좌표를 가지고 옆의 칸들과 한 칸 차이만 나는지 살펴봐야 합니다.
또한 총 인덱스의 개수, 즉 넓이가 자연수의 제곱인지도 확인합니다.
18개에서 테스트 케이스가 계속 멈추시는 분들은 #인 것도 정사각형으로 처리를 했는지 확인하시길 바랍니다.

# SW Expert 정사각형 판정 python 알고리즘

---