프로그래밍
BOJ 16197 · 두 동전
알고리즘 분류 : BFS BFS 탐색을 통해 두 동전을 보드에서 떨어뜨리는 최단 거리를 구하면 된다. 동전 두 개가 동시에 움직이므로, 방문 여부를 확인할 배열을 4차원으로 설정하는 것이 좋다. '구슬 탈출'과 비슷한 문제다. 방문 여부를 확인하고 거리를 저장할 배열 dist를 4차원으로 선언한다. (동전1 X좌표, 동전1 Y좌표, 동전2 X좌표, 동전2 Y좌표)보드를 입력받을 때 가장자리를 0으로 비워두고, 입력받는다. 즉, N*M 사이즈를 (N+2)*(M+2) 사이즈로 확장한다.동전 두 개 중 하나가, 가장자리(인덱스 0, N+1 또는 0, M+1)인 경우 BFS 탐색을 중지하고 거리를 출력한다.동전이 둘 다 가장자리로 갔다면, 둘 다 떨어뜨릴 수 없으므로 무시한다.동전이 벽(#)에 부딪혔을 경우, ..
BOJ 16198 · 에너지 모으기
알고리즘 분류 : 브루트 포스 재귀 함수를 이용하여 모든 경우의 수를 구하고, 그중에서 최댓값을 구하면 된다. 에너지 구슬을 사용하면 그 에너지 구슬은 더 이상 사용하지 않기 때문에, 사용 여부를 확인할 check 배열을 만든다.에너지 구슬을 고를 때, 첫 번째 구슬과 마지막 구슬은 사용하지 않으므로 인덱스의 범위를 앞뒤로 1씩 줄인다.양옆의 구슬을 이용하여 에너지를 모을 때, 이전에 사용된 구슬인지 확인해야 한다.왼쪽이 사용된 구슬이라면 사용하지 않은 구슬이 나올 때까지 왼쪽으로 간다. 오른쪽은 반대로 확인한다.사용한 구슬의 개수가 N-2개라면 에너지의 양이 최댓값인지 확인한다. C++ 소스코드 #include int n, ans; int w[10]; bool check[10]; void solve(i..
BOJ 16506 · CPU
알고리즘 분류 : 시뮬레이션, 문자열 처리 어셈블리어 코드를 기계어로 코드로 번역하여 출력하는 문제다. 문제를 천천히 정독하여 그대로 구현하면 된다. 문자열 처리는 파이썬이 간결하고 구현하기 쉽다. C++ 소스코드 #include #include using namespace std; const string reg[] = {"000", "001", "010", "011", "100", "101", "110", "111"}; const string con[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; bool opco..
BOJ 10678 · Meeting Time
알고리즘 분류 : 브루트 포스, DFS N이 최대 16이므로, DFS를 통해 모든 경로를 만들어서 해결할 수 있다. path 에 경로를 입력받고, 인접 리스트로 활용한다. 인접 행렬로 구현해도 무방하다.DFS를 통해 모든 경로를 탐색하고 N에 도착하면 이동 거리의 합을 dist 에 추가한다.Bessie의 이동 경로와, Elsie의 이동 경로를 모두 구한다.2개의 dist 리스트에서 서로 값을 비교한다. 값이 겹치면서 가장 작은 값을 정답으로 낸다. C++ 소스코드 #include #include #include using namespace std; struct field { int x, d; }; int n, m; void dfs(vector path[], vector &dist, int now, int..
BOJ 16755 · Magnus
알고리즘 분류 : 문자열 처리 문자열에서 HONI의 개수를 출력하는 문제다. 인덱스 0부터 시작해서 문자열의 길이까지 순서대로 이동하면서 다 찾아보면 된다. C++ 소스코드 #include #include using namespace std; string s; char honi[] = "HONI"; void solve() { int k = 0, ans = 0; for (int i=0; i
BOJ 11965 · Bessie's Dream
알고리즘 분류 : 다익스트라 빨간색(0), 분홍색(1), 주황색(2), 파란색(3), 보라색(4) 등 총 5가지 색의 타일이 있는 미로를 이동하면서 탈출해야 한다. 이미 방문했던 타일을 다시 방문할 수 있으므로, 일반적인 BFS로 최단 거리를 구하기는 까다롭다. 구현할 때, 보라색(4) 타일을 유의해야 한다. 빨간색(0) 타일로는 이동할 수 없다. 다음 이동에서 0번 타일을 보면 무시한다.분홍색(1) 타일로는 이동할 수 있다. 평범한 이동을 하면 된다.주황색(2) 타일로는 이동할 수 있으며, 이 타일을 밟으면 오렌지 냄새를 풍긴다. 냄새 상태를 True로 만든다.파란색(3) 타일로는 냄새 상태가 True일 때에만 이동할 수 있다. 냄새 상태가 False라면 이동할 수 없다.보라색(4) 타일에서는 보라색 ..
BOJ 5558 · チーズ
알고리즘 분류 : BFS 쥐가 먹을 수 있는 치즈를 순서대로 먹으면서 이동하는 최단 거리를 구하는 문제다. 다음 치즈를 먹으러 이동할 때, 방문했던 곳을 다시 방문할 수 있다.치즈를 낮은 숫자부터 순서대로 먹어야 하고, 현재 먹을 수 없는 높은 숫자의 치즈는 무시하고 이동할 수 있다.위 두 가지를 잘 고려하여, BFS 탐색을 해야 한다. 우선 BFS를 통해 먹을 수 있는 치즈를 찾고, 먹은 위치와 이동 거리를 저장한 후 BFS를 종료한다.방문 여부를 확인하는 check 배열을 초기화하고, 위에서 먹은 위치부터 다음 치즈까지 BFS 탐색을 다시 시작한다.즉, 시작점 → 1번 치즈, 1번 치즈 → 2번 치즈, ···, N-1번 치즈 → N번 치즈 순으로 BFS를 돌리면 된다. C++ 소스코드 #include..
BOJ 16769 · Mixing Milk
알고리즘 분류 : 시뮬레이션 1 → 2, 2 → 3, 3 → 1 (X → Y)을 순서대로 100번 해서 각 양동이에 우유가 얼마나 남았는지 확인하는 문제다. 순서대로 100번만 반복하면 된다. 우선 옮기기 전에, X번 양동이에 남아있는 우유의 양과 Y번 양동이에 남아있는 우유의 양을 더해서 temp에 저장해둔다.Y번 양동이의 최대치(C)와 temp와 비교한다.temp가 C보다 크거나 같을 경우 (temp - C)를 X번 양동이에 저장하고, 아니라면 0을 X번 양동이에 저장한다.Y번 양동이의 최대치(C)와 temp를 다시 비교한다.temp가 C보다 크거나 같을 경우 C를 Y번 양동이에 저장하고, 아니라면 temp를 Y번 양동이에 저장한다.위 과정을 100번 반복한다. C++ 소스코드 #include int..