백준[2513] 통학버스 (Python3)
2023 카카오 코테 2번? 하고 똑같다. 코테에서도 무난하게 풀어서 그런지, 생각보다 큰 어려움은 없었다. 지문을 분석해 보면, 버스는 가장 먼 거리에 있는 아이들을 우선으로 태우는 것이 유리하다. 또한, 버스 정원을 다 채우기 위해 왼쪽 오른쪽 왔다 갔다 할 필요가 없다. 학교를 기준으로 왼쪽, 오른쪽에 대한 큐 2개를 만들었다. 단지의 위치가 학교보다 왼쪽에 있다면, (학교 위치 - 단지 위치, 학생 수) 형태로 넣고 학교보다 오른쪽에 있다면, (단지 위치 - 학교 위치, 학생 수) 형태로 넣는다. 그 후 위치 값을 기준으로 정렬한다. 그 후, 단지의 학생 수와 버스 정원을 비교해, 다 태울 수 있다면, 해당 단지에 대한 정보를 pop 하고, 다 태우지 못하면 남은 정원만큼 학생 수를 차감하는 식으..
백준[17616] 등수 찾기 (Python3)
전형적인 그래프 탐색 문제를 응용했다. 이 문제에서 주목할 점은, 정점 X와 뒤, 앞으로 연결된 정점 개수를 파악하는 것이다. 즉, bfs를 두 번 돌려야 한다. 예제 3을 기준으로 보면 우리가 보려는 노드는 정점 1이니, 이 기준으로 본다면 정점 1과 3이 연결돼있고, 3은 4, 5와 연결돼있으니, 정점 1의 뒤엔 3, 4, 5가 있다. 정리하면, 정점1의 뒤에 있는 정점 개수는 3고, 앞에 있는 정점 개수는 0개다. 반면, 정점 2는 정점 1과 어떤 방향으로 연결돼있는지 알 수 없다. 정점 3보다 앞에 있단 것만 알지, 정점 1의 어느쪽에 연결돼는지를 알 수 없다. 다행인건 문제에서 가능한 등수의 최소, 최대만 구하는 것이기 때문에, 애매한 정점들은 하나의 경우에 묶어 생각할 수 있다. 1. 정점 1..