[파이썬/python] 백준 - 3095 플러스의 개수

문제

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

---

문제 설명

1. 0과 1로 이루어진 N*N 행렬이 주어진다.
2. 행렬에 플러스가 몇 개가 존재하는지 구해야 한다.
   1. 플러스는 변의 길이가 1보다 큰 홀수인 정사각형이다.
   2. 가운데 행과 열은 1로, 나머지는 0으로 이루어져 있다.

 

---

풀이

단순 브루트포스 문제라 쉬울거라고 예상했는데, 시간초과가 발생해서 코드를 최적화 하느라 문제 풀이 시간이 좀 더 지연됐다.

 

N의 최대 크기는 2000이기 때문에 브루트포스로 충분히 풀이가 가능하다고 생각하고 빠르게 코드를 작성했다.

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(int,input().strip())) for _ in range(N)]

dr = [0,1,0,-1]
dc = [1,0,-1,0]


def isPlus(r,c,l):
    for i in range(4):
        nr = r + dr[i]*l
        nc = c + dc[i]*l

        if nr < 0 or nr > N-1 or nc < 0 or nc > N-1 or not board[nr][nc]:
            return 0
    
    for nr in range(r-l,r+l+1):
        if nr == r:
            continue

        for nc in range(c-l,c+l+1):
            if nc == c:
                continue
            if board[nr][nc] == 1:
                return 0
        
    return 1

res = 0
for r in range(N):
    for c in range(N):
        if board[r][c] == 1:
            l = 1

            while isPlus(r,c,l):
                res += 1
                l += 1

print(res)

 

브루트포스를 통해 최초로 작성한 코드다.

 

행렬을 완전 탐색하면서 1을 발견하면 해당 위치부터 플러스 모양을 검사하고, 그만큼의 정사각형에서 0들을 검사했다.

위 사진처럼 정사각형 단위로 검사를 진행하다 보니 플러스가 커질때마다 내부 범위를 중복해서 탐색하는 경우가 발생했다.

 

중복 구간이 늘어나면서 이 코드는 시간초과가 발생했고, 시간 복잡도를 줄이고자 탐색 방식을 변경했다.

 

먼저 어떻게 탐색할지 구간을 분리했다.

1. 플러스 모양 탐색
2. 플러스 정사각형의 각 4개의 모서리 탐색
3. 1,2를 제외한 나머지 0 탐색

이렇게 3 구간으로 분리해서 탐색하면 코드는 좀 복잡해도 중복 탐색을 전부 제거할 수 있으니 시간을 최소한으로 줄일 수 있다.

 

 

 

---

코드

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(int,input().strip())) for _ in range(N)]

dr = [0,1,0,-1]
dc = [1,0,-1,0]
dr2 = [1,1,-1,-1]
dc2 = [-1,1,-1,1]


def isPlus(r,c,l):


    for i in range(4):
        nr = r + dr[i]*l
        nc = c + dc[i]*l

        #플러스 검사
        if nr < 0 or nr > N-1 or nc < 0 or nc > N-1 or not board[nr][nc]:
            return 0
        
        nnr = r + dr2[i]*l
        nnc = c + dc2[i]*l

        #모서리 0 검사
        if nnr < 0 or nnr > N-1 or nnc < 0 or nnc > N-1 or board[nnr][nnc]:
            return 0

    #네모 박스 0 검사
    for nr in [r-l, r+l]:
        for i in range(1,l):
            if board[nr][c-i] or board[nr][c+i]:
                return 0
            
    for nc in [c-l, c+l]:
        for i in range(1,l):
            if board[r-i][nc] or board[r+i][nc]:
                return 0
        
    return 1

res = 0
for r in range(N):
    for c in range(N):
        if board[r][c] == 1:
            l = 1

            while isPlus(r,c,l):
                res += 1
                l += 1

print(res)

---

시간복잡도

• 최악의 경우 행렬의 모든 범위를 탐색하게 되므로 $O(N^2) = O(4*10^6)$
  • N은 최악의 경우 2000이다.