[IT/코딩테스트] 99클럽 코테 스터디12일차 TIL + BOJ1051

 

오늘의 문제

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

 

오늘은 뿌듯하게도 권장 시간 안으로도 풀었고 나 혼자 생각해서 코드를 작성했다🥹

물론 실버3 정도의 문제였지만 그래도 기분 굿👍

 

오늘도 N 과 M 이 50보다 작거나 같은 자연수라는 것에서 완전 탐색이라는 것을 확인.

바로 노트에 아이디어를 적어보았다.

 

---

나의 첫 번째 풀이 (성공)

아래는 문제를 어떻게 풀 것인가에 대해서 생각한 흐름

 

1. 정사각형 이라고 했기 때문에 변의 길이가 핵심

변의 길이는 n, m 둘 중에 더 작거나 같은 값이어야 한다.

 

2. 맨 왼쪽 꼭짓점을 기준으로, 모든 꼭짓점을 변의 길이를 이용해서 표현 필요

* 변의 길이를 s 라고 할 때
r1 = rectangle[i][j] # 정사각형의 왼쪽 위 꼭짓점
r2 = rectangle[i][j+s] # 정사각형의 오른쪽 위 꼭짓점
r3 = rectangle[i+s][j] # 정사각형의 왼쪽 아래 꼭짓점
r4 = rectangle[i+s][j+s] # 정사각형의 오른쪽 아래 꼭짓점

 

3. 변의 길이를 더했을 때, 좌표가 n, m의 최대보다 커지면 안 된다.

맨 왼쪽 꼭짓점의 범위를 n-s, m-s 로 설정하자.
그러면 범위를 넘어가지 않는다.

 

4. for 문으로 변의 길이를 늘려가며 확인 

5. 그 안에 좌표를 이동시키도록 이중 for 문 넣기

6. 좌표에 해당하는 값이 다 같으면 넓이 리스트에 저장

7. 넓이 리스트에서 가장 큰 값 print

 

 

그렇게 작성한 코드를 파이참에서 실행해보았고, 올바르게 동작하는 것을 확인한 후에 백준 사이트에 입력했다.

그리고 결과는 ..... 

 

 

 

작성 전체 코드

import sys

n, m = map(int, sys.stdin.readline().split())
rectangle = []
sizes = []
side = m if n >= m else n

for _ in range(n):
    rectangle.append(sys.stdin.readline().strip())

# 정사각형의 왼쪽 위 꼭짓점 좌표 설정
for s in range(side):
    for i in range(n-s):
        for j in range(m-s):
            r1 = rectangle[i][j] # 왼위
            r2 = rectangle[i][j+s] # 오위
            r3 = rectangle[i+s][j] # 왼아래
            r4 = rectangle[i+s][j+s] # 오아래
            # 만약 r1, r2, r3, r4 의 값이 다 같다면 size = s의 제곱
            if r1 == r2 == r3 == r4:
                sizes.append((s + 1) ** 2)  # 정사각형 넓이 추가

print(max(sizes))

 

 

해결 완료!! 🔥🔥

 

아무래도 완전탐색은 이번주를 통해서 정복할 수 있을 것 같다!

물론 정처기가 제일 급해서 신경을 많이 못쓸 것 같기는 하지만 ㅠ 

 

나에게 가장 필요한 코테 공부는 BFS, DFS 공부라고 생각한다😸

항해 코스 다 끝나고 나서도  BFS, DFS 문제는 꾸준히 풀어야할 것 같다....

 

그리고 오늘 제출로 레벨3 으로 렙업~~👾