문제 링크 : 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..

문제 링크 : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) www.acmicpc.net 문제 설명 1. 방향 성이 없는(양방향) 그래프가 주어지고 시작점 부터 끝점 까지의 최단거리를 출력. 2. 단, 주어지는 2개의 정점을 방문하여..