백준 알고리즘 2630[파이썬]

 

문제

 

문제풀이

스스로 짠 코드

from sys import stdin
read = stdin.readline
N = int(read())
lst = []
for _ in range(N):
  lst.append(list(map(int, read().split())))

def conqure(n, lst):
  # 이중 리스트안에 1이 없으면 조건충족
  if not any(1 in i for i in lst):
    # 함수안에서 전역변수값을 가지고 쓸 때 전역변수 값을 변형시킬려면 global을 써야한다.
    lst_cnt.append(0)
    return
  # 이중 리스트안에 0이 없으면 조건충족
  elif not any(0 in i for i in lst):
    lst_cnt.append(1)
    return
  else:
    lst_0 = []
    lst_1 = []
    for i in lst:
      lst_0.append(i[:n//2])
      lst_1.append(i[n//2:])
    conqure(n//2, lst_0[:n//2])  
    conqure(n//2, lst_0[n//2:]) 
    conqure(n//2, lst_1[n//2:]) 
    conqure(n//2, lst_1[:n//2])
    return


lst_cnt = []
conqure(N, lst)
print(lst_cnt.count(0))
print(lst_cnt.count(1))

 

def conqure(n, lst): 안에 코드를 순서대로 설명해 보겠습니다.

 

if not any(1 in i for i in lst)

any(1 in i for i in lst)를 쓴 이유는 any()라는 함수는 안에 조건이 성립하면 True를 반환하고 아니면 False를 반환합니다. 그래서 만약에 lst에 1이 없다면 False를 반환하고 if not으로 되어있기 때문에 if 구문을 충족합니다. lst에 1이 없다는건 리스트에 0밖에 없다는 것이고 더이상 분할을 할 필요가 없다는 뜻입니다.

 

lst_0 = []
lst_1 = []
for i in lst:
  lst_0.append(i[:n//2])
  lst_1.append(i[n//2:])
conqure(n//2, lst_0[:n//2])  
conqure(n//2, lst_0[n//2:]) 
conqure(n//2, lst_1[n//2:]) 
conqure(n//2, lst_1[:n//2])

여기 위에 있는 코드는 lst를 4분할하는 코드입니다. for loop을 돌려서 lst를 반반씩 lst_0과 lst_1에 넣어주었습니다.

 

그 다음에 lst_0과 lst_1을 반반으로 나누고 재귀함수에 넣어서 분할된 색종이가 1이나 0만 가지고 있을 때까지 함수가 계속 실행되게 했습니다.

 

원래 cnt = 0을 전역변수로 놓고 함수안에다가 global을 쓰고 cnt 수를 높이면서 사용했는데, global을 쓰면 않좋다는 이야기를 들어서 lst_cnt라는 리스트를 만들어서 거기안에다가 0과 1을 넣고 count를 했습니다.

 

제가 짠 코드는 다른분들이 푼 방식과 다른데, 제 코드에서는 lst말고 lst_0과 lst_1을 따로 두개 더 만들어서 메모리적으로 비효율적일 수도 있다고 했습니다. 분할정복 문제를 풀 때는 주어진 하나의 리스트로 문제를 해결하는게 제일 좋다고합니다.

 

 

 

---

다른 사람이 짠 코드

import sys
read = sys.stdin.readline
N = int(read())
lst = [list(map(int, read().split())) for _ in range(N)]

result = []
# 좌표값을 놓고 for loop을 돌려서 푼다.
def divide(x, y, N):
  color = lst[x][y]
  for i in range(x, x+N):
    for j in range(y, y+N):
      if color != lst[i][j]:
        divide(x, y+N//2, N//2)
        divide(x+N//2, y, N//2)
        divide(x+N//2, y+N//2, N//2)
        divide(x, y, N//2)
        return
  if color == 0:
    result.append(0)
  else:
    result.append(1)


divide(0,0,N)
print(result.count(0))
print(result.count(1))

 

color = lst[x][y]
for i in range(x, x+N):
	for j in range(y, y+N):
		if color != lst[i][j]:

여기서 color는 색종이의 처음 시작 좌표입니다. 분할되지 않은 색종이의 시작 좌표는 (0, 0)이기 때문에 

color값은 위에 사진을 참고하면 1이 될것입니다. 

 

이제 for loop을 두번 돌려서 색종이 안에 모든 좌표값을 돌아보면서 color값과 같은지 확인할것입니다.

확인 했을 때 color값과 다르면 바로 색종이 분할을 시작합니다.

for loop에서 range(x, x+N)을 하는 이유는 색종이가 분할 된후에도 이 for loop을 사용하기 때문에 range(0, N)아니라 range(x, x+N)을 사용해야 합니다.

 

divide(x, y+N//2, N//2)
divide(x+N//2, y, N//2)
divide(x+N//2, y+N//2, N//2)
divide(x, y, N//2)

재귀함수를 사용을 했는데, 매게변수를 보면 4등분 되었을 때 각 색종이의 시작점들로 좌표값을 설정했습니다.(위에 사진을 참고하세요.) 그리고 색종이의 변의 길이가 반으로 줄어들기 때문에 N//2로 해줘야합니다.