[Python] 2567번 색종이 - 2

https://www.acmicpc.net/problem/2567

---

 

25/07/30

 

 

도형의 둘레를 구해보자.

---

 

문제 접근 방식:

 

 

여러 방법이 있지만, 결국 스위핑 아이디어로 통일된다.

 

문제에서 요구하는 대로 직사각형의 합집합을 2차원 배열 상에서 표현하는 것은 그리 어렵지 않다.

 

이제 스위핑을 하면 된다. 갑자기 엥 스위핑이 뭐지 싶지만, 그냥 배열 순회하며 쓱 쓸어버리는거라고 생각하면 된다.

 

 

귀찮아서 다 표시는 못했지만, 2차원 배열을 색칠한 후에 행 별로 순회하며 세로 길이를 모두 잴 수 있다.

 

이때 0과 1이 바뀌는 지점, 혹은, 현재 지점과 이전 지점의 값이 서로 다른 경우 경계이므로 이때 세어주면 된다.

 

이렇게 세로 경계를 다 세어주면 가로 경계를 똑같이 세어주면 된다.

 

혹은 다음과 같이 생각할 수도 있다.

 

결국 스위핑 풀이랑 거의 똑같은데, 현재 위치에서 상, 하, 좌, 우 4방향을 보는 것이다. 2방향이 0이면 모서리이므로 2를 추가, 1방향만 0이면 변이라고 생각하고 1을 추가하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2567번 색종이 - 2
# 스위핑
'''
접근 방법:
스위핑 하면서 0과 1이 달라지는 경계를 찾는다.
'''
import sys
input = sys.stdin.readline

def solve(test_case_num):
    M = [[0 for _ in range(105)] for _ in range(105)]
    N = int(input())
    for _ in range(N):
        r, c = map(int, input().split())
        for i in range(r, r+10):
            for j in range(c, c+10):
                M[i][j] = 1
    ans = 0
    for i in range(105):
        for j in range(1, 105):
            if M[i][j] != M[i][j-1]:
                ans += 1
    for j in range(105):
        for i in range(1, 105):
            if M[i][j] != M[i-1][j]:
                ans += 1
    print(ans)
    return

def main():
    T = 1
    for i in range(1, T+1):
        solve(i)
    return

main()