프로그래밍 공부 노트

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 각 점을 노드로, 점과 점 사이를 걷거나 순간이동으로 이동하는 것을 에지라고 하면, 노드 N에서 노드 K까지 bfs로 이동하는 것으로 치환할 수 있다. #include #include using namespace std; #define MAX_N 100000 // visit[i]: 노드 i를 방문했다면 true bool visit[MAX_N + 1]; // bfs에 사용..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 각 인원을 대상으로 케빈 베이컨 게임을 진행해도 되지만, 인물의 수가 충분히 적고 인물의 관계도를 그래프로 표현할 수 있으므로 플로이드-와샬 방식을 사용할 수 있다. #include #include using namespace std; #define MAX_N 100 #define FOR(i) for (i = 1; i

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 주어진 그래프를 각각 깊이 우선 탐색, 너비 우선 탐색을 하는 문제이다. 깊이 우선 탐색은 호출 스택을, 너비 우선 탐색은 STL을 이용해 계산하는 것이 편하다. #include #include using namespace std; #define MAX_N 1000 // edge[i][j]: 노드 i와 j가 연결되어 있다면 true, 아니라면 false // ..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 1. 트리의 루트 노드에서 가장 거리가 먼 노드 a에 대해, 노드 a로부터 가장 거리가 먼 노드 b까지의 거리가 트리의 지름이 된다. #include #include using namespace std; typedef pair edge; #define MAX 100001 #define _node first #define _dist second int N, ret = 0; edge ..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 각 파티를 그래프, 파티에 참여하는 사람을 노드, 서로 만난 사람의 관계를 에지, 처음에 진실을 아는 사람을 탐색 시작 노드로 치환하면 이 문제는 그래프 탐색 문제가 된다. 우선 진실을 아는 사람, 그러니까 탐색을 시작할 노드 번호를 입력받고 파티, 그러니까 연결되지 않은 그래프를 입력받아 저장한다. 그리고 탐색 시작 노드로부터 각 그래프에 대해 탐색을 진행하면 탐색한 그래프와 탐색하지 않은 그래프로 나뉘게..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 주어진 입력을 희소행렬 꼴로 저장한 뒤 값이 입력된 성분을 노드, 1차 혹은 2차 인덱스가 같고 나머지 인덱스가 1 차이나는 두 성분을 서로 연결된 노드로 생각하자. 배열의 각 성분을 탐색하며 노드를 발견한다면, 그 자리에 배추가 존재한다는 뜻이므로 그래프를 탐색하며 배추흰지렁이의 수를 1씩 늘린다면 필요한 배추흰지렁이의 수를 얻을 수 있다. #include #define MAX 50 int M, N; boo..