득이공간

문제풀이 다익스트라 알고리즘을 이용해서 푸는 문제입니다.(1,1) -> (n,m)으로 이동하되, 인접 노드 탐색 시 priority_queue(최소힙) 자료구조를 이용해서큐에 들어오는 노드 중 벽을 부수는 비용이 가장 적은 노드부터 탐색하도록 했습니다.그리고 인접 노드의 최소비용 배열의 값을 갱신해주도록 해서 풀었습니다.코드#include #include #include #include using namespace std;typedef pair p;typedef pair pp;const int Inf = INT_MAX;const int DX[4] = { -1, 0, 1, 0 };const int DY[4] = { 0, -1, 0, 1 };int N, M;bool IsWall[100][100];int Co..

문제풀이 백트래킹을 이용해서 푸는 문제입니다.먼저 각 학생의 친구 수를 저장하는 배열과모든 학생에 대해서 친구인지 아닌지를 저장하는 2차원 배열을 생성했습니다.그리고 백트래킹을 이용해서 1부터 N번의 학생까지 K-1 이상의 친구를 보유한 학생을 선택해서K명을 선택했을 때 모두 서로 친구라는 조건이 만족하면 출력 & 종료하도록 했습니다. 코드#include using namespace std;int N, K, F;int FN[901];bool Friend[901][901];int Sel[62];bool Check(){ for (int i = 0; i N) { return; } if (FN[Num] >= K - 1) { Sel[Idx] = Num; DFS(Idx + 1, Num + 1); } DFS(..

문제풀이 다익스트라 알고리즘을 이용해서 푸는 문제입니다.각각의 노드 사이의 이동 시간을 구해서 저장해주고 나면나머지는 일반적인 다익스트라 유형의 문제의 풀이와 동일합니다.각 노드 사이의 이동 시간을 구할 때 시작 노드를 출발 지점으로 놓으면 도착 지점까지 걸어가는 시간으로 구해야 합니다.시작 노드를 제외한 나머지 노드에서 출발 할때는 걸어가는 시간과 대포를 이용한 시간 중 작은 값으로 저장해주면 됩니다.코드#include #include #include #include #include using namespace std;const double Inf = INT_MAX;typedef pair p;typedef pair n;int S, E, N;p Point[102];list Neighbor[102];dou..

15683번: 감시스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감www.acmicpc.net 문제풀이 구현할 것이 많은 시뮬레이션 & 브루트포스 & 백트래킹 유형의 문제입니다. 카메라의 개수는 많지 않기 때문에, 각 카메라의 방향을 완전탐색(브루트포스 & 백트래킹)으로모든 각도에서 지정해보고 그 중 사각지대의 최소값을 구하면 됩니다. 사각지대를 구하기 전에 각 카메라의 방향에 따른 사무실의 상태를 구할 때 많은 구현이 필요합니다.각 카메라가 사무실을 스캔할 때, 카메라의 종류에 따라 먼저 분류하고지정된 스캔 방향, 횟수에 따라서 사무실의 상태를 구..

2470번: 두 용액첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00www.acmicpc.net 문제풀이 적절한 두 용액을 선택하는 과정에서 완전 탐색을 이용하면 $100000 * 100000$번의 연산이 수행되므로 시간초과가 발생합니다.따라서 한 용액을 먼저 선택한 후 다른 용액을 이분 탐색을 이용해서 선택하도록 하면 $100000 * 16.6 (={log_{2}}{100000})$번의 연산만으로 풀 수 있습니다.Start, End 인덱스를 지정할 때는 선택한 두 용액의 합과 0의 크기를 비교해서 조절해주면 됩니다.코드#in..

16234번: 인구 이동N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모www.acmicpc.net 문제풀이 너비 우선 탐색을 이용해서 푸는 시뮬레이션 유형의 문제입니다.미방문 노드에서 BFS를 시작해서 연합 영역을 큐에 저장해주고연합의 크기가 2이상일 때 인구 이동을 시켜주었습니다.인구 이동이 더이상 이뤄지지 않을 때까지 해당 로직을 반복해서 시뮬레이션하도록 구현했습니다.코드#include #include #include using namespace std;typedef pair p;const int..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제풀이 DFS 알고리즘 & List 자료구조를 이용해서 풀었습니다. 각 노드 마다 부모 노드를 배열에 저장해주고, 자식 노드는 리스트로 구성해주었습니다. 그리고 삭제 노드를 입력받았을 때 해당 노드의 부모의 자식 리스트에서 제거해주고 루트노드로부터 깊이 우선 탐색을 수행하도록 구현했습니다. 코드 #include #include #include using namespace std; int N, Root, Cnt; int P[50]; list C[50]; v..

3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제풀이 덱 자료구조를 이용해서 뱀 몸의 위치를 기록하는 방법으로 푸는 시뮬레이션 유형의 문제입니다. 각 초마다 문제에서 제시한 조건대로 이동을 구현해주어 풀었습니다. 덱에 push_back으로 머리 이동 위치를 저장해주었고, 사과를 먹지 않았을 때는 pop_front로 꼬리를 이동해주었습니다. 그리고 초가 끝났을 때는 입력받은 X, C 정보에 따라 뱀이 현재 향하고 있는 방향(0:L, 1:R, 2:T, 3:B)을 나타내는 변수를 바꿔주었습니다. 코드 #include ..

16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제풀이 이분 탐색, 유니온-파인드 연산을 이용해서 푸는 문제입니다. 민수의 카드를 오름차순 정렬하고 upper_bownd 함수(이분 탐색)를 사용해서 내야하는 카드를 찾아 출력하면 됩니다. 그런데 한 번 낸 카드는 다시 낼 수 없기 때문에 다음 탐색에서는 제외해야 합니다. 카드의 총 개수가 많기 때문에 이 때 원소를 삭제하는 방식으로 풀면 시간초과가 발생합니다. 따라서 유니온-파인드 연산을 이용해서 한번 낸 ..

2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제풀이 N-1개의 에지를 구성하는 최소 비용을 구하는 MST 유형의 문제입니다. 각 에지의 비용을 구할 때, 모든 행성끼리 연결해버리면 O($N^{2}$)으로 시간초과가 발생합니다. 따라서 행성들을 X값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개), Y값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개), Z값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개)를 구합니다. 이렇게 되면 3N-3개의 에지만으로 문제를 풀 수 ..