전체 글

문제 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 다익스트라에 경로 추적을 결합한 문제이다. 처음 문제를 읽었을 때, 최소 스패닝 트리 문제인줄 알았지만 최소 스패닝 트리로 접근할 경우 문제의 두번째 조건이 만족하지 않는다는 것을 알았다. 최소 스패닝 트리로 네트워크를 만들었을 때는 그래프의 가중치의 합이 최소인 그래프가 만들어지지, 최단 경로로 그래프를 만들어 주지는 않을 수 있다. 그러므로, 다익스트라로 접근하였고 필요한 것은 최단 거리가 아니라 연결된 간선이 필요하므로..

Network Role 내가 클라이언트라면 나의 클라이언트 머신 상에 내가 컨트롤하고 있는 폰이 존재한다. 그와 동시에 서버에도 이 폰이 있다. 여기서 다른 클라이언트도 서버에 연결되어 있다면, 그 클라이언트의 머신에도 이 폰이 존재한다. 즉, 현재 세 명이 게임에 들어와 있다면, 내 폰은 세 개가 각각의 머신에 존재한다. 이제 어떤 버전의 폰을 코드로 다룰 것인지가 중요해진다. 이런 점을 해결하기 위해, 언리얼 엔진은 ENetRole이라는 enum으로 Role이라는 개념이 있다. 캐릭터나 폰에 부여된 이 enum으로 Role을 식별할 수 있다. ENetRole::ROLE_Authority 서버 머신에 존재하는 폰의 Role이다. 언리얼 엔진은 authoritative 서버 모델을 사용하기에, 서버에 존..

문제 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 다익스트라에 경로 추적을 결합한 문제이다. 출력 시, 각 집하장에서 다른 집하장까지의 최단 경로가 필요하므로 각 집하장마다 다익스트라를 실행해야 한다. 다익스트라 도중에 최단 경로가 갱신될 때, 현재 노드의 부모 노드를 갱신한다. next_node를 최단 경로로 도달하기 위해서는 current_node애서부터 와야 한다. 부모 노드를 추적하면 한 집하장에서 다른 집하장으로 최단 경로로 갈 때, 바로 다음 집하장을 알 수 있다. 코드 #include #inclu..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 풀이 다익스트라 문제이다. 도로를 하나의 그래프로 생각하는데 주목한다. 그래프의 노드는 바로 다음 노드와 거리가 1로 연결되어 있다. 위의 그래프에서 입력 받은 지름길을 추가한다. 역주행 할 수 없으므로, 지름길의 끝이 D를 넘어간다면 그래프에 추가하지 않는다. 지름길의 거리가 시작과 끝의 거리보다 길다면, 거리를 줄일 수 없으므로 그래프에 추가하지 않는다. 그래프를 0에서부터 다익스트라를 통해 D까지의 최소 거리를 구한다. 코드 #include..

문제 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 다익스트라 문제이다. 첫 시도에는 s를 시작점으로 다익스트라를 한번 실시하고, 경로를 추적하여 시도하였지만, 메모리 초과가 발생하였다. 그리고 이 방법은 x까지의 최단 경로가 여러 개 존재할 경우, 답이 올바르지 않을 수 있다. s, g, h를 시작점으로 다익스트라를 세번 실시한다. s -> g -> h -> x로 가는 최단 경로의 비용이 s -> x로 가는 최소 경로의 비용과 일치한다면, 해당 최소 경로는 g -> h를 거친다고 볼 수 있다. ..

문제 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 다익스트라 문제이다. b가 감염되고 s초 후, a가 감염된다는 뜻은, 노드 b에서 노드 a로 가는 간선의 비용이 s라는 뜻이다. 위의 조건대로 그래프를 만들고 c를 시작으로 다익스트라를 실시한다. c에서 갈 수 있는 컴퓨터의 수와 최대 거리를 구한다. 코드 #include #include #include #include #include using namespace std; vector edges; vector dist; void solution(int st..

문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 [백준][C++] 1261: 알고스팟 문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의 kantatatam.tistory.com 너비 우선 탐색 문제로, 위의 문제와 풀이가 동일하다. 하나 주의해야 할 점은, 시작 지점의 거리가 0이 아니고, 시작 지점의 도둑 루피..

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 너비 우선 탐색 문제이다. 다익스트라로 시도를 했을 때, 메모리초과와 시간초과가 발생하여 너비 우선 탐색으로 변경하였다. 미로의 각 칸을 하나의 노드로 생각하고, (0, 0)칸부터 탐색한다. 현재 노드의 상하좌우를 탐색한다. 탐색하는 노드까지의 거리는 현재 노드까지의 거리에서 벽이 있다면 +1 없다면 +0이다. 탐색하는 노드의 거리를 갱신할 수 있다면 갱신하고, 큐에 넣는다. 거리를 나타내는 배열이 2차원 배열임을 주목하자. 코드..

문제 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 구현, 시뮬레이션, 큐 문제이다. 뱀의 머리, 꼬리, 몸통의 정보를 따로 저장해둔다. pair head = make_pair(0, 0); // 현재 머리의 위치 pair tail = make_pair(0, 0); // 현재 꼬리의 위치 queue body; // 사과를 먹지 못했을 때, 줄어들 꼬리의 위치가 front snake[0][0] = true; // 뱀이 있는 영역을 표시 이동 후 머리의 위치를 queue에 넣어둔다. 이동 후 사과를 먹지 못했다면,..

UWorld::ServerTravel UWorld::ServerTravel Jumps the server to new level. docs.unrealengine.com 서버에서만 실행되며, 서버가 다른 레벨로 이동하며 모든 클라이언트 들을 해당 레벨로 이동시킨다. 서버는APlyerController::ClientTravel을 호출한다. APlayerController::ClientTravel APlayerController::ClientTravel Travel to a different map or IP address. docs.unrealengine.com 클라이언트에서 ClientTravel을 호출하면 다른 서버로 이동한다. 서버에서 ClientTravel을 호출하면 플레이어를 다른 레벨로 이동시킨다.