프로그래밍 공부 노트

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 모든 노드에서 모든 노드로의 경로를 묻는 문제이므로 플로이드-워셜 알고리즘을 사용한다. #include #define MAX_N 100 int main() { // graph[i][j]: i에서 j로 가는 경로가 있다면 true, 없다면 false bool graph[MAX_N][MAX_N]; // 노드의 개수 int N; // 문제의 조건을 입력받은 뒤 scanf("%d", &N); for (int i = 0; i < N; i++) fo..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 입력받은 2차원 배열의 각 성분을 노드, 인접한 노드 사이의 관계를 에지로 보면, 이 문제는 그래프 탐색을 통해 같은 값을 가진 인접한 노드 집합의 수를 세는 문제이다. 이 때 일반적으로 그래프를 탐색할 경우 visit 배열을 사용해 해당 좌표를 방문했는지 여부를 판단하지만, 주어진 문제에선 그래프를 두 번 탐색해야 하고 그룹을 어느정도 유지해야 하므로, 탐색한 노드의 값을 바꾸는 방법으로..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 상근이의 집과 락 페스티발, 각 편의점을 노드로, 맨하탄 거리가 1000 이하인 두 노드 사이의 경로를 에지로 두면 주어진 문제는 그래프 탐색 문제로 볼 수 있다. 그래프 탐색을 진행한 뒤 상근이의 집, 즉 0번 노드에서 락 페스티발, 즉 N + 1번 노드로 이동할 수 있다면 happy, 그렇지 않다면 sad를 출력하면 된다. - bfs #include #include using namesp..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 각 수를 노드, 연산을 통해 수를 변환하는 것을 에지라고 하면 이 문제는 노드 A에서 노드 B로의 최단 경로를 찾는 문제이다. 따라서 각 노드를 방문했는지 여부와 직전 노드, 그리고 연산 종류를 저장하는 클래스 node를 생성한 뒤 bfs를 통해 최단 경로를 찾고, 탐색한 경로를 순서대로 출력하면 정답이 된다. #include #include #include using namespac..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 상자의 각 칸을 노드로, 칸 사이의 인접한 관계를 에지로 보면 이 문제는 2차원 그래프를 탐색하는 문제로 볼 수 있다. bfs를 아직 익지 않은 토마토의 개수, 즉 값이 0인 노드의 개수를 추적하면서, 그래프를 모두 탐색했을 때 값이 0인 노드를 모두 탐색했다면 bfs의 단계의 수를, 그렇지 않다면 -1을 출력한다. 이 때 이 단계의 수를 출력하는 문제이므로 dfs는 사용할 수 없..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 상자의 각 칸을 노드로, 칸 사이의 인접한 관계를 에지로 보면 이 문제는 3차원 그래프를 탐색하는 문제로 볼 수 있다. bfs를 아직 익지 않은 토마토의 개수, 즉 값이 0인 노드의 개수를 추적하면서, 그래프를 모두 탐색했을 때 값이 0인 노드를 모두 탐색했다면 bfs의 단계의 수를, 그렇지 않다면 -1을 출력한다. 이 때 이 단계의 수를 출력하는 문제이므로 dfs는 사용할..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리를 배열로 저장했을 때, 트리의 인덱스 범위 [s, e)에 대해 루트 노드는 항상 s에 있고, 왼쪽 서브 트리와 오른쪽 서브 트리는 어느 경계를 기점으로 나뉘어 있다. 범위 (s, e)에 대해 lower_bound를 실행할 경우 왼쪽 서브 트리와 오른쪽 서브 트리, 즉 값이 루트 노드보다 작은 부분과, 값이 루트 노드보다 크거나 같은 부분을 나누는 지점을 찾을 수 있다. 이 때 오..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 각 별을 노드, 별자리 위의 선을 에지, 별과 별 사이의 거리를 가중치로 두면, 이 문제는 최소 스패닝 트리를 구하는 문제이다. - 크루스칼 기법 #include #include #include using namespace std; typedef pair point; typedef pair edge; #define MAX_N 100 #define _y first #define _x second #d..

https://www.acmicpc.net/problem/3182 3182번: 한동이는 공부가 하기 싫어! H-ALGO 회원인 한동이는 공부하는것을 좋아하지 않는다. 하지만 약삭빠르게도 한동이는 공부도 하지 않으면서 어려운 시험을 통과하고 싶어한다. 그러던 와중 어느 날, 한동이의 동기가 한동이에 www.acmicpc.net 각 선배들을 노드로, 각 선배가 알려주는 다른 선배를 에지 관계로 보면, 이 문제는 가장 긴 사이클의 길이를 찾는 문제이다. 각 노드에서 시작해, 이전에 방문한 적이 있는 노드가 나올 때까지 에지를 타고 올라가면서 이용한 에지의 수를 센다. 이렇게 센 에지의 수 중 최댓값을 출력하면 정답이 된다. #include #define MAX_N 1001 // visit[i]: 노드 i를 방..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2차원 배열 형태로 주어진 그래프를 탐색하며 독립된 그래프의 수와 각 그래프의 노드 수를 출력하는 문제이다. -bfs #include #include #include #include using namespace std; typedef pair coord; #define MAX_N 25 #define _y first #define _x second // N: 단지 부지의 크기, map: 단지 배치도 ..