[BOJ][Python]2567번 풀이

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

2567번: 색종이 - 2

import sys
ssr = sys.stdin.readline

t = [[0 for _ in range(101)] for _ in range(101)]
n = int(ssr())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for _ in range(n):
    x,y = map(int, ssr().split())
    ans = 0 
    for i in range(10):
        for j in range(10):
            t[x+i][y+j] = 1
    for i in range(101):
        for j in range(101):
            for k in range(4):
                if t[i][j] == 1 and t[i+dx[k]][j+dy[k]] == 0:
                    ans += 1
print(ans)

개인적으로 진짜 고민 많이 했던 문제입니다. 처음에는 경우를 총 3가지(완전히 겹칠 때, 겹칠 때, 겹쳤는데 내부에 빈공간이 생길 때)로 나눠서 각각 구하려 했습니다. 그러다 보니 모든 색종이가 다 겹쳐서 놓여있지는 않다는 생각이 들었고 해당 이슈를 해결하기 위해 겹쳐있는 그룹끼리 구분할 수 있는 코드를 작성했는데, 문득 굳이 이럴 필요없이 그냥 겹칠 때 마다 해당 부분을 빼주면 되지 않나하는 생각이 들었고, 몇몇 경우에 대해서는 잘 동작을 했습니다. 근데 백준에서는 계속 틀리더라구요. 딱히 질문 탭에 질문도 많이 없어서 혼자서 계속 반례를 생각하면서 풀던 와중에 특정 선이 여러 번 겹치는 경우에 대해서는 제 풀이가 성립하지 않는다는 사실을 깨달았습니다. 그 때 사용했던 반례는 이것입니다.

5

0 0

10 0

0 10

10 10

5 5

답 : 80

제가 풀었던 방식으로는 40이 나왔었고 코드를 살펴보니 5,5에 붙여진 색종이와 겹치는 부분이 이미 그 전에 다 겹쳐지는 부분으로 인식해서 빼주었던 부분들이더라구요. 제가 짜고있던 풀이로는 어떤 선이 여러번 겹치는지를 기억하게할 방법이 없었기 때문에 해당 방법으로 고민을 하고 있다가 풀이를 찾아봤습니다. 배열을 이용해서 다들 푸시더라구요. 약간 머리를 맞은 듯한 느낌이었습니다. 그렇게 하면 굳이 이렇게 귀찮게 할 필요도 없이 배열의 합만 가지고도 문제를 해결할 수 있을 것 같아서 바로 해당 방법을 이용해봤습니다. 결과적으로는 배열의 합만 가지고 구하도록 짜진 않았지만 코드도 훨씬 간결해지고 저 스스로도 이해가 잘됐습니다. 무엇보다 배열로 구하니까 디버깅이 압도적으로 편리했어요. 정말 구현 문제들은 이렇게 번뜩이는 무언가를 항상 요구하는 것 같습니다. 풀 때 마다 느끼지만 참 어려워요.

 

문제 접근은 배열의 탐색입니다. 도화지의 크기가 100X100이므로 101, 101짜리 배열을 선언해줍시다. 그렇게 하고 이차원 배열을 이용해서 입력에 따라 색종이의 위치를 표시해주기 위해 색종이가 붙여지는 좌표를 1로 바꿔줍니다. 그렇게 하면 어딘가는 0이고 어딘가는 1이겠죠. 따라서 전체 도화지를 다 탐색하는 이중반복문을 이용해서 가운데는 1이고 주변은 0인 경우(즉, 색종이의 테두리)를 카운트 해주면 그게 색종이들의 전체 둘레가 되는 것입니다.

 

그래도 다행인 것은 어째서 제가 했던 방법이 해답으로 이어질 수 없는지를 확실히 파악하고 그 단점을 해결할 수 있는 풀이를 찾을 수 있었다는 점이네요. 아무 것도 알아내지 못하고 배열을 이용해 푸는 걸 봤다면 왜 이걸 쓰는지 이해조차 못했겠죠. 고민하느라 시간은 많이 썼지만 성장으로 이어진 것 같아서 기분 좋습니다.