꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1963 오랜만에 에라토스테네스의 체와 함께 BFS(Breadth First Search) 알고리즘을 사용하여 푸는 문제였습니다.에라토스테네스의 체를 통해 우선 4자리 소수를 미리 구해놓은 뒤에 한자리씩 숫자를 바꿔가며 BFS를 적용하면 풀리는 문제였습니다.주의할 점은, 4자리 소수이기 떄문에 천의 자리 수가 0이면 안됩니다!! #include #include #include #include //memset using namespace std; const int MAX = 10000; int start, destination; int minFactor[MAX]; //minFactor[i] -> i의 가장 작은 소인수(i가 소수인 ..

문제 링크입니다: https://www.acmicpc.net/problem/5014 BFS(Breadth First Search) 알고리즘을 적용하여 푸는 문제였습니다.기존의 BFS 문제와는 달리 Dir 구조체와 Dir 배열을 미리 정의하지 않고 while문 내에서 다음 층(위로 갔을 경우, 아래로 갔을 경우) 두 가지만 고려해주면 되는 문제였습니다.결과는 백준 2589번 보물섬(http://jaimemin.tistory.com/644) 문제와 같이 cache[도달한 층] - 1을 출력해야합니다. #include #include using namespace std; const int MAX = 1000000 + 1; int F, S, G, U, D; int cache[MAX]; int BFS(void) ..

문제 링크입니다: https://www.acmicpc.net/problem/2589 기존의 BFS(Breadth First Search) 문제와 달리 시작점과 도착점이 정해져있지 않아서 Brute Force 방식으로 찾아봐야하는 문제였습니다.다행히 가로와 세로의 크기가 최대 50이기 때문에 전체 지도 크기가 50*50=2500이기 때문에 시간초과를 걱정하지 않아도 됩니다!그리고 cache 배열에는 시작점과 도착점까지의 칸 수이기 때문에 경로는 cache[시작점][도착점] - 1 입니다. #include #include #include #include #include //memset using namespace std; const int MAX = 50; typedef struct { int y, x; }..

문제 링크입니다: https://www.acmicpc.net/problem/2410 2의 n 제곱수의 합으로 표현할 수 있는 방법의 수를 쉽게 구하기 위해 cmath 헤더파일의 pow 함수를 사용했던 문제였습니다.DP를 적용하기 위해 cache[MAX][20] 이차원 배열을 선언했는데 pow(2, 20) = 1,048,576이기 때문에 20으로 했습니다.처음에는 cache[MAX][MAX]로 선언하려고 했지만 배열의 크기가 너무 크기 때문에 2^k를 표현하는 k승만 저장했습니다.간단한 DP 문제였기 때문에 별도로 설명할 내용은 별로 없는 것 같고 조건충족에서 (num > 0 && k == 0)은 1을 통해 모든 숫자를 표현가능하기 때문에 2^k = 2^0 = 1의 경우 조건 충족 처리를 했습니다. #in..

문제 링크입니다: https://www.acmicpc.net/problem/7569 백준 7576번 토마토(http://jaimemin.tistory.com/605)와 거의 동일하지만 2차원이 아닌 3차원이라는 점이 유일한 차이점이였습니다.대각선에 위치할 경우 토마토는 익지 않기 때문에 6가지의 경우의 수만 고려해줍니다.(왼쪽 오른쪽 위 아래 앞 뒤)7576번은 잠시 FIFO 개념을 혼동해서 덱(deque)을 사용했지만 이번에는 전형적인 BFS(Breadth First Search) 알고리즘답게 큐를 사용하여 풀었습니다. #include #include using namespace std; const int MAX = 100; typedef struct { int y, x, z; }Dir; Dir mov..

문제 링크입니다: https://www.acmicpc.net/problem/2644 BFS(Breadth First Search) 알고리즘을 사용하여 푼 문제였습니다.이번 문제는 visited 대신 cache를 이용하여 촌수가 이미 정해져있는 사람은 찾지 않고 촌수가 정해져있지 않은 사람만 큐에 넣어 계산하는 문제였습니다.주의할 점은 부모 자식 관계를 벡터에 넣을 때 양방향으로 넣어줘야한다는 점입니다! #include #include #include #include using namespace std; const int MAX = 100 + 1; int N, M; int node1, node2; //촌수 계산하는 두 사람 vector family[MAX]; int cache[MAX]; //전형적인 BFS..

문제 링크입니다: https://www.acmicpc.net/problem/1389 플로이드-와샬 알고리즘을 사용하여 푸는 문제였습니다.최소 베이컨 수를 구해야하기 때문에,1. i와 j가 아직 모르는 경우 k를 통해 아는 경우 단계 수를 업데이트하고2. i와 j가 서로 알더라도 k를 통해 알면 단계 수가 줄어들 경우에도 업데이트합니다. 이후에는 각 사람마다 베이컨 수를 계산하고 동등한 베이컨 수더라도 인덱스가 적은 사람을 출력하라고 했기 때문에 result>sum일 때만 업데이트해주면 됩니다! #include #include using namespace std; const int INF = 987654321; const int MAX = 100 + 1; int N, M; int graph[MAX][MAX..

문제 링크입니다: https://www.acmicpc.net/problem/7562 BFS(Breadth First Search) 알고리즘으로만 풀 수 있는 문제였습니다.(DFS 불가능)나이트가 움직일 수 있는 8 방향을 미리 정의한 뒤에 BFS를 통해 현재 위치에서 갈 수 있는 지점을 큐에 집어넣으면서 움직인 횟수를 업데이트하며 풀면 되는 문제였습니다.cache를 모두 INF로 초기화한 뒤에 min(다음 위치에 저장되어 있는 움직인 횟수, 현재 지점까지 움직인 횟수 + 1)을 통해 최소 이동횟수를 구하면 됩니다.pair를 통해 y와 x의 좌표를 저장하였고 start는 시작지점, destination은 도착지점, 그리고 currentPos는 현재 위치의 좌표입니다! #include #include #in..

문제 링크입니다: https://www.acmicpc.net/problem/2468 DFS(Depth First Search) 혹은 BFS(Breadth First Search) 알고리즘을 적용하여 풀 수 있는 문제였습니다.물에 잠기는 높이가 주어지지 않았기 때문에 1~100까지 모두 살피면서 연결된 요소들의 개수 즉, Component 최대 개수를 Brute Force 방식으로 찾아봐야하는 문제였습니다.copy 함수를 통해 물에 잠기지 않는 높이만 area 배열에서 temp 배열로 복사하고 DFS를 통해 Component 개수를 찾아보면 되는데 한 가지 주의할 점은 최소 연결 요소는 1이기 때문에 처음에 result=1로 초기화 한 상태에서 max(result, cnt);를 통해 최대 연결 요소 개수를..

문제 링크입니다: https://www.acmicpc.net/problem/11724 DFS(Depth First Search) 또는 BFS(Breadth First Search) 알고리즘을 사용하여 풀 수 있는 문제였습니다.무방향 그래프(Undirected Graph)이기 때문에 양쪽 정점을 모두 연결해주고 DFS를 통해 연결 요소들의 개수를 찾으면 쉽게 풀 수 있는 문제였습니다. #include #include using namespace std; const int MAX = 1000 + 1; int M, N; vector graph[MAX]; bool visited[MAX]; //전형적인 DFS void DFS(int node) { visited[node] = true; for (int i = 0;..