4836. [파이썬 S/W 문제해결 기본] 2일차 - 색칠하기

출처

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

그림과 같이 인덱스가 있는 10x10 격자에 빨간색과 파란색을 칠하려고 한다.

N개의 영역에 대해 왼쪽 위와 오른쪽 아래 모서리 인덱스, 칠할 색상이 주어질 때, 칠이 끝난 후 색이 겹쳐 보라색이 된 칸 수를 구하는 프로그램을 만드시오.

주어진 정보에서 같은 색인 영역은 겹치지 않는다.
 

	0	1	2	3	4	5	6	7	8	9	c
0
1
2
3
4
5
6
7
8
9
r

예를 들어 2개의 색칠 영역을 갖는 위 그림에 대한 색칠 정보이다.

2

2 2 4 4 1  ( [2,2] 부터 [4,4] 까지 color 1 (빨강) 으로 칠한다 )

3 3 6 6 2 ( [3,3] 부터 [6,6] 까지 color 2 (파랑) 으로 칠한다 )

 

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.   ( 1 ≤ T ≤ 50 )

다음 줄부터 테스트케이스의 첫 줄에 칠할 영역의 개수 N이 주어진다. ( 2 ≤ N ≤ 30 )

다음 줄에 왼쪽 위 모서리 인덱스 r1, c1, 오른쪽 아래 모서리 r2, c2와 색상 정보 color가 주어진다. ( 0 ≤ r1, c1, r2, c2 ≤ 9 )

color = 1 (빨강), color = 2 (파랑)

 

[출력]
 

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

입력
3
2
2 2 4 4 1
3 3 6 6 2
3
1 2 3 3 1
3 6 6 8 1
2 3 5 6 2
3
1 4 8 5 1
1 8 3 9 1
3 2 5 8 2

출력
#1 4
#2 5
#3 7

 

Pass 코드

T = int(input())

for t in range(T):
    # 칠할 영역 개수
    N = int(input())

    # 색 1,2의 위치를 저장하는 리스트
    # 리스트 원소는 set() 으로 초기화 : set 은 중복을 허용하지 않는다.
    color_set = [set(), set()]

	# 영역 개수 만큼 반복
    for i in range(N):
        x1, y1, x2, y2, color = map(int, input().split())
        
		# (x1, y1) 부터 (x2, y2) 까지 color에 따라 color_set에 담는 과정
        for x in range(x1, x2+1):
            for y in range(y1, y2+1):
                color_set[color-1].add((x, y))

    # 겹치는 부분만 꺼낸다.
    result = color_set[0] & color_set[1]
    print('#{} {}'.format(t+1, len(result)))

 

해설

color_set = [set(), set()]
color_set[0] : 빨간색
color_set[1] : 파란색


# 첫 번째 영역
(x1, y1) = (2, 2)
(x2, y2) = (4, 4)
color = 1 (빨간색)

# (2, 2) 부터 (4, 4) 까지 color_set[0]에 좌표가 담긴다.
[{(2, 2)}, set()]
[{(2, 3), (2, 2)}, set()]
[{(2, 3), (2, 4), (2, 2)}, set()]
[{(2, 3), (2, 4), (3, 2), (2, 2)}, set()]
[{(2, 4), (2, 3), (3, 3), (2, 2), (3, 2)}, set()]
[{(2, 4), (3, 4), (2, 3), (3, 3), (2, 2), (3, 2)}, set()]
[{(2, 4), (3, 4), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, set()]
[{(2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, set()]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, set()]


# 두 번째 영역
(x1, y1) = (3, 3)
(x2, y2) = (6, 6)
color = 2 (파란색)

# (3, 3) 부터 (6, 6) 까지 color_set[1]에 좌표가 담긴다.
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(3, 3)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(3, 3), (3, 4)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(3, 3), (3, 4), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(3, 3), (3, 4), (3, 5), (3, 6)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(3, 4), (4, 3), (3, 3), (3, 6), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (3, 4), (4, 3), (3, 3), (3, 6), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (3, 4), (4, 3), (4, 5), (3, 3), (3, 6), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (3, 4), (4, 3), (4, 6), (4, 5), (3, 3), (3, 6), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (3, 4), (4, 3), (4, 6), (4, 5), (3, 3), (3, 6), (5, 3), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (3, 4), (4, 3), (5, 4), (4, 6), (4, 5), (3, 3), (3, 6), (5, 3), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (5, 5), (3, 4), (4, 3), (5, 4), (4, 6), (4, 5), (3, 3), (3, 6), (5, 3), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (5, 5), (3, 4), (4, 3), (5, 4), (4, 6), (4, 5), (3, 3), (5, 6), (3, 6), (5, 3), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (5, 5), (3, 4), (4, 3), (5, 4), (4, 6), (4, 5), (3, 3), (5, 6), (3, 6), (5, 3), (6, 3), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (5, 5), (3, 4), (4, 3), (5, 4), (4, 6), (6, 4), (4, 5), (3, 3), (5, 6), (3, 6), (5, 3), (6, 3), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (5, 5), (3, 4), (6, 5), (4, 3), (5, 4), (4, 6), (6, 4), (4, 5), (3, 3), (5, 6), (3, 6), (5, 3), (6, 3), (3, 5)}]
[{(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}, {(4, 4), (5, 5), (3, 4), (6, 5), (4, 3), (5, 4), (4, 6), (6, 6), (6, 4), (4, 5), (3, 3), (5, 6), (3, 6), (5, 3), (6, 3), (3, 5)}]


# 빨간색과 파란색이 둘 다 칠해진 곳을 찾아야함
color_set[0] = {(4, 4), (2, 4), (3, 4), (4, 3), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2)}
color_set[1] = {(4, 4), (5, 5), (3, 4), (6, 5), (4, 3), (5, 4), (4, 6), (6, 6), (6, 4), (4, 5), (3, 3), (5, 6), (3, 6), (5, 3), (6, 3), (3, 5)}
color_set[0] & color_set[1] = {(4, 4), (3, 3), (3, 4), (4, 3)} // 빨간색이 칠해진 좌표와 파란색이 칠해진 좌표의 교집합을 꺼내줌 (겹치는 곳)

답
#1 4