[BOJ/Python] 백준 2563 - 색종이

문제

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

 

입력

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다.

 

출력

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

풀이

# 색종이의 수
n = int(input())

# 색종이 위치 입력(좌하단 꼭짓점의 좌표)
li = [list(map(int, input().split())) for _ in range(n)]

# 입력받은 색종이의 위치를 스택에 넣고 꺼내면서 방문 처리
# 1 * 1 칸의 넓이는 1이다

# 방문 리스트 생성
graph = []
for _ in range(101):
    graph.append([0] * 101)

# 스택을 돌면서 방문 처리
while li:
    x, y = li.pop()
    for i in range(10):
        for j in range(10):
            graph[x + i][y + j] = 1

# # 출력 확인하기
# for i in range(100):
#     for j in range(100):
#         print(graph[i][j], end = '')
#     print()

ans = 0
for i in graph:
    ans += sum(i)
print(ans)

    다음을 고려하여 코드를 작성하였다.

1. 좌표평면을 1*1의 정사각형의 집합이라고 생각하고, (1.1)부터 입력받기 위해 가로 101, 세로 101의 맵을 생성한다.
2. 중복에 대한 추가 연산을 피하기 위해 방문 리스트를 생성한다.
3. 입력받은 색종이의 위치(좌하단 꼭짓점)를 스택에 넣고, 하나씩 돌면서 방문 처리를 한다.
   이 때, 가로 10, 세로 10에 해당하는 좌표를 모두 방문 처리한다.
4. 색종이가 붙은 넓이의 합계는 방문 처리된 그래프의 합계이다.