https://school.programmers.co.kr/learn/courses/30/lessons/12905
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이 문제를 처음 접했을때 무조건 bfs혹은 dfs로 풀어야겠다 생각했다.
우선 가장 넓은 범위를 구하기 위해 bfs를 사용했다. 그리고 정사각형을 어떻게해서 찾을 것인지 생각해보았다.
단순이 상하좌우가 1인 것만 찾는다면 "정"사각형을 찾지는 못한다.
그래서 생각해낸 방법이 바로 위, 바로 왼쪽, 왼쪽 대각선이 모두 1인 경우를 정사각형이라 보고 그 왼쪽 대각을 q에 담는다.
아래는 위 생각을 그대로 옮긴 코드이다.
from collections import deque
def solution(board):
answer = 1
def bfs(i, j):
q = deque()
area = 1
q.append((i, j))
while q:
x, y = q.popleft()
nx = x - 1
ny = y - 1
if 0 <= nx < len(board) and 0 <= ny < len(board[0]):
if board[nx][y] == 1 and board[x][ny] == 1:
if board[nx][ny] == 1:
q.append((nx, ny))
area += 1
return area
for i in range(len(board)-1, -1, -1):
for j in range(len(board[0])-1, -1, -1):
if board[i][j] == 1:
area = bfs(i, j)
if area > answer:
answer = area
return answer
print(solution([[0, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [0, 0, 1, 0]]))하지만 테스트 결과 무려 1/3이 실패했다.
이류를 찾기 위해서 머리를 싸맸지만 찾지 못했고 결국 다른 이의 답안을 확인했다.
다른사람들이 주로 쓴 알고리즘은 bfs가 아닌 dp였다.
생각해보니. 조건이 1천개 이하인데 bfs를 먼저 떠올린게 이상했다.
아래는 다른 사람의 코드를 이해하고 나 혼자 작성한 코드이다
def solution(board):
answer = 0
for i in range(1,len(board)):
for j in range(1,len(board[i])):
if board[i][j] == 1:
board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1
for i in board:
mm = max(i)
if answer < mm:
answer = mm
return answer ** 2우선 이중 반복문은 board[1][1]부터 시작한다.
그리고 board[i][j]가 1일때 board[i-1][j], board[i][j-1], board[i-1][j-1] 중에서 최소값을 찾는다.
즉, 바로 위, 왼쪽, 왼쪽 위(왼쪽 대각)에서 최소값에 1을 더한 값을 board[i][j]에 넣는다.
그리하면 정사각형이 아니라면 1이 나오게 되고 정사각형이라면 앞선 값에 +1을 한 값이 되는 것이다.