SWEA - 색칠하기 [Python]

 문제

 

 

 문제 상황

 

- 각각 빨간색과 파란색으로 칠해진 부분이 주어지고 이 두 부분이 겹쳐 보라색이 된 부분의 넓이를 구한다.

- 같은 색이 다시 칠해지는 경우 겹쳐지는 색이 의미가 없으므로 반드시 다른 색이 겹쳐져 색이 변한 것을 처리해야한다. (예를 들어, color red = 1, color blue =2 일 때, red를 2번 칠하면 2가 된다고 blue가 되는 것이 아니다.)

 

 해결 전략

 

- 문제의 조건이 색깔이 2개 밖에 없는 점에 주목한다. 1 1 2 같이 색칠이 될 경우는 기존에 1이 있으면 1을 안 칠한다는 조건, 즉 기존 색깔에 다를 경우만 칠한다고 설정할 수 있지만 1 2 1 처럼 칠하면 이미 3인 보라색이 되어버려 여기에 또 1을 더해 4가 된다. 그래서 조건을 3보다 작은 동시에 기존 색깔과 다르다고 주면 이러한 문제를 해결할 수 있다.

 

 코드

 

# 새로운 코드
# 범위가 매우 작으므로 for문을 여러번 중첩할 수 있었다.
# 기존에 비해 조건을 쉽게 정해 쉽게 구현할 수 있었다.
# SWEA 사이트에서는 stack overflow 문제가 발생한다.
# board를 선언할 때에 board = [[0]*10]*10 으로 설정하면 오류가 발생한다.
 
T = int(input()) #testcase의 수
for idx in range(T):
    n = int(input()) #색칠할 수 
    board = [[0]*10 for _ in range(10)]
    # 보라색 칸의 수
    cnt = 0
    # 색칠을 실행
    for c in range(n):
        r1, c1, r2, c2, color = map(int, input().split())
        for i in range(r1, r2+1):
            for j in range(c1, c2+1):
                if board[i][j] != color and board[i][j] < 3:
                    board[i][j] += color
                    if board[i][j] == 3:
                        cnt += 1
    print(f"#{idx+1} {cnt}")
    
 
# 예전 코드
 
# T = int(input()) # testcase
# result = []
# for _ in range(T):
#     board = [[0 for i in range(10)] for j in range(10)] # 색칠할 판 초기화
#     N = int(input()) # 칠할 횟수
#     ctype = [[[] for i in range(10)] for j in range(10)] # 색칠된 색의 종류 
#     mxlen = 0 # 색깔 최대 개수 저장
#     for i in range(N):
#         x1, y1, x2, y2, c = map(int, input().split()) # (x1, y1), (x2, y2) c 색 종류
#         for x in range(x1, x2+1):
#             for y in range(y1, y2+1):
#                 if c not in ctype[x][y] : # 색칠이 되어있지 않을 경우에만 색칠
#                     board[x][y] += c
#                     ctype[x][y].append(c)
#                     if len(ctype[x][y]) > mxlen :
#                         mxlen = len(ctype[x][y])
#     ck = mxlen*(mxlen+1)//2 # 색 종류의 합
#     rlist = [(i,j) for i in range(10) for j in range(10) if board[i][j] == ck]
#     result.append(len(rlist))
# for i in range(T):
#     print("#{} {}".format(i+1, result[i]))
 

 

 

 해설

 

- 범위가 작아 여러 for문을 중첩하였다. 주어지는 r1,c1,r2,c2를 이용하여 조건에 맞는 공간에 색칠을 하고 색칠을 하는 동시에 보라색을 찾는 연산을 넣어 연산의 횟수를 줄인다.

 

 새로 학습한 것 & 실수 

 

- 배열을 초기화할 때에 [[0]*10]*10 으로 초기화하면 안바뀌어야될 부분이 같이 바뀌는 현상이 있었다. list comprehension을 쓰자

 

 

출처 - https://swexpertacademy.com/main/