어흥

문제 링크: https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 1. 주의할 점 - 매 쿼리마다 통행을 바꿔야하는 횟수를 구하지 않는다 2. 구현 - Arr[][] 배열을 통해 간선에 대한 정보를 받으며, Arr[a][b]는 a->b로 가기 위해 바꿔야 하는 도로의 수를 저장한다 - Arr[][] 배열을 초기화하고, 입력받을 때 단방향인 경우에는 0,1을 저장하고 양방향인 경우에는 0,0을 저장한다 - 플로이드 와샬 알고리즘을 통해 Arr[][]..

문제 링크: https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 1. 주의할 점 - 최단경로에 사용되는 간선인지 아닌지 구분이 필요하다 - 최단경로 알고리즘에 대해 알고 있어야 한다 2. 구현 - 모든 그래프의 경로를 알기 위해 Arr[][] 배열을 생성과 초기화한다 - 최단경로가 저장된 값을 Result[][] 배열에 저장한다 - Result[][] 배열에 입력된 간선들에 대한 정보를(중복 제외) 우선순위큐에 저장한다(가중치의 오름차순으로 정..

문제 링크: https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 1. 주의할 점 - 초기화 작업을 거친다 - 다익스트라나 플로이드와샬 알고리즘에 대해 알고 있으면 해결할 수 있다(Tree라서 DFS도 간단히 가능) import java.util.*; import java.lang.*; import java.io.*; class Main { static final int MAX = 987654321; static int node,query; public static void main (Strin..

문제 링크: programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 더보기 0. 유사 문제 www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 1. 주의할 점 - 순위가 정해져 있는 조건은? 2. 구현 - 순위가 정해져 있는 경우: 전체 N명에서 현재 위치에서 자기 앞에 A명, 자기 뒤에 B명이 있다면 A+B = N-1인 경우다(자기자신 제외) - 위의 경우를 어떻게 찾을 것인가? → 플로이드 와샬(다익스트라를..

문제 링크: www.acmicpc.net/problem/6059 6059번: Pasture Walking The N cows (2 b>>val; arr[a][b]=val; arr[b][a]=val; } floyd(); for(int i=0;i>a>>b; cout

문제 링크: www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 1. 주의할 점 - 다익스트라 혹은 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 모든 간선에 대한 정보를 TC마다 초기화한다 - 간선에 대한 정보를 Arr[][] 배열에 입력받는다 - floydWarshall() 함수를 통해 각 노드사이의 최단거리를 구한다 - 친구들이 위치한 방을 V벡터에 받은 후, 1~Node번방까지 모두 모임의 방이라고 가정하며 모임방↔친구들이 위치한 방까지의..

문제 링크: www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 1. 주의할 점 - 다익스트라나 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 플로이드 와샬 알고리즘(시간복잡도: O(N^3)로 50^3 < 10^9)을 사용하여 구한다 - 간선들의 정보를 입력 받기 전, Dist[][] 배열을 1000으로 초기화한다 - 간선들의 정보를 입력받은 후, 플로이드 와샬을 통해 IJ 까지의 최소 간선 수를 구한다 - 1~N번까지의 사람들 중에서 가장 먼 ..

문제 링크: www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 1. 주의할 점 - 다익스트라나 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 각 Node마다 보유한 아이템의 수를 Item[] 배열에 담는다 - 플로이드 와샬 알고리즘을 사용하기 위해 Arr[][] 배열을 미리 초기화한다 - 간선이 주어진 경우, Arr[][]에 대입한다 - 플로이드 와샬 알고리즘을 수행한 후, 각 지점마다 수색범위 D를 넘지 않을 경우, Temp에 해당 지역이 보유한 ..