돌이 코딩하는 방

문제 태그 : https://www.acmicpc.net/problem/2472 정말 좋은 문제라고 생각한다. 여러가지 테크닉을 같이 써야 문제를 해결할 수 있다. 그런데 최근에 재채점을 당해 틀려서 다시 푼 김에 글을 작성하였다. 문제 소개 그래프가 주어지고 3개의 출발 지점이 주어진다. 만약 지점 A와 B가 존재해서 출발지점 3곳에 대해서 모두 B가 A보다 출발 지점까지의 거리가 짧으면 A에는 매장을 설치할 수 없다. 각 지점에 대해서 질의를 던지면 그 지점에 매장을 설치할 수 있는지 대답을 해야한다. 문제 풀이 일단 그래프 상에서 어떠한 한 노드를 중심으로 다른 모든 점까지의 거리를 각각 구하는 것은 다익스트라를 3번 돌리는 것으로 쉽게 처리해 줄 수가 있다. 다르게 말하면 우리는 모든 노드에 대해..

문제 태그 : https://www.acmicpc.net/problem/17940 문제 소개 출발지에서 목적지까지 지하철을 타고 이동한다. 각 지하철역은 A회사 또는 B회사의 소유인데 방문하는 지하철역의 변경횟수를 최소화 하면서 이동을 해야한다. 만약 횟수가 최소인 경로가 여러가지가 있으면, 경로의 길이가 가장 짧은 경로를 선택한다. 이때 최소 변경횟수와 경로의 길이를 출력하라. 문제 풀이 사전지식 + 간단한 아이디어 하나로 바로 해결할 수 있다. 1. 일단 경로를 구하는것이고 시작점->도착점 하나이기 때문에 기본문제면 다익스트라를 이용해 해결 할 수 있다. 2. 결국 중요한 것은 지하철역 회사가 바뀌는 경로이다. 3. 똑같은 위치로 이동할 때 다른 경로를 아무리 길게 해도 회사가 바뀌는 경로로 가는 것..

문제 태그 : https://www.acmicpc.net/problem/1848 다익스트라에 관해 포스팅을 하다가 백준 다익스트라 문제들을 살펴보았는데, 한 문제 시도하다가 틀린 흔적을 발견했다. 그래서 그 문제를 풀게 되었는데, 굉장히 좋다고 생각하여, 풀이도 저장할겸 포스팅을 하게 되었다. 문제 설명 양 방향 그래프가 주어지는데 일반적인 양방향 그래프와 다른 점은 A점에서 B점으로 갈 때의 비용과 B점에서 A점으로 갈 때의 비용이 다르다는 것이다. 이때 목적은 1번 정점에서 출발하여 1번 정점으로 다시 돌아오는 최단거리를 구하는 것이다. 이때 한 번 지난 간선은 역으로도 다시 올 수 없다는 것이다. 즉 다시 말해, 1->3->1의 경로로 이동하는 것은 안된다는 것이다. 문제 풀이 (사고의 흐름) 일단..

문제 태그 : https://www.acmicpc.net/problem/1753 문제 설명 이 문제에서 요구하는 것은 방향그래프에서 특정 정점이 주어졌을 때 그 점으로부터 모든 점까지의 거리를 각각 구하는 것이다. 이는 다익스트라 알고리즘이 하는 일과 정확히 일치한다. 맞다. 다익스트라를 한번 연습해보라는 뜻이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include using namespace std; typedef long long int ll; typedef pair pii; #define ff first #define ss..

이번에 그래프 관련 알고리즘 다익스트라 (dijkstra) 를 들고 오게 되었다. 우리가 앞으로 그래프 문제를 많이 보게 될 텐데, 그래프 문제에서 가장 많이 다루게 되는 요소가 무엇일까? 바로 거리일 것이다. 가장 짧은 거리, 가장 짧은 거리의 경로, 임의의 두 노드 사이의 거리 등 정말 다양한 거리들을 알아야 할 필요성이 앞으로 생기게 된다. 다익스트라는 그 중 한 노드에서부터 모든 노드까지의 각각의 거리를 알아내고 싶을 때 사용되어진다. 어느정도 bfs랑 비슷한 느낌일 수 있다. bfs를 할 때는 queue의 맨 앞 노드에서 도달할 수 있는 모든 노드를 다시 queue에 넣어 탐색을 한다. 다익스트라는 도달할 수 있는 노드 중 기준노드로부터 가장 가까운 점을 뽑아 그 점을 거쳐 도달할 수 있는 다른..