프로그래밍 공부 노트

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: 단지 배치도 ..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 입력받은 모눈종이에서 외부 공기를 나타내는 값을 따로 지정하자. 이후 모눈종이에 놓인 각 치즈에 대해 외부 공기가 2 이상이라면 해당 치즈를 녹인 뒤, 해당 좌표와 인접한 칸을 외부 공기로 바꾼다. 이 과정을 모든 치즈가 녹을 때까지 반복하면 해결할 수 있다. #include #include using namespace std; typedef pair coord; #define MAX..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 각 컴퓨터를 노드로, 주어진 컴퓨터 쌍을 에지로 보면 주어진 문제는 그래프를 탐색했을 때 탐색 가능한 노드의 수를 출력하는 문제이다. - dfs #include #define MAX_N 100 // graph: 그래프, virus[i]: i번 노드를 방문했다면 true, 그렇지 않다면 false bool graph[MAX_N][MAX_N], virus[MAX_N]; // 노드의 수 int N; int ..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 주어진 지역 정보를 비가 높이 K만큼 왔을 때 잠기는지 여부를 저장하는 2차원 bool 배열로 생각하면, 그래프 탐색을 통해 안전지대의 개수를 셀 수 있다. 지역의 최대 크기가 100 * 100이고 각 높이의 최댓값 역시 K이므로, 각 지점의 범위 내에 있는 모든 K에 대해 그래프 탐색을 실행하면 충분히 빠른 시간 안에 답을 구할 수 있다. #include #define MAX_N 100 // N: 지역..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 입력받는 맵의 각 성분을 노드로, 상하좌우로 인접한 관계를 에지로 보자. 값이 1인 노드를 단 한 번 방문할 수 있게 하면 나머지는 일반적인 그래프 탐색 문제와 같다. #include #include using namespace std; typedef pair coord; typedef pair stat; typedef pair agent; #define MAX_Y 100..

https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 문자판의 각 칸을 노드로, 상하좌우로 인접한 관계를 에지로 보자. 그래프 탐색을 사용하면 문자판의 크기와 문자열의 길이가 작을 때는 시간 안에 정답을 구할 수 있지만, 문자판의 크기나 문자열의 길이가 커지면 시간 초과가 발생한다. 따라서 각 노드를 탐색할 때 노드와 문자열의 위치에 따라 탐색한 결과를 저장하고, 기존에 탐색한 위치를 다시 탐색할 경우 저장한 값..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 값이 1인 미로의 각 성분을 노드, 상하좌우로 연결된 노드의 관계를 에지라고 보면 이 문제는 그래프를 탐색해 (1, 1)에서 (N, M)까지 탐색하는 그래프 탐색 문제이다. #include #include #include using namespace std; typedef pair coord; #define MAX_N 100 #define _y first #define _x second // table[y][x]: 현재 노드가 ..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 1. 트리의 루트 노드에서 가장 거리가 먼 노드 a에 대해, 노드 a로부터 가장 거리가 먼 노드 b까지의 거리가 트리의 지름이 된다. #include #include using namespace std; typedef pair edge; #define MAX 10000 #define _node first #define _dist second int N, ret = 0; edge..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 배열의 각 성분을 노드, 성분이 상하좌우로 인접한 것을 에지라고 하면 이 문제는 그래프를 순회하며 그래프의 개수와 노드의 수가 가장 많은 그래프를 찾는 문제가 된다. - 너비 우선 탐색 #include #include using namespace std; typedef pair coord; #define _y first #define _x second #define MAX_N 500 // 그림이 그려진..