문제

' 2567번 색종이-2 '
https://www.acmicpc.net/problem/2567

풀이

조건

• 101x101 모양의 흰색 도화지 위에 입력값 (x,y)부터 10x10 크기의 색종이를 붙인다.
• 겹쳐진 N개의 도화지는 하나의 색종이 도형으로 생각해서 둘레의 길이를 구해야 한다.
• 색종이가 도화지 밖으로 나가는 경우는 없다.

풀이 순서

• 도화지 영역의 배열을 만든다. 101*101
• 각 색종이의 (x,y)를 입력받아 10*10의 넓이는 다 체크해준다.
• 모든 영역을 순회하면서 그 지점의 4방향을 탐색했을 때 모두 True가 아니라면 둘레값이므로 +1 해준다.

Check point

• range범위를 생각해서 흰색도화지 영역은 101*101로 잡는다.
• 색종이의 영역을 체크할 때 점을 기준으로 하면 x~x+10으로 해주어야겠지만 인덱스로 본다면 x~x+9를 체크해야 한다.
• 모서리와 변의 tmp는 다르다.
• 4방향이 모두 체크 되었다면 영역 안이라는 뜻이다.

코드

Python

N = int(input())
arr=[[False for _ in range(101)] for _ in range(101)]  #가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지
for _ in range(N):
    x,y=map(int,input().split())
    for i in range(x,x+10):  # 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이
        for j in range(y,y+10): # 좌표가 아니라 영역이므로 range는 y~y+9
            arr[j][i] = True  # 색종이 영역 칠하기

total=0  # 둘레값 
dx=[0,0,1,-1]  # 4방향
dy=[1,-1,0,0]
for i in range(101):    # 흰색 도화지에서 색종이 영역 찾기
    for j in range(101):
        if arr[j][i] == True:  # 한점이 1일때
            tmp=0
            for k in range(4):
                if arr[j+dy[k]][i+dx[k]] == True:
                    tmp+=1
            # 그점의 4방향이 모두 1가 아니라면 그점은 둘레값
            if tmp == 3:  # 3방향이 1 라면 변의 길이
                total +=1
            elif tmp == 2: # 2방향이 1 라면 모서리의 길이 -> ㄱ 자 모양 => 가로, 세로 둘다 존재 하므로 +2
                total +=2

print(total)

다른 방법 1

• 영역을 체크해 준 뒤, 한 줄 씩 순회하면서 한 지점의 값이 그 전 지점과 다른 경우 경계선으로 인식해서 둘레값 +1 해준다.

def count(arr):
    cnt = 0
    for lst in arr:
        for i in range(1, len(lst)):
            if lst[i-1]!=lst[i]:  # 현재값과 직전의 값이 다르면 경계선!
                cnt+=1
    return cnt

N = int(input())
arr = [[0]*102 for _ in range(102)]
for _ in range(N):
    # 해당 영역을 1로 표시
    sj, si = map(int, input().split())
    for i in range(si, si+10):
        for j in range(sj, sj+10):
            arr[i][j]=1

arr_t = list(zip(*arr))  # 세로줄 
ans = count(arr) + count(arr_t)  # 가로로 체크 + 세로로 체크
print(ans)

다른 방법 2

N=int(input())
board=[[0]*102 for _ in range(102)] #만약 마지막 좌표쪽에 둘레가 있다면 체크하기 어려우므로 여유를 더주기

for _ in range(N):
    x, y = map(int, input().split())
    # 색종이가 정사각형의 10x10
    for i in range(x, x + 10):
        for j in range(y, y + 10):
            board[i][j] = 1

cnt=0
#바깥영역 0, 안쪽 검은 영역 1 카운트 1 증가 (열 기준으로)
for i in range(1,101):
    for j in range(1,101):
        if board[i][j] == 0 and board[i][j+1]==1:
            cnt+=1
        if board[i][j]==1 and board[i][j+1] ==0:
            cnt+=1
#바깥영역 0, 안쪽 검은 영역 1 카운트 1 증가 (행 기준으로)
for i in range(1,101):
    for j in range(1,101):
        if board[i][j] == 0 and board[i+1][j]==1:
            cnt+=1
        if board[i][j]==1 and board[i+1][j] ==0:
            cnt+=1
print(cnt)

다른 방법 3

N=int(input())
board=[[0]*102 for _ in range(102)] #만약 마지막 좌표쪽에 둘레가 있다면 체크하기 어려우므로 여유를 더주기

for _ in range(N):
    x, y = map(int, input().split())
    # 색종이가 정사각형의 10x10
    for i in range(x, x + 10):
        for j in range(y, y + 10):
            board[i][j] = 1

cnt=0

for i in range(1,101):
    for j in range(1,101):
        #i,j 좌표가 검은 영역이라면 4방탐색을진행해서 흰영역에 도달하면 카운트 1 증가
        if board[i][j] == 1:
            for di,dj in ((0,1),(0,-1),(1,0),(-1,0)):
                ni = i+di
                nj= j+dj
                if board[ni][nj] == 0:
                    cnt +=1
print(cnt)