알고리즘 문제풀이/백준
-
[백준/BOJ] 1068번 트리알고리즘 문제풀이/백준 2022. 4. 25. 23:13
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 인접 리스트를 이용해 트리를 구현한 후, DFS 탐색을 하면서 리프노드에 도달하면 1을 리턴하고, 리프 노드의 수를 각 노드를 거쳐 루트까지 누적해가면 된다. 이때, 루트 노드를 제거하는 경우를 예외처리 해줘야 한다.
-
[백준/BOJ] 2636번 치즈알고리즘 문제풀이/백준 2022. 4. 24. 18:00
https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net (0,0)부터 차례대로 BFS 탐색을 한다. 탐색 도중 값이 1인 지역을 만난다면, 해당 지역은 가장 바깥부분을 의미한다. 따라서 해당 지역을 0으로 바꿔주고, 큐에는 넣지 않는다. 이렇게 하면 BFS 탐색을 할 때마다, 치즈 안쪽의 구멍을 신경쓰지 않아도 공기에 노출된 겉표면만을 제거할 수 있다. #include using namespace std; typedef long long ll; const int dx[]..
-
[백준/BOJ] 1051번 숫자 정사각형 (C++)알고리즘 문제풀이/백준 2021. 11. 16. 17:34
https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 문제의 이해가 좀 어려웠는데, 난이도는 쉬운 문제였다. 꼭지점의 값이 모두 같은 가장 큰 정사각형의 넓이를 찾는 완전 탐색(브루트 포스) 문제였다. #include #include using namespace std; int map[51][51]; int main(void) { freopen("input.txt", "rt", stdin); ios_base::sync_with_stdio(false)..
-
[백준/BOJ] 1600번 말이 되고픈 원숭이 (C++)알고리즘 문제풀이/백준 2021. 11. 4. 15:17
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 2206번 벽 부수고 이동하기를 응용한 것 같은 문제였다. 해당 문제를 해결했다면 어렵지 않았을 BFS 문제다. #include #include #include #include using namespace std; struct Pos { int x, y, cnt; }; int k, w, h; int map[201][201]; int visit[31][201][201]; int dx..
-
[백준/BOJ] 1527번 금민수의 개수 (C++)알고리즘 문제풀이/백준 2021. 11. 2. 16:51
https://www.acmicpc.net/problem/1527 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 간단한 완전탐색(브루트포스) 문제였다. 4와 7로 이루어진 1~9번째 자리의 숫자를 DFS로 모두 구해준 후, 이를 벡터에 저장했다. 그 후, 입력으로 들어온 a와 b 사이에 있는 값이 벡터에 몇개 들어있는지 찾으면 된다. #include #include #include using namespace std; int a, b, answer; vector v; void DFS(int cnt, int..
-
[백준/BOJ] 2573번 빙산 (C++)알고리즘 문제풀이/백준 2021. 11. 2. 16:28
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제의 조건을 정리하며 차례대로 구현하면 어렵지 않게 해결할 수 있는 BFS 문제였다. 1. map 입력을 받는다. 2. map[i][j] > 0, 현재 빙산과 접하는 바닷물의 수를 구하고, 이를 현재 빙산에서 빼준다. (그 뺀 값이 음수라면 0으로 바꿔주기) 3. 모든 map에 대해 2번 작업을 완료했다면, BFS를 통해 분리된 덩어리의 수를 구한다. 4. 분리된 덩어리의 수가 2보다 크거..
-
[백준/BOJ] 2206번 벽 부수고 이동하기 (C++)알고리즘 문제풀이/백준 2021. 10. 29. 15:04
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 벽 뚫기 사용의 유무를 체크하기 위해 3차원 배열을 이용해야 한다. 해당 아이디어만 잘 떠올린다면 어렵지 않게 해결할 수 있는 BFS 문제였다. #include #include #include #include using namespace std; int N, M; int map[1001][1001]; int visit[2][1001][1001]; int dx[4] = {-..
-
[백준/BOJ] 5014번 스타트링크 (C++)알고리즘 문제풀이/백준 2021. 10. 28. 17:26
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1697번 숨바꼭질 문제와 비슷한 BFS 문제였다. 그래서 어렵지 않게 해결 ㅎ (범위 처리만 잘 해주자) #include #include #include #include using namespace std; int F, S, G, U, D; int visit[1000001]; int BFS() { queue q; q.push(S); visit[S] = 0; while(!q.empty()) { int now ..