0과 1의 쉼터

풀이 n개의 정점에 대해 최단거리를 전부 구해준 후, 최단거리가 수색범위(m) 이하인 경우에 대해서 정점이 가지는 아이템의 합들의 최댓값을 구하면 된다. n개의 정점에 대해 최단거리를 구하기 위해 Floyd Warshall을 사용했다. n개의 정점에 대한 최단거리를 모두 구한 후, i번째 정점에서 출발해 수색범위 내로 이동할 수 있는 정점이 가지는 아이템의 합을 구하면 된다. n개의 정점에 대해 아이템 합의 최댓값을 출력해주면 된다. 소스코드 소스코드 보기 출처 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net

풀이 N명의 학생들에 대해 각각 자신의 키가 몇 번째 순서인지 알아내는 문제다. 즉, N명의 키 순서에 대한 단방향 그래프에서 탐색하고자 하는 정점에서 출발하거나 도착하는 관계(간선) 에 대해 자신을 제외한 N - 1 명이 포함 되었는지 살피는 문제다. 가중치는 중요하지 않으니 1로 처리해 단순히 연결 여부만 기록하자. Floyd Warshall으로 탐색을 진행하며, 단방향 그래프에서 간접적으로 연결된 간선이 존재한다면 두 가중치의 합은 inf가 아니여야 한다. 동일하게 연결 여부만 1로 기록하자. 위의 과정을 진행했다면, 이제는 단방향 그래프속 자신이 갈수 있거나, 자신에게 올 수 있는 정점들의 갯수를 카운트 해야한다. 자기 자신이 아니면서( u != v ), 자신으로부터 갈수있는 정점이 아니고( gr..

풀이 가중치가 없는 방향 그래프가 주어질 때, 모든 정점 간 연결이 가능한지 아닌지를 탐색 후 인접 행렬 형식으로 표현해주면 된다. Floyd Washall 을 사용해서 풀이했다. 가중치는 없지만, 결국 모든 탐색 가능한 정점에 대해 정점 간 연결이 존재하는 경우 또 다른 정점간의 간접적 연결이 되기 때문이다. 단, 단순히 정점간의 간접적 연결에 대한 유무 판단만 하면 되기에 아래의 조건만 충족한지 살펴보자 소스코드 소스코드 보기 출처 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net

풀이 'Six Degrees of Separations' theory로도 불리는 이론이다. 자신과는 아무 연관성(inf or V) 없는 사람일지라도, 만약 친구가 한 명 이상 있다면(connected), 대부분 6단계(5명의 관계)를 걸쳐 알 수 있게 된다는 이론이다. 즉, 당신이 6단계를 넘어선다면 아싸일 확률이 매우 높... 문제에서 "모든 사람은 친구 관계로 연결되어져 있다." 라고 하여 주어지는 TC에 대한 별도의 예외처리는 없다. Floyd Warshall을 이용해 모든 친구 관계에 대해서 최단 단계를 구해주고, 각각의 유저가 모든 유저간에 대한 단계의 합으로이루어진 집합(step) 속 최솟값의 순번을 구하자. 소스코드 소스코드 보기 출처 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의..