PS/백준

실버2 색종이 만들기(2630)

2024. 1. 1. 15:52
 

2630번: 색종이 만들기

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.

www.acmicpc.net

분할 정복 공부하면서 이렇게 4개로 나눠지는 형태를 쿼드트리라는 것을 처음 알았다. 이렇게 4분할 해서 재귀를 돌리는 형태의 코드가 많이 나왔다. 

import sys
input = sys.stdin.readline

def divide(r, c, n):
  check, flag = matrix[r][c], True
  for i in range(r, r+n):
    for j in range(c, c+n):
      if check != matrix[i][j]:
        flag = False
        n //= 2
        divide(r, c, n)
        divide(r, c+n, n)
        divide(r+n, c, n)
        divide(r+n, c+n, n)
        return 0
  if flag: result[check] += 1

n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
result = {0:0, 1:0}

divide(0, 0, n)
print(result[0])
print(result[1])

처음에는 각 4분면을 나누고 브루트포스로 검색해서 다르면 또 4분면을 나누어가며 재귀를 나타내는 방법으로 풀려고 했다. 하지만 이런 방법은 아무리 생각해도 너무 비효율적인 코드였다. 그러다 생각해보니 첫번째에 전부 1이거나 0이면 1로 출력해야한다는 것이 생각나서 "전체를 탐색하고 다른게 나오면 4분할 한다"라는 생각으로 구현했다. 그리고 result를 딕셔너리로 구현했고, flag를 세워서 다른게 있으면 증가하지 않게 만들었다. 여기서 가장 중요했던 건 아무래도 return을 하는 것이였다. return을 하지 않아서 자꾸 다른 답이 나오고 계속 탐색을 이어나갔기 때문이다.

'PS > 백준' 카테고리의 다른 글

[백준] 25418 - 정수 a를 k로 만들기  (1) 2024.01.11
[백준] 2583 - 영역 구하기  (0) 2024.01.11
실버1 z(1074)  (1) 2023.12.31
실버3 구간 합 구하기 4(11659)  (0) 2023.12.30
실버3 1로 만들기(1463)  (0) 2023.12.30
'PS/백준' 카테고리의 다른 글
  • [백준] 25418 - 정수 a를 k로 만들기
  • [백준] 2583 - 영역 구하기
  • 실버1 z(1074)
  • 실버3 구간 합 구하기 4(11659)
jjw000628
jjw000628
jjw000628
wldnd2
jjw000628
전체
오늘
어제
  • 분류 전체보기 (27)
    • Skill Up (1)
      • Algorithm Theory (1)
      • Java (0)
      • JS (0)
      • 프로젝트 및 회고 (0)
    • PS (23)
      • 백준 (15)
      • 프로그래머스 (8)
    • Lab (3)
      • Basic Concept (0)
      • 무선 이동 통신 (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • DP
  • 백준
  • 파이썬
  • 깊이우선탐색
  • 분할정복
  • 재귀
  • 브루트포스
  • dfs
  • BFS
  • 프로그래머스
  • 그래프탐색
  • 문자열
  • C++
  • 알고리즘
  • 그래프
  • JS
  • 파싱
  • 무선
  • 너비우선탐색
  • 누적합
  • Cpp
  • 정규식
  • 네트워크

최근 댓글

최근 글

hELLO · Designed By 정상우.
jjw000628
실버2 색종이 만들기(2630)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.