색종이 만들기[백준 2630] - python

 

 

import sys 
input = sys.stdin.readline

def BOJ2630() :
  global N
  global graph
  global white
  global blue

  N = int(input())
  graph = []
  white = 0
  blue = 0


  def dfs(x, y, length) :
    global N
    global graph
    global white
    global blue 

    flag = True

    for i in range(x, x + length) :
      for j in range(y, y + length) :
        if graph[x][y] != graph[i][j] and visited[i][j] == False and flag:
          flag = False
          break
    
    if flag :
      for i in range(x, x + length):
        for j in range(y, y + length):
          visited[i][j] = True
      if graph[x][y] == 0 :
        white += 1
      else :
        blue += 1

  for _ in range(N) : 
    graph.append(list(map(int, input().split())))
  visited = [[False for _ in range(N)] for _ in range(N)]
  
  length = N
  while length >= 1 :
    for i in range(0, N, length) :
      for j in range(0, N, length) :
        if visited[i][j] == False :
          dfs(i, j, length)
    length //= 2

  print(white)
  print(blue)
BOJ2630()

 

접근 방법 :

1. 방문배열과 입력배열을 선언해주었다(다른 분들의 풀이를 보면 방문 배열은 굳이 필요없어 보인다)

2. 변의 길이를 2씩 나누어 주면서 1이 될때까지 계속 탐구를 하게 해주었다.

 

장애물 이였던 것 :

1. 아직 python 내에서 global을 쓰는게 익숙치 않다. 공부한번 해야겠다

2. 코드의 짜임새나 로직이 만족스럽지 못하다. 다른 분들의 코드를 참고해 봐야겠다.

 

 

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

2630번: 색종이 만들기