BOJ
BOJ 2309 · 일곱 난쟁이
알고리즘 분류 : 브루트 포스 난쟁이 9명 중 7명 키의 합이 100이 되는 것을 찾는 간단한 문제다. 9명 중 2명을 빼서 100을 찾는다고 생각하면 더 쉽다. 9명의 키를 입력받으면서 모두 더한다. 입력이 끝나면 정렬한다.모두 더한 값에서 2명을 빼서 100이 되는 값을 찾는다.2명을 제외하고 순서대로 출력한다. C++ 소스코드 #include #include const int N = 9; int a[N], sum; void solve() { std::sort(a, a+N); for (int i=0; i
BOJ 3055 · 탈출
알고리즘 분류 : BFS BFS를 통해 고슴도치가 동굴까지 이동하는 최단 거리를 구하는 문제다. 1분마다 물은 상하좌우로 1칸씩 번지고, 고슴도치도 1칸씩 움직인다. 고슴도치는 물로 이동할 수 없고, 다음 시간에 물이 차는 곳으로도 갈 수 없다. 때문에 물을 먼저 Queue에 넣고, 그다음 고슴도치를 Queue에 넣어 BFS를 돌리면 된다. Queue에 고슴도치의 위치와 물의 위치가 들어가므로, 물과 고슴도치를 구별할 flag를 만든다.map struct의 변수 s가 1인 경우 고슴도치이며, 0인 경우 물이다.입력받을 때, 물(*)은 곧바로 Queue에 넣고, 고슴도치(S)는 위치를 기억해둔다.입력이 끝난 후, 고슴도치의 위치를 Queue에 넣는다.고슴도치와 물은 돌(X)로 이동할 수 없고, 비어있는 칸..
BOJ 9328 · 열쇠
알고리즘 분류 : BFS BFS를 통해 맵을 탐색하면서 문서를 얻는 문제다. 이동 가능한 위치까지 최대한 이동해서 문서를 얻어야 한다. 빌딩 밖을 나갔다가 다시 들어와서 문을 열 수 있으므로, 주어진 맵을 확장할 필요가 있다. 예를 들면 아래 그림처럼 확장한다. 맵을 입력받을 때, 가장자리를 빈 공간(.)으로 만든다. 맵의 범위가 가로(1~W), 세로(1~H)라면, 가로(0, W+1), 세로(0, H+1)를 빈 공간으로 설정하면 된다. C++ 코드에서는 빈 공간을 0으로 처리했다.열쇠를 저장할 26(알파벳 총 개수) 길이의 배열을 만들고, 열쇠가 있으면 true, 없으면 false로 처리한다.큐는 총 2가지 종류이다. 이동 위치를 나타낼 Position queue와, 문의 위치를 나타낼 Door queu..
BOJ 14442 · 벽 부수고 이동하기 2
알고리즘 분류 : BFS 2206번 '벽 부수고 이동하기'를 변형한 문제다. 이전 문제는 벽을 최대 1개까지만 부술 수 있었으나, 이번 문제는 최대 10개까지 가능하다. 1개에서 10개로 늘어난 것이므로, 풀이는 비슷하게 접근할 수 있다. 이전 문제는 이곳에서 참조. dist 배열을 통해 방문 체크를 하고 이동 거리를 저장한다.dist는 3차원 배열이며, 인덱스는 [x좌표] [y좌표] [벽 부순 횟수] 이다. C++ 소스코드 #include #include using namespace std; struct map { int x, y, w; // w is a flag for counting broken walls. 0(Unbroken) 1~10(Broken) }; int n, m, k; char a[100..
BOJ 2206 · 벽 부수고 이동하기
알고리즘 분류 : BFS BFS를 통해 최단 거리를 구할 수 있는 문제다. 미로 탐색에서 약간 변형된 문제이며, 벽을 최대 1개만 부셔서 이동할 수 있다. 벽을 부수지 않거나(0), 벽을 1개 부시는(1) 경우로 나뉜다.위의 경우를 확인하기 위해 flag를 만들고, 이를 Queue에 집어 넣는다.다음 이동에서 벽을 만난 경우, flag가 0이면 벽을 부수고 flag를 1로 바꾼다.방문 여부는 dist 배열로 체크하며, 값이 0이 아니면 방문한 곳이다.dist 배열은 3차원 배열이며, 인덱스는 [x 좌표] [y 좌표] [벽 부순 여부] 이다.마지막 인덱스가 [0]이면 벽을 부수지 않고 (N, M)에 도착한 경우이고, [1]이면 벽을 한 번 부수고 (N, M)에 도착한 경우이다. C++ 소스코드 #inclu..
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