99클럽 코테 스터디 5일차 TIL, BFS, 그리디

백준 244444번: 알고리즘 수업 - 너비 우선 탐색 1

• BFS
• 어제 DFS 문제보다 쉽다 (큐를 쓰라고 친절하게 설명 되어있다)
• 수도코드가 써있고 언어 연습하라고 있는 문제

넘 빨리 끝나서 챌린지 문제 풀음

---

백준 2457번: 공주님의 정원

• 그리디: 전에 진 꽃보다 빠르거나 같게 피고, 최대한 늦게 지면 됨

날짜 비교를 처음엔 date1 <= date2로만 했는데 여러 번 틀려서 문제를 다시 읽으니..

5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미

문제 제대로 안 읽어서 수학 문제 못 푸는 초딩들 이해 안 갔는데.. 그게 나였다

• 마지막 꽃의 지는 날 > 11월 30일

시간 초과가 나서 sort 하나를 max로, 월/일 if else 비교를 tuple 비교로 바꿨다. 그래도 시간 초과가 나서 input을 readline으로 바꿨다. 쩝

import sys
input = sys.stdin.readline

n = int(input())
flowers = [tuple(map(int, input().split())) for _ in range(n)] # 꽃 하나에 튜플 하나

def find_flowers(flowers):
    end_m, end_d = 3, 1
    flower_n = 0
    while True:
    	# 지기 전에 피는 애들
        flower = [x for x in flowers if ((x[0], x[1]) <= (end_m, end_d))]
        if not flower:
            return 0

        # 가장 늦게 지는 꽃
        start_m, start_d, end_m, end_d = max(flower, key=lambda x: (x[2], x[3]))
        flower_n += 1
        if ((11, 30) < (end_m, end_d)):
            return flower_n
            
        # 지금꺼보다 늦게 피는 애들
        flowers = [x for x in flowers if ((start_m, start_d) < (x[0], x[1]))]

print(find_flowers(flowers))

flowers는 지금 핀 꽃보다 일찍 피기 시작한 꽃을 제외해 탐색 영역을 줄이는 역할이고, flower는 가장 늦게 지는 꽃을 찾기 위한 결과 집합이기 때문에 변수를 따로 쓴다.