[파이썬/python] 백준 - 31462 삼각 초콜릿 포장 (Sweet)

문제

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

---

문제 설명

1. 정육각형 3개를 삼각형 모양으로 붙인 초콜릿을 판매하려고 한다.
2. 같은 크기의 정육각형 $N(N+1)/2$개를 삼각형 모양으로 붙인 형태의 틀에 이 초콜릿들을 넣어 포장하려고 한다.
3. 위로 뾰족한 방향으로 배치된 초콜릿은 빨간색, 반대 방향의 초콜릿은 파란색으로 개별 포장한다.
4. 완성된 상품이 제대로 포장되었는지 판별한다.

 

---

풀이

위로 뾰족한 방향으로 배치된 초콜릿은 빨간색, 반대 방향의 초콜릿은 파란색으로 개별 포장한다.

-> 이 말이 무슨 의미인지부터 이해해 보자.

문제에 나와있는 예시 이미지이다. R은 빨간색, B는 파란색 초콜릿이다.

R은 위가 뾰족한 형태, B는 아래가 뾰족한 형태의 삼각형을 이루기 때문에 이러한 구조가 반복되어 포장되어야 알맞은 포장이다.

 

따라서 완전탐색을 통해서 빨간색 삼각형과 파란색 삼각형을 찾아서 해당 위치를 방문처리하며 탐색했다.

 

빨간색 초콜릿

가장 하단의 두 개의 이어진 빨간 초콜릿을 탐색한 후 바로 위에 빨간색이 존재하는지 검사한다.

이때 삼각형의 모양이 만들어지지 못한다면 바로 0을 출력하고 프로그램을 종료했다.

 

파란색 초콜릿

하단에 1개의 파란 초콜릿을 탐색하면 상단에 이어진 두 개의 초콜릿이 존재하는지 검사한다.

마찬가지로 삼각형의 모양이 만들어지지 못한다면 바로 0을 출력하고 프로그램을 종료했다.

 

문제의 조건만  만족한 상태로 완전탐색을 하면 결과를 확인할 수 있다. 문제의 N 범위는 5000이므로 시간복잡도 또한 약 $O(25*10^6) =$ 약 $O(10^7)$정도로 아슬아슬하지만 탐색이 가능했다.

 

문제의 핵심은 조건분기를 할 때 인덱스의 범위를 넘어가지 않도록 하는 것과 캐싱을 통해 방문 처리를 해야 한다는 점이라고 생각했다.

 

문제를 보자마자 브루트포스를 생각하고 완전탐색을 돌렸는데 조건분기가 너무 길어져 스스로 코드를 약간 의심했지만 다행히 정답이었다. 

 

 

-> 상위권 사람들의 코드를 보니 나보다 3배 정도의 시간이 빨라서 뭐가 차이인지 살펴봤다.

여러 가지 이유가 존재했는데 방문처리를 단순 정수 배열이 아니라 비트마스킹으로 처리한 것,

조건 분기를 할 때 길게 늘어트리지 않고 나누어서 세세한 예외처리를 진행한 것 정도였다.

 

사실 평소 알고리즘을 풀 때는 크게 영향을 미치지 않을 것 같다고 생각하긴 하는데, 시간이 엄청 빡빡한 문제에서는 이런 최적화 기법으로 도움을 받을 수 있을 것 같으니 기억해 놓아야겠다.

 

---

코드

import sys
input = sys.stdin.readline

n = int(input())

arr = [list(input().strip()) for _ in range(n)]
if n == 1:
    print(0)
    exit()
    
visited = []
for i in range(1,n+1):
    visited.append([0]*i)

for r in range(n-1,0,-1):
    for c in range(len(arr[r])):
        if visited[r][c]:
            continue
        #블루 제거
        if 0 < c < len(arr[r])-1 and arr[r][c] == 'B' and not visited[r][c]:
            if not visited[r-1][c-1] and not visited[r-1][c] and arr[r-1][c-1] == 'B' and arr[r-1][c] == 'B':
                visited[r][c], visited[r-1][c-1], visited[r-1][c] = 2,2,2
            else:
                print(0)
                exit()
        #레드 제거
        elif c+1 < len(arr[r]) and not visited[r][c] and arr[r][c] == 'R' and not visited[r][c+1]  and arr[r][c+1] == 'R':
            if not visited[r-1][c] and arr[r-1][c] == 'R':
                visited[r][c], visited[r][c+1], visited[r-1][c] = 1,1,1
        else:
            print(0)
            exit()

print(1)

---

시간복잡도

• 최악의 경우 $N = 5000$이므로 $O(N(N+1)/2)$일 때 약 $O(10^7)$의 시간복잡도가 소요된다고 볼 수 있다.