[백준][BFS] 20207. 달력

20207. 달력

 

• 내 풀이
  • 떨어진 날들은 따로 계산해야하므로 연속된날의 시작점을 찾아서 start에 저장
  • -> start에서 하나씩 뽑아서 각각 bfs 돌리면서 계산
• 처음) 런타임 에러 오류 -indexError
  •  q+1 파악할때 q+1이 365를 넘어가는지 확인해줘야함

#가장 많이 겹치는 날: 행
#일정이 떨어지지 않으면 열은 길어짐
from collections import deque

#일정 개수
n=int(input())
lst=[0 for _ in range(366)] #0~365 

#겹치는 날은 값이 증가하도록
for i in range(n):
    s, e=map(int,input().split())
    for j in range(s,e+1):
        lst[j]+=1

flag=0
start=[]
#연속된 날 파악
for i in range(366):
    if lst[i]==0:
        flag=0
        continue

    if flag==0 and lst[i]!=0:
        flag=1
        start.append(i)

queue=deque()
def bfs(v):
    global r,c
  
    queue.append(v)
    c+=1
    
    while queue:
        q=queue.popleft()
        r=max(r, lst[q])

        if q+1<=365: #이거 체크안하면 indexError
            if lst[q+1]!=0:
                c+=1
                queue.append(q+1)
                r=max(r, lst[q+1])
    
answer=0
r,c=0,0
for st in start:
    #초기화
    r=0
    c=0
    bfs(st)
  
    answer+= (r*c)

print(answer)