https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 1. Logic 시작점에서 출발해서 다른 정점들을 거쳐 n-1번째 노드에 도착 하는 최단 거리를 구해야 하기 때문에 다익스트라를 사용해서 풀었다. 와드나 시야가 있는지를 체크하기 위해 bool sight배열을 선언 후 sight배열이 true면 continue하도록 조건을 넣어준 후 다익스트라를 돌리면 된다. 2. Code #include using namespace s..
Algorithm/Beakjoon
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. Logic 시작점에서 시작하여 모든 노드를 순회하면서 연결된 모든 노드까지의 최단거리를 갱신한다. 한 노드에서 모든 노드까지의 최단거리를 구하는 문제이기 때문에 다익스트라 알고리즘을 사용했다. 2. Code #include using namespace std; const int INF = 0x3f3f3f3f; int n..
https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 1. Logic vis배열을 선언하여 탐색한 곳을 표시한다. -모양을 만나면 가로로 끝까지 탐색하며 vis배열에 기록한다. |모양을 만나면 세로로 끝까지 탐색하며 vis배열에 기록하고 연산을 한 횟수를 세준다 2. Code #include using namespace std; string input[51]; bool vis[51][51]; int main() { int n, m; cin >> n >> m..
https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 1. Logic 좌상우하 순서대로 1, 2, 4, 8이라는 값을 가지고 있기 때문에 이는 비트마스킹으로 쉽게 표현할 수 있다. 13을 예시로 들어보면 13을 2진수로 표현하게 되면 1101이다. 즉 13인 방에서 갈수있는 방향을 왼쪽 오른쪽 아래 총 3가지 방향만 갈 수 있다. BFS를 돌 때 dir방향인 dy[4] dx[4]배열을 만들어 놓는데 이와 같은 방향일 때 내가 있는 공간에서 막혀..
https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 1. Logic 이 문제를 풀 때는 산봉우리의 의미를 잘 파악하는 것이 중요하다. 문제에서 정의한 산봉우리는 " 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.)" 라고 했다 인접은 X, Y좌표가 1이하로 차이나야 하기 때문에 (1,1)을 중심으로..
https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 1. Logic BFS로 노드를 지날 때 마다 거리를 더해주며 BFS를 돌면 된다. 입력을 받을 때 양방향으로 받아주고 m개를 입력 받을 때 마다 vis배열만 초기화 잘 시켜주면 된다. 2. Code #include using namespace std; int n, m; vector graph[1001]; bool vis[1001]; int BFS(int start, int e..
https://www.acmicpc.net/problem/9656 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. Logic 돌 갯수가 짝수인지 홀수인지만 판단하면 된다. 돌 갯수가 짝수면 항상 상근이가 이기고 홀수이면 항상 창영이가 이긴다. 2. Code #include using namespace std; int n; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; if(n % 2 == 1) cout
https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 1. Logic 해당 문제를 환형으로 보지말고 그냥 직선형으로 봐서 0번째 색깔을 선택하는 경우와 0번째 색깔을 선택하지 않는 경우 2가지로 나눠서 해결했다. 0번째 색깔을 을 선택하는 경우는 1번째 색깔을 절대로 선택 못하기 때문에 인덱스를 2로 올려준 후 함수로 전달한다. 0을 선택하지 않는 경우는 1번 색깔을 선택해도 되고 안해도 되기 때문에 인덱스는 1, cnt는 0 으로 넣어준다 2. Code #include ..
https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 www.acmicpc.net 1. Logic 입력을 받은것을 기반으로 숫자 입력을 받을 때 마다 vis배열에 체크를 하고 for문을 돌며 각 빙고 라인들을 체크해준다. 2. Code #include using namespace std; int bingo[5][5]; int vis[5][5]; int check1() { int ret = 0; for(int i = 0; i < 5; i++) if(vis[i][0] && vis[i][1] &&..
https://www.acmicpc.net/problem/2441 2441번: 별 찍기 - 4 첫째 줄에는 별 N개, 둘째 줄에는 별 N-1개, ..., N번째 줄에는 별 1개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. www.acmicpc.net 1. Logic 구현,,, 쉬운 구현,,, i만큼 공백 출력 i-공백만큼 별 출력 2. Code #include using namespace std; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { cout
