알고리즘 문제 풀이/BOJ

[ 풀이 방법 ]1. 물고기의 수가 가장 적은 어항에 물고기 한 마리를 넣는 기능  - min_element()를 이용해 최소값 찾고, 최소값이 저장된 어항(board)의 물고기의 수를 1씩 증가시킨다. 2. 어항 쌓기 기능  - 시작 좌표(initX, initY)와 목표 좌표(targetX, targetY)를 설정하고 시작 좌표의 값을 목표 좌표로 옮겨 구현한다.      - 시작 좌표는 (N-1, 0), 목표 좌표는 (N - 2, initY + 1)에서 시작한다.      - 이후, 시작 좌표의 y좌표는 (이전 반복에서 값이 실제로 옮겨진 targetY의 최대값), 목표좌표의 y좌표는 (initY+반복 횟수)에서 시작한다.      - 2중 loop를 이용해 시작 좌표와 목표 좌표의 위치를 이동하며 ..

[ 풀이 방법 ] 1. 복제 마법 시전 기능 - AUX 배열(aux)에 현재 배열(board)에 저장된 물고기와 방향을 저장한다. 2. 물고기 이동 기능 - 물고기 구조체를 별도의 배열에 저장해둔 뒤 순회하며 물고기 이동을 구현 - 물고기 구조체(x, y 좌표와 방향, 상어에게 먹혔는지 여부 저장) - 물고기 구조체 배열(fish)과 물고기 위치를 저장한 2차원 배열(board) 모두에 물고기 이동 결과를 갱신. - 상어에게 이미 먹힌 물고기는 스킵한다. - 물고기의 방향으로 한 칸 이동 - 이동해야 할 위치가 board의 범위를 벗어나거나, 상어가 있거나, 물고기 냄새가 남아았는 경우 물고기 이동 불가 - 물고기 이동 불가한 경우, 물고기가 이동 가능할 때까지 45도 반시계 방향으로 물고기 방향 회전 ..

[ 풀이 방법 ] 1. 온풍기 방향으로 바람을 내보내는 기능 - 온풍기 위치에서 온풍기 방향으로 한 칸 이동한 칸부터 BFS 시작 - 온풍기 방향에 따라 벽의 위치 확인하여 탐색 가능한 칸만 탐색 (벽에 막히거나, 보드의 범위 벗어나거나, 이미 탐색했거나, 첫 탐색 위치로부터 5칸 이상 떨어진 경우 탐색 X) - 상, 하: 해당 칸과 해당 칸의 좌, 우로 한 칸 이동한 후의 칸에서 온풍기 방향으로 한 칸 이동하는 경우 탐색 - 좌, 우: 해당 칸과 해당 칸의 상, 하로 한 칸 이동한 후의 칸에서 온풍기 방향으로 한 칸 이동하는 경우 탐색 - 이미 탐색한 칸은 탐색하지 않기 위해 visited 배열 사용 - 첫 탐색 위치의 칸은 5(=k), 이후로는 --k 씩 해당 칸의 온도 증가 2. 온도 조절 기능 -..

[ 풀이 방법 ] 1. 주사위의 다음 이동 방향을 정하는 기능 - 처음엔 동쪽 방향으로 이동 - 이후로는 주사위 아랫면의 정수(A)와 보드의 해당 칸의 정수(B)를 비교하여 이동 방향을 결정한다. - A > B: 현재 방향에서 90도 시계 방향으로 회전한다. - A < B: 현재 방향에서 90도 반시계 방향으로 회전한다. - A = B: 현재 방향 그대로, 만약 다음 이동 시 보드 칸을 벗어난다면 이동 방향을 반대로 한다. - 주사위 구조체에 다음 이동 방향과 현재 위치를 저장하여 구현한다. 2. 주사위 이동 기능 - 1에서 정한 이동 방향으로 주사위를 한 칸 이동하는 기능 - 주사위의 위치 이동 + 주사위를 이동 방향으로 굴림 - 주사위 구조체에 위, 아래, 왼쪽, 오른쪽, 앞, 뒤에 적힌 정수를 저장..

노드의 개수가 최대 500000, 선분의 개수가 최대 500000이므로 최대 O(n+m log n+m)인 알고리즘을 사용해야 한다. union-find 알고리즘을 사용해 문제를 해결했다. [ 정답 코드 ] #include #include #include using namespace std; int N, M; vector parent; int res = 1; int findParent(int u) { if(parent[u] == u) return u; return findParent(parent[u]); } void mergeUV(int u, int v) { u = findParent(u); v = findParent(v); if(u == v) return; if(u < v) { parent[v] = u;..

[ 풀이 방법 ] 1. 블리자드 마법 시전 기능 - 상어 위치에서 d방향으로 s칸 이내의 모든 칸의 구슬을 파괴하는 기능 - board의 해당 칸을 모두 0으로 초기화 - 방향은 ↑, ↓, ←, → 순서대로 0, 1, 2, 3을 할당 2. 구슬 이동 기능 - 문제에서 주어진 반시계 방향 순서대로 탐색하며 빈 칸의 개수를 세고 빈 칸의 개수만큼 구슬을 시계 방향으로 이동하도록 구현 3. 구슬 폭발 기능 - 문제에서 주어진 반시계 방향 순서대로 탐색하며 동일한 구슬 번호가 연속해서 몇 번 나오는지 세고, 4번 이상 나왔다면 해당 구슬들을 모두 파괴하도록 구현 - 반시계 방향으로 탐색하는 과정에서 동일한 구슬 번호가 나오면 cnt++, - 다른 구슬 번호가 나오면 시계 방향으로 cnt번 탐색하며 해당 위치를 ..

[ 풀이 방법 ] 비구름 생성 -> 이동 -> 바구니의 물의 양 증가 -> 비구름 제거 -> 물복사버그 위 과정이 반복된다. 1. 비구름을 생성하는 기능 - 2차원 배열인 board를 이용해 바구니의 뮬의 양을 저장한다. - 2차원 배열인 rain을 이용해 비구름의 위치를 저장한다. - 2차원 배열인 pre를 이용해 비구름이 제거된 위치를 저장한다. - 첫 비구름은 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 생성된다. - rain 배열의 좌측 하단 4칸을 true로 초기화한다. - 그 이외의 비구름은 바구니에 담긴 물의 양이 2 이상인 칸의 위치에서 생성된다. - 이 때, 바구니의 물의 양이 2 줄어든다. - 이전 반복에서 해당 위치의 비구름이 제거되었다면 현재 반복에서는 해당 위치..

[ 풀이 방법 ] 1. 크기가 가장 큰 블록 그룹을 찾는 기능 2. 크기가 가장 큰 블록 그룹이 여러개인 경우, 그룹에 포함된 무지개 블록의 수가 가장 많은 그룹을 찾는 기능 - 아직 탐색하지 않은 일반 블록의 위치를 행과 열이 작은 순서대로 찾고, 찾은 위치에서부터 DFS를 시작해 같은 블록이 들어있거나 무지개 블록이 있는 위치를 방문 처리하며 크기와 무지개 블록 개수를 구한다. - 구한 크기와 무지개 블록 개수를 비교하여 저장된 최대 블록 그룹 크기와 기준 블록을 갱신한다. - 이 때, 행과 열이 작은 순서대로 탐색되기 때문에, 탐색한 그룹의 크기와 무지개 블록 개수가 저장된 최대 블록 크기 그룹과 같다면 나중에 탐색된 그룹으로 갱신하여 "기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가..