프로그래밍
BOJ 1261 · 알고스팟
알고리즘 분류 : BFS, 다익스트라 2178번 미로탐색에서 약간 변형된 문제이다. (1, 1)부터 (N, M)까지 미로를 이동하면서 벽을 부시는 최소 횟수를 구해야 한다. 빈 방으로 이동하면 가중치가 0, 벽으로 이동하면 가중치가 1인 것으로 바꿔서 생각한다.가중치가 0과 1로 나뉘므로, 일반적인 BFS 방법으로는 풀 수 없다.이를 BFS 방법으로 해결하기 위해 큐(Queue)를 2개 사용하면 된다.빈 방으로 이동할 때는 첫 번째 큐에 넣고, 벽을 부수고 이동할 때는 두 번째 큐에 넣는다.두 개의 큐에 들어간 값을 순서대로 빼면서 처리하면 된다.큐를 2개 사용하므로, 덱(Deque)을 앞 뒤로 사용하면 비슷한 방법으로 해결할 수 있다. C++ 소스코드 #include #include using name..
BOJ 1697 · 숨바꼭질
알고리즘 분류 : BFS N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. 한번 이동할 때 1초 걸리고, 최소 시간을 구하는 문제이므로, BFS를 사용하기에 적합하다. 현재 좌표를 X라고 할 때, 다음 좌표는 X-1, X+1, X*2 중 하나이다.X의 범위는 0부터 100,000까지 이므로, BFS 탐색을 하면서 범위를 벗어나지 않도록 체크한다.다음 좌표로 이동하면서 현재 좌표까지 걸린 시간에 1초를 더해서 다음 좌표에 저장한다.정답은 K 좌표에 있다. C++ 소스코드 #include #include using namespace std; const int MAX = 1e6; int n, k; int dist[MAX+1]; void bfs() { queue q; q.push(n); while..
BOJ 4963 · 섬의 개수
알고리즘 분류 : DFS 섬의 개수를 세는 문제다. 섬은 인접한 땅으로 이루어져 있고, 인접의 기준은 센터를 중심으로 8방향(상하좌우대각선)으로 한 칸씩 떨어진 곳이다. 4방향 인접 문제에서 방향만 추가해서 구현하면 된다. 비슷한 문제는 BOJ 2667번 '단지번호붙이기'이다. C++ 소스코드 #include #include int w, h; int a[51][51]; bool check[51][51]; const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}; const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1}; void dfs(int x, int y) { check[x][y] = true; for (int i=0; i
BOJ 1707 · 이분 그래프
알고리즘 분류 : DFS DFS를 이용하여 이분 그래프인지 아닌지 확인할 수 있다. 이분 그래프(Bipartite graph)란, 인접한 노드는 서로 다른 색의 노드로 구분되고, 그래프 내의 모든 노드를 두 가지 색으로만 칠할 수 있는 그래프를 말한다. DFS 탐색을 통해 아직 방문하지 않은 노드(0)를 방문한다. 방문할 때 어떤 색인지 표시해둔다. 이 코드에서는 2개의 그룹으로 나눈다고 가정하고, 1과 -1의 그룹으로 구분했다.다음 노드는 현재 그룹 번호에 -1을 곱해서 1과 -1을 교차하여 그룹 짓도록 했다.만약 다음 노드가 이미 방문한 노드라면, 현재 노드의 그룹 번호와 다음 노드의 번호가 같은지 확인한다.번호가 같으면 인접한 노드가 같은 그룹이므로, false를 리턴한다.DFS 탐색이 끝날 때 까..
BOJ 11724 · 연결 요소의 개수
알고리즘 분류 : DFS DFS를 통해 연결 그래프의 개수를 확인하면 된다. 방문 여부를 저장하는 check 배열을 따로 만들고, N개의 노드 개수만큼 루프를 돌면서 방문하지 않은 곳에 DFS를 돌리면 된다. 처음 DFS를 호출할 때 카운트를 하면 연결 요소의 개수를 셀 수 있다. C++ 소스코드 #include #include using namespace std; int n, m; vector a[1001]; bool check[1001]; void dfs(int now) { check[now] = true; for (int i=0; i
BOJ 2667 · 단지번호붙이기
알고리즘 분류 : DFS, BFS DFS/BFS 완전 탐색을 하여 풀 수 있는 문제다. 연결 그래프의 개수를 세는 문제와 비슷하다. 단지는 서로 이어져있으므로, 인접한 집(1)이 있는지 DFS로 탐색한다.DFS로 탐색하면서 집의 수를 센 후, 값을 0으로 변경한다.0은 집이 없거나, 이미 방문한 곳이므로 다시 방문하지 않는다.DFS 탐색이 끝나면, 단지(인접한 집의 그룹)는 모두 0이 되어 있다.N x N 지도를 처음부터 끝까지 탐색하면서 아직 방문하지 않은 곳이 있다면, DFS로 다시 탐색한다.DFS를 처음 시작한 횟수가, 단지의 수이다.각 단지내 집의 수를 오름차 순으로 정렬해야 하므로, 이를 저장하는 배열을 따로 만들고 정렬하여 출력한다. C++ 소스코드 (DFS) #include #include ..
BOJ 6588 · 골드바흐의 추측
알고리즘 분류 : 수학 골드바흐의 추측(Goldbach's conjecture)이란, 2보다 큰 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다는 추측을 말한다.우선 2부터 1,000,000까지의 모든 소수를 에라토스테네스의 체로 구한다. 참조입력 N에 대하여 위에서 구한 소수를 2부터 순서대로 A라고 정한다.B = N-A인 소수가 존재하는지 확인하기 위해서, 위에서 구한 소수의 집합에서 확인한다.존재하면, N = A + B를 출력하고 마친다. 참고사항10^18 이하의 숫자에 대해서는 골드바흐의 추측이 참인 것이 보증되므로, "Goldbach's conjecture is wrong."을 출력할 필요는 없다.에라토스테네스의 체를 통해 구한 소수를 별도의 배열로 생성하여 범위를 줄이면 시간을 줄일 수 있..
BOJ 2960 · 에라토스테네스의 체
알고리즘 분류 : 수학 에라토스테네스의 체를 이용하는 문제이다. 자세한 내용은 이곳을 참조.주어진 규칙에 따라 숫자를 지우면서, 숫자를 카운트하면 된다. C++ 소스코드 #include bool prime[1001]; int main() { int n, k; int cnt = 0; scanf("%d %d", &n, &k); for (int i=2; i