[백준] 2730번 색종이 만들기 파이썬 정답 코드

2630번: 색종이 만들기

---

1. 문제 내용

 

 

2. 접근 방식

• 제 1, 2, 3, 4사분면으로 나뉘는 프렉탈 구조

데이터 리스트에서 0과 1이 모두 존재한다면, 해당 데이터 리스트를 4개의 사분면으로 나누어 각각 재귀 함수를 호출한다. 이때 사분면은 중간 인덱스 i를 기준으로 나누면 된다.

데이터 리스트가 0 또는 1로만 이루어져 있다면 각 개수를 세는 count 변수에 +1 한다.

 

 

3. 정답 코드

• divide( ) : data의 제 quadrant사분면을 구한다.
• find( ) : data에서 0 또는 1 (= n)을 찾는다.
  • 리스트의 index( ) 내장 메서드는 리스트에 없는 값을 찾으려고 할 경우 에러를 리턴하기 때문에 사용할 수 없다.

def divide(data, quadrant):
    i = len(data) // 2
    tmp = []
    if quadrant == 1:
        for row in data[:i]:
            tmp.append(row[i:])
    elif quadrant == 2:
        for row in data[:i]:
            tmp.append(row[:i])
    elif quadrant == 3:
        for row in data[i:]:
            tmp.append(row[:i])
    elif quadrant == 4:
        for row in data[i:]:
            tmp.append(row[i:])
    return tmp


def find(data, n):
    flag = 0
    for row in data:
        for e in row:
            if e == n:
                flag = 1
                break
        if flag == 1 : break
    return flag


def recursive(data, count):
    if find(data, 0) and find(data, 1): # 0과 1이 모두 있을 때
        # quadrant 1
        recursive(divide(data, 1), count)
        # quadrant 2
        recursive(divide(data, 2), count)
        # quadrant 3
        recursive(divide(data, 3), count)
        # quadrant 4
        recursive(divide(data, 4), count)
        return count

    elif find(data, 0): # 0으로만 이루어졌을 때
        count[0] += 1
        return count

    elif find(data, 1): # 1로만 이루어졌을 때
        count[1] += 1
        return count

# main
n = int(input())
data = []
for i in range(n) :
    data.append(list(map(int, input().split())))

answer = recursive(data, [0, 0])
print(answer[0])
print(answer[1])

 

 

4. 기타

def find(data, n):
    flag = 0
    for e in data[0]:
        if e == n:
            flag = 1
            break
    return flag

처음에 제출한 코드에서 find( ) 메서드가 위와 같았다. data의 첫 번째 행만 검사, 즉 한 변을 대상으로만 검사를 진행했다. 문제의 테스트 케이스는 통과하지만, 위 코드로 제출하면 틀렸다고 나온다.

data2 = [[0, 0, 0, 0],
         [1, 1, 1, 1],
         [1, 1, 1, 1],
         [1, 1, 1, 1]
         ]

위와 같은 데이터가 주어지면 결과가 1 0이 나온다. 그러나 정답은 4, 6이어야 한다. 이런 결과가 나온 이유는 한 변만을 대상으로 했기 때문이었다. 0과 1로 이루어진 정사각형을 제대로 검사하려면 한 변이 아니라, 전체를 검사해야 한다. 따라서 최종 3. 정답 코드에서처럼 find( ) 함수를 2차원 리스트 data 전체를 검사하도록 수정하였다.

 

나름 n = 4일 때, n = 2일때의 테스트 케이스를 만들어 보고 검사하였는데도, data2 같은 테스트 케이스를 고려하지 못하였다. 아무 테스트 케이스가 아닌, 오류가 발생할 가능성이 높은 결정적인 테스트 케이스를 잘 설계하는 능력을 키워야겠다.