넘치게 채우기

https://www.acmicpc.net/problem/2606BOJ - 바이러스문제 유형: 그래프, 연결 요소, bfs, dfs문제 난이도: Silver III시간 제한: 1초메모리 제한: 128MB 문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때..

https://www.acmicpc.net/problem/6118BOJ - 숨바꼭질문제 유형: bfs, 그래프문제 난이도: Silver I시간 제한: 1초메모리 제한: 256MB 문제재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다. 모든 헛간은 M(1재서기는 발냄새가 지독하기 때문에 최대한 냄새가 안나게 숨을 장소를 찾고자 한다. 냄새는 1번 헛간에서의 거리(여기서 거리라 함은 지나야 하는 길의 최소 개수이다)가 멀어질수록 감소한다고 한다. 재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾을 수 있게 도와주자! 입력첫 번째 줄에는 N과 M이 공백을 사이에..

https://leetcode.com/problems/valid-arrangement-of-pairs/description/leetcode - Valid Arrangement of Pairs문제 유형: 그래프, 오일러 경로, 오일러 회로, dfs문제 난이도: Hard 문제You are given a 0-indexed 2D integer array pairs where pairs[i] = [starti, endi]. An arrangement of pairs is valid if for every index i where 1  endi-1 == starti.Return any valid arrangement of pairs.Note: The inputs will be generated such that t..

https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid/description/leetcode - Minimum Time to Visit a Cell in a Grid문제 유형: 최단 경로, 행렬, 그래프문제 난이도: Hard 문제You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the tim..

https://www.acmicpc.net/problem/1167BOJ - 트리의 지름문제 유형: 최단 거리, 다익스트라, 트리, 그래프, 트리의 지름문제 난이도: Gold II시간 제한: 2초메모리 제한: 512MB 문제트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 ..

https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i/description/leetcode - Shortest Distance After Road Addition Queries I문제 유형: 최단 경로, 그래프, 다익스트라, 다이나믹 프로그래밍문제 난이도: Medium 문제You are given an integer n and a 2D integer array queries.There are n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 queries[i] = [ui..

https://leetcode.com/problems/find-champion-ii/description/leetcode - Find Champion II문제 유형: 그래프문제 난이도: Medium 문제There are n teams numbered from 0 to n - 1 in a tournament; each team is also a node in a DAG.You are given the integer n and a 0-indexed 2D integer array edges of length m representing the DAG, where edges[i] = [ui, vi] indicates that there is a directed edge from team ui to team vi ..

https://www.acmicpc.net/problem/11779BOJ - 최소비용 구하기 2문제 유형: 최단 거리, 다익스트라, 유니온-파인드문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다. 입력첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄..

https://www.acmicpc.net/problem/1865BOJ - 1865 웜홀문제 유형: 최단경로, 플로이드-워셜, 그래프문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였..

https://www.acmicpc.net/problem/1238BOJ - 파티문제 유형: 그래프, 최단경로, 플로이드-워셜문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중..