빅맥좋아요

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 백준 13549번 숨바꼭질 3을 풀었다. 처음엔 BFS를 사용해서 풀었다가 틀렸다. 간선의 가중치가 다른 경우엔 BFS를 함부로 사용하면 안된다는 것을 알았다. 우선순위 큐를 사용하지 않으면 dist배열 값에 더 큰 비용이 덮어씌어지는 것 같다. 그래서 다익스트라 알고리즘으로 문제를 해결했다. 아래는 전체 코드입니다. #include #include #includ..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 백준 12851번 숨바꼭질 2를 풀었다. BFS문제인데 도착하는 경로의 수까지 계산해야 한다. 목적지에 가장 빨리 도착하는 시간을 minTime에 기록해둔다. 목적지에 도착하는 경로에 대해서 시간이 minTime인지 확인한 후 cnt값을 올린다. BFS 함수가 종료되면 minTime에 동생을 찾는 가장 빠른 시간이 기록되고, cnt에 가장 빠른 시간으로 동생을..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백준 14502번 연구소 문제를 풀었다. 바이러스가 퍼지는 과정은 BFS 알고리즘을 사용했고 안전 영역을 구할 때는 전수 조사를 사용했다. 전수 조사 하는 과정에서 매번 초기화를 잘 해줘야 다음 시행에 영향이 없다. 아래는 전체 코드입니다. #pragma warning(disable:4996) #include #include #include #include #include #include using names..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 백준 1238번 파티 문제를 풀었다. 최단 경로 중에 가장 긴 경로를 구하는 문제다. 입력 N이 최대 1000개라서 플로이드 와샬 알고리즘은 사용할 수 없다. 간선의 가중치에 음수가 없어서 다익스트라 알고리즘을 사용했다. X마을로 갔다가 다시 자신의 마을로 최단 경로를 통해서 돌아오고 이 값을 기록해야한다. 먼저 X마을로부터 다른 마을까지의 최단 경로를 다익스트라 알..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 백준 1613번 역사 문제를 풀었다. 플로이드 와샬 알고리즘을 응용해서 푸는 문제다. 예제를 입력받고 플로이드 와샬 알고리즘을 수행한 후의 dist배열을 살펴보자. dist 1 2 3 4 5 1 0 1 1 2 INF 2 INF 0 1 1 INF 3 INF INF 0 1 INF 4 INF INF INF 0 INF 5 INF INF INF INF 0 dist[i][j]의 값이 INF가 아니라는..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 백준 1916번 최소비용 구하기를 풀었다. 최대 N이 1000이므로 플로이드 와샬로는 풀 수 없다. 그래서 인접리스트를 이용한 다익스트라 알고리즘으로 풀었다. 같은 시작 노드 u와 같은 도착 노드 v에 대해 다른 비용의 입력이 들어 올 수 있다. 예를 들어 2 3 2와 2 3 10이 입력으로 들어 올 수 있다. 그러면 비용이 더 큰 버스에 대해선 연산을 건너 뛰어..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 백준 10159번 저울을 풀었다. 예제 1번의 입력을 넣었을 때 dist 배열이다. dist 1 2 3 4 5 6 1 0 1 2 3 INF INF 2 INF 0 1 2 INF INF 3 INF INF 0 1 INF INF 4 INF INF INF 0 INF INF 5 INF INF INF 1 0 INF 6 INF INF INF 2 1 0 dist[i][j] INF가 아니면..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 백준 1956번 운동을 풀었다. dist[i][i]를 INF로 놓고 플로이드 와샬 알고리즘을 수행하면 i번 노드에서 i번 노드로 가는 최소 비용이 dist[i][i]에 저장된다. 아래는 전체 코드입니다. #include #include #include #include #include #pragma warning(disable:4996) using namespace..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 백준 2458번 키 순서를 풀었다. 먼저 플로이드 와샬 알고리즘으로 전체 노드의 비용을 구한다. 예제 1을 인풋으로 넣었을 때 dist배열이다. 1 2 3 4 5 6 1 0 2 INF 2 1 3 2 INF 0 INF INF INF INF 3 INF 2 0 1 INF 2 4 INF 1 INF 0 INF 1 5 INF 1 INF 1 0 2 6 INF INF INF INF INF 0 그 다음 알아볼 노드..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 백준 11404번 플로이드를 풀었다. 플로이드 와샬 알고리즘을 사용해서 푸는 문제다. 입력받을 때 시작 노드와 도착 노드가 같지만 비용이 다른 버스를 유의해야 한다. 출력할 때 dist배열에 INF로 정한 값이 있다면 갈 수 있는 경로가 없는 것이므로 0으로 바꿔줘야 한다. 아래는 전체 코드입니다. #include #include #include #include #include using name..