BOJ
BOJ 14891 · 톱니바퀴
알고리즘 분류 : 시뮬레이션 톱니바퀴의 회전 동작을 시뮬레이션하는 문제다. 문제는 어렵지 않으나, 회전 방향이 헷갈려서 귀찮은 문제다. 입력으로 주어지는 톱니바퀴를 기준으로 시작한다.톱니바퀴의 인덱스는 12시 방향부터 시계방향으로 [ 0 1 2 3 4 5 6 7 ] 로 둔다.1. 기준 톱니바퀴의 왼쪽에 톱니바퀴가 있다면, 기준 톱니바퀴의 왼쪽 톱니(인덱스 6)와 왼쪽 톱니바퀴의 오른쪽 톱니(인덱스 2)를 비교한다.2. 극이 다르다면, 왼쪽 톱니바퀴의 회전 방향을 기준 톱니바퀴의 반대 회전 방향으로 저장한다.첫 번째 톱니바퀴까지 1~2 과정을 반복하여, 회전 방향을 저장해둔다.3. 기준 톱니바퀴의 오른쪽에 톱니바퀴가 있다면, 기준 톱니바퀴의 오른쪽 톱니(인덱스 2)와 오른쪽 톱니바퀴의 왼쪽 톱니(인덱스 6..
BOJ 3190 · 뱀
알고리즘 분류 : 시뮬레이션 주어진 조건을 그대로 구현하는 시뮬레이션 문제다. 뱀이 사과를 먹으면서 길이를 늘리는 게임을 구현해야 한다. 뱀의 시작 위치는 (0, 0)이며 시작 방향은 오른쪽이다. 범위 (0, 0) ~ (N-1, M-1) 기준뱀의 이동 좌표를 저장하기 위해 Queue를 사용한다.매초, 뱀이 현재 방향으로 머리를 먼저 한 칸 앞으로 옮긴다. 머리 위치를 큐에 push 한다.이동한 칸에 사과(1)가 있을 경우, 꼬리를 줄이지 않는다.이동한 칸이 빈칸(0)이라면, 꼬리를 한 칸 줄인다. 큐에서 꼬리 칸을 pop 한다.뱀의 좌표는 (2)로 둔다.이동 후에, 방향 전환을 해야 한다면, 주어진 입력에 따라 방향을 바꾼다.이동할 때 벽에 부딪히거나(맵을 벗어난 경우), 뱀 자신(2)에게 부딪히면 종료..
BOJ 14499 · 주사위 굴리기
알고리즘 분류 : 시뮬레이션 문제에 주어진 조건에 따라 주사위를 굴리는 문제다. 먼저 주사위의 숫자를 임의로 고정시킨다.동서남북 방향에 따라 바뀌는 주사위의 숫자를 설정한다.방향에 따라 시뮬레이션 한다.아래의 그림을 참조. 주사위 모양에서 0이 윗면이고, 5가 바닥면이다. C++ 소스코드 #include int n, m, x, y, k; int a[20][20]; int dice[6], temp[6]; const int direct[4][6] = { {2, 1, 5, 0, 4, 3}, {3, 1, 0, 5, 4, 2}, {4, 0, 2, 3, 5, 1}, {1, 5, 2, 3, 0, 4} }; const int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0}; void sol..
BOJ 13458 · 시험 감독
알고리즘 분류 : 시뮬레이션 문제에 주어진 조건 그대로 구현하면 된다. 총 감독관은 항상 1명 존재하므로, 문제의 정답은 N명 이상이다.부 감독관은 각 시험장에 남아있는 응시자의 수를 부 감독관 수로 나눠서 구할 수 있다. C++ 소스코드 #include int n, b, c; int a[1000000]; long ans; void solve() { for (int i=0; i= b) { int d = a[i]-b; ans += (d%c == 0 ? d/c : d/c+1); } } printf("%lld\n", ans+n); } int main() { scanf("%d", &n); for (int i=0; i= b: d = a[i]-b ans += d//c if d%c == 0 else d//c+1 pr..
BOJ 14502 · 연구소
알고리즘 분류 : 브루트 포스, DFS 연구소에 벽을 3개 세워서 바이러스를 최대한 덜 퍼트리고, 안전 영역의 최대 크기를 구하는 문제다. N*M은 최대 64이므로, 벽을 두는 모든 경우의 수를 구해서 최대 크기를 확인해 볼 수 있다. 우선 입력으로 받은 맵에 벽을 3개 세워야 한다.벽(1)은 빈 칸(0)에만 세울 수 있다. N*M을 순회하면서 빈 칸이라면 벽을 둔다.벽을 두는 함수는 재귀로 구현한다. 벽 카운트를 세면서 3이 되면, DFS를 통해 빈 칸에 바이러스(2)를 퍼트린다.바이러스를 퍼트리면서, 바이러스가 퍼진 칸을 센다.바이러스 칸이 최소가 될 때, 안전 영역의 크기가 최대가 된다. C++ 소스코드 #include #include #include using namespace std; int n..
BOJ 2151 · 거울 설치
알고리즘 분류 : BFS 문에서 다른 문까지 빛으로 연결하기 위해 필요한 거울의 최소 개수를 구하는 문제다. 빛은 거울에서만 꺾이고, 거울은 45도 각도로 설치할 수 있다. 거울을 적절히 설치해서 문에서 문으로 빛을 연결해야 한다. 문('#')은 항상 2개만 주어지므로, 하나의 문을 시작점으로, 다른 하나의 문은 도착점으로 둔다.BFS 탐색을 하면서 다음 이동 좌표가 갈 수 있는 곳인지 확인한다.방문 체크와 거울 설치 횟수를 저장할 배열 dist를 3차원으로 선언한다.dist의 인덱스는 [X 좌표] [Y좌표] [이동 방향] 이다.만약 다음 이동 좌표가 맵의 밖이거나 벽('*')이라면, 이동할 수 없다.다음 이동 좌표가 빈 공간('.')이라면, 계속 이동한다.while 반복문을 통해 다음 이동이 가능한 위..
BOJ 3197 · 백조의 호수
알고리즘 분류 : BFS 두 마리의 백조가 서로 만나는 데 걸리는 시간을 구하는 문제다. 백조는 빙판을 지날 수 없으며, 물로만 이동이 가능하다. 또한, 매일 물과 인접한 빙판이 녹아서 물로 변한다.입력으로 주어지는 맵의 범위가 최대 1500*1500이므로, 일반적인 BFS 방법으로는 시간 초과가 나온다. 여러 방법이 있겠지만, 아래 코드에서는 큐(Queue) 4개를 이용하는 방법을 사용했다. 빙판이 물로 녹는 BFS와, 백조가 이동하는 BFS를 따로 나눈다.물을 위한 큐는 wq1, wq2가 있고, 백조를 위한 큐는 sq1, sq2가 있다.입력으로 주어지는 호수 맵에서 물('.')의 좌표를 wq1에 모두 넣는다.호수 맵에서 백조('L')의 좌표를 sq1에 하나 넣고, 다른 하나의 백조 위치는 도착 위치(..
BOJ 2234 · 성곽
알고리즘 분류 : DFS 성을 DFS로 탐색하면서 3가지 값을 구해야 한다. 첫 번째는 성에 있는 방의 개수(A), 두 번째는 가장 큰 방의 넓이(B), 세 번째는 벽 하나를 제거해서 얻을 수 있는 가장 큰 방의 넓이(C)이다. 입력으로 주어지는 맵을 DFS로 탐색한다.현재 칸을 (X, Y)라 할 때, check[X][Y]를 숫자 Z로 채운다.다음 칸으로 이동하기 전에 벽으로 막혀있는지 확인한다.벽을 확인하는 방법은 a[X][Y] & (1