문제 [Gold I] 다리 만들기 2 - 17472 문제 설명 섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다. 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다. 나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자. 입력 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다 출력 모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든..

1. 문제 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 2. 접근 N의 범위는 3

1. 💎 문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 2. 🤔 접근 구해야 하는 것은 최소 강의실의 수이다. 그러므로 n개의 강의실을 운영하다가 n개의 강의실이 모두 꽉 차있어 새로운 강의를 열 수 없을 때, 강의실을 늘려준다. 1. 우선 순위 큐 사용 n개의 강의실을 운영하기 위해 우선 순위 큐를 사용한다. 왜냐하면 최소의 강의실을 유지하기 위해서는 여러 개의 강의실 중 가장 일찍 끝나는 강의실에 새로운 강의를 배정해야 되기 때문이다. 그러므로 항상 가장 일찍 끝나는 강의실을 찾기 위해 삽입 시 오름차순 정렬을 해주는 우선 순위 큐를 사용한다. 2..

1. 문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net - 주어진 한 정점 부터 각 모든 정점 최소 경로 구하기 2. 해결 포인트 이 문제는 주어진 노드의 제한이 크기 때문에 정점마다 탐색을 진행할 수 없다. 최소 경로 문제에 쓰이는 알고리즘이 필요하다. 한 노드에서 각 모든 노드까지 가는 최단 경로를 구할 수 있는 다익스트라 알고리즘을 쓴다. 다익스트라(Dijkstra) 알고리즘 한 노드에서 각 모든 노드까지 가는 최단 경로를 구하는 알고리즘. 음의 간선을 포함할 수..

1. 📄 문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net - 반드시 3개의 벽을 세워서 확보할 수 있는 안전 구역의 최댓값을 구하기 2. 🤔 어떻게 풀까? 문제를 처음 봤을 때 대체 어떠한 방법으로 벽을 세울 위치를 정해야될지 난감했다. 바이러스를 중심으로 한다해도 어렵고, 벽을 중심으로 해도 어렵고.. 모르겠다가 넉넉한 시간과 작은 N과 M의 개수를 보고 완전 탐색을 생각했다. 그후 과연 시간 조건을 충족할 수 있을지 계산을 해보았고 아주 넉넉했다. 그래서 벽을 세울 수 있는 모든 경우의 수로 벽을 세우고, BFS ..