[맛있는물회] <SWEA알고리즘> 4836 "색칠하기"

문제 조건

---

 

Input

---

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

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

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

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

 

Output

---

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

 

생각한 아이디어

---

처음에는 일반적인 좌표평면을 생각해서 한참 고민했다. 예제를 넣었는데도 겹치는 부분이 없었다.

계속 다시 읽어보면서 친구와 논의해보니 일반 좌표평면처럼 겹치는 부분을 의미하는 것이 아니라 하나의 사각형이다. 즉, 점이 아니라 칸을 의미하는 것!

그렇게 하니 간단하게 풀릴 줄 알았다...

근데.. 어떤 방식으로 빨강과 파랑이 겹치는지 케이스를 나누려고 했다. 그랬더니 엄청 많은 케이스가 나오는 것이다.

아무리 생각해도 너무 복잡해서 다른 분의 아이디어를 조금 참조 했다.

 

좌표 즉, 점 부분을 List로 만들어서 Red와 Blue 두개의 좌표 리스트를 만드는 것이다. 그리고 2중 포문을 통하여 겹치는 횟수를 구한다!!

아주 아주 스마트한 접근이다. 

예를 들어(x,y) = (1,2) 인 점과 (2,4)의 점이 Red이면 Red = [(1,2), (2,4)...] 이런식으로 좌표평면의 리스트를 만든다.

이렇게 접근하니 아주 간단하게 문제가 풀렸다. 

 

소스코드

T = int(input())
for TC in range(1, T+1):
    N = int(input())
    red = list()
    blue = list()
    cnt = 0
    for i in range(N):
        x1,y1,x2,y2,color = map(int,input().split())
        for x in range(x1, x2+1):
            for y in range(y1,y2+1):
                if color == 1:#red
                    red.append((x,y))
                else:
                    blue.append((x,y))
    
    for i in range(len(red)):
        for j in range(len(blue)):
            if red[i][0] == blue[j][0] and red[i][1] == blue[j][1] :
                cnt += 1

    print("#%d %d" %(TC, cnt))

 

*파이썬 문법 정리

- 파이썬에는 &&, || 와 같은 연산자가 없다. and, or로 사용한다. 아주 직관적이다.