[구현,시뮬레이션] 빗물 - 백준

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

14719번: 빗물

 

문제는 단순 구현 문제였다.

다음과 같이 빗물이 있으면 빗물을 담기게 할 수 있는 양을 구하는 문제인데

예를 들어 위의 검정색을 건물(?)이라고 치면

건물을 구성하는 부분을 1, 하얀색으로 빈 부분을 0이라고 하자. 

 

저 그림을 이중 배열을 통해 나타낼 수 있는데

다음과 같이 나타낼 수 있다.

 

[

  [ 0, 0, 0, 0, 1, 0, 0, 0 ]

  [ 1, 0, 0, 1, 1, 0, 0, 0 ]

  [ 1, 0, 1, 1, 1, 0, 0, 1 ]

  [ 1, 1, 1, 1, 1, 1, 1, 1 ]

]

 

여기서 중요한 부분은 각 노드 별로 빗물을 담을 수 있는 조건은

양 쪽에 1로 막힌 부분이 조건이 된다.

예를 들어 위의 예시에서

저 2번째 idx의 0은 양 쪽이 막혀있어 빗물이 고일 수 있다. 

저런 방식으로 고일 수 있는 경우는 양쪽의 1로 막혀있는 경우이고

한쪽이라도 뚫린 경우는 고일 수 없는 경우다. 

 

우선 본 문제는 처음 판을 구성하는 복잡도 O(row x col)과

고일 수 있는 지를 판단하는 O(row x col x col)로

 

총 시간 복잡도는 O(row x col x col)로 문제를 통과하였다.

다행히 입력이 크지 않아 통과할 수 있었던것 같다.

 

총 코드는 다음과 같다. 

row, col = [int(x) for x in input().split()]

ls = [int(x) for x in input().split()]

### 초기 setting
Total = []
for _ in range(row) :
    Total.append([0]*col)

idx = 0
for e in ls :
    for i in range(e) :
        Total[i][idx] = 1
    idx += 1

cnt = 0

def check(c, lst) :
    if ( c == 0 ) or (c == len(lst)-1) :
        return False
    A = False; B = False;
    dim_idx = c; inc_idx = c;
    #dim_idx -= 1; inc_idx += 1;
    while True :
        if dim_idx < 0 :
            break
        if lst[dim_idx] == 1 :
            A = True
            break
        dim_idx -= 1
    while True :
        if inc_idx > len(lst)-1 :
            break
        if lst[inc_idx] == 1 :
            B = True
            break
        inc_idx += 1

    return (A and B)

for r in range(row) :
    for c in range(col) :
        # 1일 때는 볼 필요가 없지
        if Total[r][c] == 0 :
            if check(c, Total[r]) :
                cnt += 1

print(cnt)