문제 링크 : https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 www.acmicpc.net 문제 설명 거의 최단경로 : 시작점에서 목적지 까지 가는 최단경로를 이용하지 않고 갈 수있는 최단 경로 . 1. 단..

문제 링크 : https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1> result; answer = INF; //0번째 스위치를 누르지 않은 상태에서 시작 copyS = s; simulation(1, 0); //0번째 스위치를 누른 상태에서 시작 copyS = s; push(0); simulation(1, 1); if (answer == INF) cout

플루이드 - 와샬 알고리즘은 그래프 탐색 알고리즘중 가장 간단하지만 모든 정점사이의 최단거리를 구할 수있다. 하지만 시간 복잡도가 O(N^3) 이므로 정점의 갯수가 많으면 쓰는데 제약이있다. 설명보다는 문제를 보면서 이해하는게 쉽다. 문제 링크 : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 ..

깊이 우선 탐색 (depth-first search: DFS) 정의 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사 알고리즘 1. 시작지점을 기준으로 이동가능한 경우 자기자신을 호출(재귀 함수) 를 통하여 방문가능한 곳까지 방문. 2. 이미 방문하였거나 더이상 방문할 수 없을경우 return. 코드 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..

BFS(너비 우선 탐색) 정의 너비 우선 탐색(Breadth-first search, BFS)은 그래프 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 자료구조 큐를 이용하여 구현. 그림에서 보면 회색은 현재 큐에 들어가있는 정점이고 검은색은 방문완료한 정점이다. 알고리즘 (2차원 배열기준) 1. 큐를 이용하여 시작점을 먼저 push . 2. 큐가 비워 질때까지 반복 3. 시작점을 중심으로 상,하,좌,우 중 탐색가능한지점을 큐에 넣어주고 탐색이 끝 날때 까지반복. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..

문제 링크 : https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때 www.acmicpc.net 문제 설명 1. 각 마을에는 한명의 학생이살고 각 마을마다 파티가 열린다. 2. 각 마을로 이동하는 단방향 그래프가 주어짐 3..