내가 헷갈렸던 지점은

분명 DFS 문제 풀이때는 2차원 벡터를 매개변수로 받았을 때, 직접 값을 변경해주기 위해 &를 사용했었는데, 왜 BFS에서는 큐의 원소로 vertex 구조체를 넣으면서 관리하려니 안되는걸까?

우선 DFS에서 &가 잘 동작했던 이유는

• void dfs(vector<vector<int>>& grid
  • grid는 하나의 객체
  • 함수 안에서도 그 동일 객체를 계속 사용

  • 즉, 참조 하나로 충분

& (Reference)

• Vertex& a = b;

  • a는 b의 별명이다.
  • 한 번 연결되면 다른 객체로 바꿀 수 없다. 즉, 이 정점의 parent를 나중에 정점으로 바꾼다거나, 여러 정점을 컨테이너에 넣고 연결한다. 와 같은 동작이 불가능하거나 매우 제한되는 것.

단순히 '값 복사를 피하면서 직접 수정이 가능하다'가 아니라, 한 번 연결된 경우 수정이 불가한 비가역적인 기능이었다.

* (Pointer)

Vertex* p = &a;
p = &b;

• 포인터는 주소를 저장하는 변수이기 때문에 a의 주소를 저장해두었다.
• 포인터 p의 경우 저장중인 주소값을 다른 값으로 변경할 수 있다.
• 따라서 여러 객체를 자유롭게 연결할 수 있는 것이다.
• 여기서 쓰인 &는 참조가 아니라, 주소를 가져오는 연산자이다.

정리하자면, 핵심 원인은 값 복사 vs 동일 객체 참조의 차이였고, 나는 그 기능을 잘 이해하지 못한 채 참조 기능을 오용 및 남용하고 있었다.

최종 정리

참조(&)는 복사를 막고, 같은 객체를 쓰게 해주는 도구. 포인터(*)는 객체들 간의 연결 구조를 만들 수 있는 도구.

• Characterize the sutructure of an optimal solution
• Recursively define the vaule of an optimal solution
• Compute the value of an optimal solution in a bottom-up fashion
• Construct an optimal solution from computed information

In order for dynamic programming to apply, the problem must have

1. Optimal substructure

   • 전체 최적해는 부분문제들의 최적해들로 이루어진다.
   • 어떤 문제가 optimal substructure를 가지면, 그 문제는 동적 계획법을 적용할 수 있는 강한 신호이다.
   • 동적 계획법에서는 부분문제들의 최적해를 이용하여 전체 문제의 최적해를 구성한다.
   • 결과적으로, 우리가 고려하는 부분문제의 범위가 최적해를 구성하는 데 사용되는 부분문제들을 포함하도록 보장해야 한다.

   • 최적해를 구성하는 데 필요한 ‘모든 종류의 부분문제 상태’가 정의 안에 포함되어야 한다.

2. Overlapping subproblems

   • When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has "overlapping subproblems".

재귀식은 아래와 같다.

T(n) = T(i) + T(n-i-1) + n

// 1, 2, ..., i, i+1(pivot), i+2, ..., n-1, n
// 즉, 좌집합 T(i), 우집합 (n-i-1)에 대한 Conquer 진행.
// 뒤의 n은 combine과정이 아니라 Partition cost를 의미한다.

따라서, Worst case는 피봇 기준 어느 한 쪽으로 계속 치우쳐지는 경우로,

T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     ...
     = T(1) + 2 + 3 + ... + (n-1) + n
     = T(1) + (n+2)*(n-1)/2
     = O(n^2)

반면, Best case는 피봇 기준 항상 n/2로 나눠지는 경우로,

T(n) = 2*T(n/2) + n

Master method에 의해 n^log2(2) = n이 f(n) = n과 같으므로
Theta(nlog(n)).

정리하기보단 직접 풀면서 공부하는 게 훨씬 효율이 좋은 듯 하여 여기까지만 기록하기로.

template <class T>
void QuickSort(T *a, const int left, const int right)
{ 
// Sort a[left:right] into nondecreasing order.
// a[left] is arbitrarily chosen as the pivot. Variables i and j
// are used to partition the subarray so that at any time a[m] ≤ pivot, m < i
// and a[m] ≥ pivot, m > j. It is assumed that a[left] ≤ a[right + 1]

if (left < right) { int i=left, j = right + 1, pivot = a[left]; do { do i++; while (a[i] < pivot); do j--; while (a[j] > pivot); if(i < j) swap(a[i], a[j]); } while (i<j);

swap(a[left], a[j]);
QuickSort(a, left, j-1);
QuickSort(a, j+1, right);
}

}

```

• 재귀 호출이 partition 작업이 끝난 후에야 수행되는 것을 볼 수 있다.
• partition이 In-place 방식이다.

Loop Invariant

복습) Initialization : It is true prior to the first iteration of the loop. Maintenance : If it is true before an iteration of the loop, it remains true before the next iteration. Termination : When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Build-Max-Heap의 Loop Invariant

At the start of each iteration of the for loop, each node i+1, i+2, ..., n-1, n is the root of a max-heap.

Initialization

• At the start of the for loop, i = floor(A.length/2). Each node i+1, i+2 ... n은 리프노드이므로 자명한 max heap이다.

• L.I hold

Maintenance

• L.I에 의해 i의 두 자식들은 max heap이다. max-heapify(A, i)는 i를 루트 노드로 하는 서브트리를 max-heap으로 만들어주며, i+1, i+2, ..., n을 각각 루트노드로 하는 서브트리에 대해 max heap 성질을 유지한다.
• i를 감소시키면 다음 수행을 위한 L.I가 여전히 만족한다. "i, i+1, i+2, ..., n-1, n에 대해 ~"

Termination

• i가 0일 때 종료. 이를 L.I에 넣어보면,
• Each node 1, 2, ..., n is the root of a max-heap이 되며, 이는 node 1을 루트로 하는 서브트리, 즉 전체 트리가 max-heap이라는 뜻이다.

• 그러므로 Build-max-heap은 max heap을 만드는 데에 correct algorithm.

Simpler Upper Bound

• Build-max-heap 자체가 i = floor(n/2)부터 1까지 순회하므로 O(n), 각 순회마다 O(logn)이 걸리는 Max-Heapify를 콜한다.

Tighter Upper Bound

• Max-Heapify는 트리 높이가 h일 때 O(h)의 시간이 걸린다.
• 높이 h는 전체 노드 n개일 때 floor(log(n))이다.
  height : 그 노드에서 아래로 내려가 리프에 도달하는 가장 긴 경로의 간선 수 depth : 루트에서부터의 거라. level이라고도 함.

• 중간에 +1을 넣어서 ceil fn을 벗겨내는 디테일 좋다.

따라서, Build max heap의 upper bound를 더욱 타이트하게 잡아보면 O(nlog(n))에서 O(n)까지 만들 수 있다.

Another Analysis of Building a Heap

Let's assume the tree is Complete binary tree. 그러면 노드의 총 개수 n은 2^h - 1개가 된다.

• 높이가 h인 노드의 개수는 1개이며, 이 노드에서 max heapify는 최악의 경우 h만큼 내려간다.
• 높이가 h-1인 노드의 개수는 2개이며, 이 노드에서는 h-1만큼 내려간다. ...
• 이를 식으로 표현해보면 cost S = h + 2(h-1) + 2^2(h-2) + 2^3(h-3) + ... + 2^(h-1)\(1) + 2^h*0 2S = 2h + 2^2(h-1) + 2^3(h-2) + ... + 2^h(1) ... S = 2*2^(log(n)) - log(n) - 2 <= 2n

Heapsort

1. Build max heap을 통해 max-heap으로 만든다.
2. 최댓값이 항상 root에 있으므로 맨 마지막 원소인 A[n]과 A[1]을 교환한다.
3. Max-heapify(A,1)을 A[1...n-1]까지 수행한다.
4. heap의 사이즈가 2가 될 때까지 1~3 과정 반복. -> 어차피 A[1]과 A[2]는 이미 정렬되어있기 때문.

Running time

• Build max heap : O(n)
• Each of the n-1 calls to Max-Heapify takes O(lgn) time.

• O(nlgn)

Priority Queue

MAX_HEAP_INCREASE_KEY(A, i, key)
if (key < A[i])
    return "new key is smaller than current key"

A[i] = key
while i > 1 && A[parent(i)] < A[i]
    exchange(A[parent(i)], A[i])
    i = parent(i)

MAX_HEAP_INSERT(A, key)
A.heap-size = A.heap-size + 1
A[heap-size] = -Inf
MAX_HEAP_INCREASE_KEY(A, A.heap-size, key)

vs Insertion sort,

1. in-place.
2. running time is O(nlgn).

vs Merge sort,

1. running time is same as O(nlgn).
2. it does not require O(n) additional space.

-> Heap sort를 선택하는 대표 조건은 "추가 메모리를 거의 못 쓰면서도, 항상 O(nlgn) 성능을 보장해야 할 때" 이다.

Heap

배열 A에서

• A.length : the number of elements in the array
• A.heap-size : the number of elements in the heap
• only the elements in A[1...A.heap-size], where 0 <= A.heap-size <= A.length are valid elements of the heap.
• A[1] is the root of the tree
• index i가 있을 때
  • 2i : left child (if 2i <= A.heap-size)
  • 2i + 1 : right child (if 2i + 1 <= A.heap-size)
  • parent : floor(i/2)
• The height of a node is the number of edges on the longest simple downward path from the node to a leaf.
• Since a heap of n elements is based on a complete binary tree, its height is O(lgn).
• The height of the heap is the height of the root.

Max Heapify

시간복잡도 분석

• 어떤 노드 i를 루트로 하는 서브트리의 크기가 n이라고 하자.
• 즉, i 아래에 총 n개의 노드가 있다고 하자.

• 그럼 이 노드의 자식 중 하나가 가질 수 있는 최대 서브트리 크기는 얼마인가?

왜 subtree의 사이즈는 최대 2n/3을 못넘기는가?

높이가 0 ~ H-1인 완전이진트리가 있다고 하자.
전체 노드 수는 2^H - 1개.
>
높이가 1인 두 노드중 좌측 노드를 루트 노드로 하는 서브 트리를 LST라 하자. 
LST의 크기는 2^(H-1) - 1개.
>
LST에만 리프노드를 전부 채운다고 하면, 이 때 리프노드의 개수는 2^(H-1)개. 
전체 노드 개수와 LST에 리프노드 개수를 각각 더해주면
전체 노드 개수는 2^H - 1 + 2^(H-1) = 3/2 * 2^H - 1
>
LST의 개수는 2^H - 1
>
따라서
LST/전체노드개수 = 2^H - 1 / (3/2 * 2^H - 1) = 약 2/3

그래서 아래 문장도 설명된다.

• For a subtree of size n rooted at a given node i, the size of the subree rooted at a child of node i becomes maximum when the bottom level of the tree is exactly half full.

• 노드 i를 루트로 하는 사이즈 n짜리 서브트리에서의 수행 시간은 다음으로 이루어져 있다.

1. A[i], A[left], A[right] 정렬 - Theta(1).
2. T(2n/3) to recursively process on a subtree rooted at one of the children of node i.

• 이를 정리하면 T(n) <= T(2n/3) + Theta(1) 인 것. 그러므로 부등식임에 따라 T(n) = O(lgn)이다.

우리가 보이고 싶은 명제는 "전체 배열의 maximum subarray는

1. 왼쪽 부분 배열의 maximum subarray
2. 오른쪽 부분 배열의 maximum subarray
3. mid를 가로지르는 maximum subarray

위 세 가지 중 하나이다."

전체 배열의 최적해 A[i...j]를 하나 잡았다고 하자.

1. 최적해의 원소들이 전부 mid보다 왼쪽 구간에 있으면 A[i...j]는 왼쪽 부분배열 안에서의 maximum subarray이다.
   • 만약 왼쪽 구간에 A[i...j]보다 합이 더 큰 부분배열 A[p...q]가 존재한다면
   • 이는 기존 최적해 A[i...j]를 A[p...q]로 잘라 붙여 더 큰 합의 해를 만들 수 있기 때문에 A[i...j]가 최적해라는 가정에 모순이 된다.
   • 따라서 A[i...j]는 왼쪽 부분배열의 maximum subarray이다.

2. 최적해의 원소들이 전부 mid보다 오른쪽 구간에 있으면 A[i...j]는 오른쪽 부분배열 안에서의 maximum subarray이다.

   • 만약 오른쪽 구간에 A[i...j]보다 합이 더 큰 부분배열 A[p...q]가 존재한다면
   • 이는 기존 최적해 A[i...j]를 A[p...q]로 잘라 붙여 더 큰 합의 해를 만들 수 있기 때문에 A[i...j]가 최적해라는 가정에 모순이 된다.

3. 최적해의 원소들중 mid를 지나는 원소가 있다면, A[i...j]는 crossing array중 maximum subarray이다.

   • crossing 최적해 A[i...j]는 왼쪽은 mid에서 끝나는 최대 suffix, 오른쪽은 mid+1에서 시작하는 최대 prefix의 결합이다.
   • 만약 A[i...mid]보다 합이 더 큰 suffix A[p...mid]가 존재한다면
   • A[i...j]를 A[p...j]로 교체할 수 있다.
   • 이는 기존 최적해 A[i...j]보다 더 큰 합의 해를 만들 수 있기 때문에 A[i...j]가 최적해라는 가정에 모순이 된다.
   • 따라서 A[i...mid]는 최대 suffix이다.
   • 마찬가지로, 만약 A[mid+1...j]보다 더 큰 prefix A[mid+1...q]가 존재한다면
   • A[i...j]를 A[i...q]로 교체할 수 있으므로 가정에 모순이다.
   • 따라서 A[i...mid]는 mid에서 끝나는 최대 suffix, A[mid+1...j]는 mid+1에서 시작하는 최대 prefix 형태이며, 따라서 이는 crossing subarray들중 maximum subarray이다.

MSP in Linear time

#include <iostream>
using namespace std;

int main() {
    int arr[11] = { 0, 2, -3, 5, -1, -2, -4, 10, 7, -2, -3};

    int thisSum = 0;
    int maxSum = 0;
    for (int i = 1; i <= 10; i++) {
        thisSum += arr[i];
        if (thisSum > maxSum) {
            maxSum = thisSum;
        }
        else if (thisSum < maxSum) {
            thisSum = 0;
        }
    }

    cout << maxSum;

    return 0;
}

• linear time의 장점

1. 메모리 효율
   • 스트리밍처럼 한 번 쭉 읽으면서 처리가 가능하기 때문에
   • 배열 전체를 메모리에 다 올릴 필요가 없다.
   • 데이터를 앞에서부터 한 번씩만 읽으면서 처리 가능하다.
2. 실시간 처리 (Online)
   • 데이터를 끝까지 다 보지 않아도, 지금까지 읽은 부분에 대해서는 항상 정답을 알고 있다.
   • 즉, 중간 과정에서도 항상 지금까지의 정답이 유지되고 있다.

왜 갑자기 재귀?

• Divide and Conquer 알고리즘의 수행 시간을 분석하는 데 가장 자연스러운 접근법.

Methods for solving Recurrences

1. Brute-force method
2. Substitution method
3. Recursion tree method
4. Master method

Inequality Recurrences

만약 T(n) = 2 * T(n/2) + Theta(n) 이런 식으로 주어졌다면 Theta notation 사용이 가능하지만, 부등식일 경우 불가능하다.

• T(n) <= 2 * T(n/2) + Theta(n)

• 상한이 주어졌으므로 Big-O notation 사용.

• T(n) >= 2 * T(n/2) + theta(n)

• 하한이 주어졌으므로 Big-Omega notation 사용.

Brute-force Method

[ex 1]
T(n) = 2 * T(n/2) + n
     = 2 * (2 * T(n/4) + n/2) + n = 2^2 * T(n/2^2) + 2n
     = 2 * (2 * (2 * T(n/8) + n/4) + n/2) + n = 2^3 * T(n/2^3) + 3n
     ...
     = 2^k * T(n/2^k) + kn = n*T(1) + log(n) * n
     = O(nlogn)

[ex 2]
T(n) = 2 * T(n/2) + n
T(n)/n = T(n/2)/(n/2) + 1
T(n/2)/(n/2) = T(n/4)/(n/4) + 1
...
T(2)/2 = T(1)/1 + 1

T(n)/n = T(1)/1 + 1 + 1 + 1 + ... + 1 + 1 = n + logn
T(n) = nlogn

Substitution Method

1. Guess the form of the solution.
2. Use mathematical induction to find the costants and show that the solution works.

• 만약 어떤 상수나 낮은 차수에 의해 기존의 증명하려던 식이 성립하지 않을 경우, 해당 차수를 관리할 수 있는 임의의 조작을 해주어야 한다.

Avoiding Pitfalls

귀납 증명은 "정확히 같은 형태"로 돌아와야 한다.

Changing Variables

점화식이 이상하면 변수 치환으로 바꿔라.

Recursion-tree Method

재귀 호출 구조를 트리 형태로 표현한 뒤, 각 레벨에서 발생하는 총 비용을 계산하고 이를 모두 더하여 전체 수행 시간을 구하는 방법이다.

Master Method

T(n) = a*T(n/b) + f(n)에서 a >= 1, b > 1인 상수이며 f(n)이 점근적으로 양수 함수일 때 사용하는 방법.

a가 1보다 크거나 같아야 하고, b가 1보다 커야 하는 이유가 뭘까. 결국 b가 1보다 커야 문제가 기존보다 작은 부분문제로 감소하기 때문이며, a역시 1보다 크거나 같아야 하는 이유는 주어진 문제를 적어도 1회 이상은 온전히 푸는 구조여야 Divide and Conquer의 구조를 유지하기 때문인가?

b는 몇 개로 쪼개질 것인가, a는 하위 문제의 개수가 몇 개인가를 담당해야 하기에 저런 조건을 세운 듯 하다.

n^log_b(a) 이 식은 결국 Divide and Conquer를 하는 과정에서 생기는 총 작업량을 의미한다. 또한, f(n)은 각 레벨에서의 노드 처리 작업량을 의미한다.

따라서, 두 식을 비교하여 더 큰 값이 있다면 해당 값이 다른 값을 무시할 수 있기에 해당 값이 답인 것이고, 두 값이 같다면 곱해주어야 한다.

Master method를 보면 Divide and Conquer 알고리즘의 핵심 골격을 알 수 있는 것이다.

We can predict how an algorithm will perform for large input sets, based on its performance for moderate input sets.

Big-Θ

Θ(g(n)) = { f(n): there exist positive c1, c2, and n0 such that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0 }.

• 집합이므로 f(n)이 Θ(g(n))에 포함된다고 표기할 수 있다. 다만 표기상 f(n) = Θ(g(n))이라고 한다.
• Θ(g(n))에 속하는 모든 함수 f(n)은 충분히 큰 n에 대해 0 이상이어야 한다.
  • 왜냐, 어차피 성장률 비교이기 때문에.
  • 만약 음수가 된다면, Θ(g(n))은 공집합이 된다.

Big-O

Θ에서 하한이 없어진 버전. O(g(n)) = {f(n) : there exist positive constants c, n0 such that 0 <= f(n) <= c*g(n) for all n >= n0}.

Big-Ω

Θ에서 상한이 없어진 버전. Ω(g(n)) = {f(n) : there exist positive constants c, n0 such that c*g(n) <= f(n) for all n >= n0}.

Properties

• if T1(n) = O(f(n)) && T2(n) = O(g(N)),
  • T1(n) + T2(n) = max(O(f(n)), O(g(n))
• T1(n) * T2(n) = O(f(n) * g(n))
• O(c * f(n)) = O(f(n))

  Names

• O(n^3) : Cubic
• O(n^2) : Quadratic
• O(nlogn)
• O(n) : Linear

Theorem 3.1

For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)). -> 즉, 하한과 상한의 함수가 같아야 세타가 존재한다.

Growth compare

log(n) < n < nlog(n) < n^2 < 2^n

Divide and Conquer

핵심 성질

• Divide : 더 작은 동일 문제로 나눈다.
• Conquer : 재귀로 해결한다.
• Combine : 부분해를 combine하여 전체해로 만든다.

merge sort에서의 Divide and conquer 접목

Divide -> 정렬할 n개의 원소로 이루어진 수열을 각각 n/2개의 원소를 가지는 2개의 부분수열로 나눈다.

Conquer -> 두 개의 부분수열을 merge sort을 통해 재귀적으로 정렬한다.

Combine -> 두 개의 정렬된 부분수열을 merge하여 전체가 정렬된 정답을 만든다.

Merge Procedure

• It merges them to form a single sorted subarray that replaces the current subarray A[p...r].

• we assume that the subarray A[p...q] and A[q+1...r] are in sorted order.
• MERGE(A, p, q, r) 보조 함수로 해당 기능을 수행한다.

MERGE(A, p, q, r)    A : p ~ r
n1 = q - p + 1
n2 = r - q

Let L = [1 ... n1 + 1] and R = [1 ... n2 + 1]
for i = 1 to n1
    L[i] = A[p + i - 1]
for j = 1 to n2
    R[j] = A[q + j]

L[n1 + 1] = Inf
R[n2 + 1] = Inf
i = 1
j = 1
for k = p to r
    if L[i] <= R[j]
        A[k] = L[i]
        i++
    else
        A[k] = R[j]
        j++

Correctness of Merge Procedure

• Loop Invariant(L.I)

• At the start of each iteration for the merging loop, the subarray A[p...k-1] contains the (k - p) smallest elements of L[1...n1+1] and R[1...n2+1], in ascending order.

• Moreover, L[i] and R[j] is the smallest element of their arrays that have not been copied back into A.

Initialization

• 첫 루프 진입 전 k는 p이고, i와 j는 모두 1이다. 이를 Loop invariant에 넣어보자.
  • At the start of each iteration for the merging loop, the subarray A[p...p-1] contains the (p - p = 0) smallest elements of L[1...n1+1] and R[1...n2+1], in ascending order.

  • A[p...p-1]은 공집합이다.

  • 이 집합은 0개의 가장 작은 원소들(in L, R)을 갖고 있다.

  • Moreover, L[1] and R[1] is the smallest element of their arrays that have not been copied back into A.

  • A는 공집합이므로 아무것도 복사되지 않았으며, 처음에 merge procedure에서 "we assume that the subarray A[p...q] and A[q+1...r] are in sorted order."를 언급했으므로 L[1]과 R[1]은 각 배열에서 복사되지 않은 가장 작은 수임을 보장한다.

• 따라서 Initialization은 L.I를 만족한다.*

Maintenance

복습 : "If it is true before an iteration of the loop, it remains true before the next iteration.

• Loop 내에 두 가지 경우가 존재하므로 각각에 대해 증명해야 한다.

1. When L[i] <= R[j]
   • 루프 시작 전에 L.I가 만족한다고 하자.
     • At the start of each iteration for the merging loop, the subarray A[p...k-1] contains the (k-p) smallest elements of L[1...n1+1] and R[1...n2+1], in ascending order.
     • Moreover, L[i] and R[j] is the smallest element of their arrays that have not been copied back into A.

     • L[i]는 A에 복사되지 않은 가장 작은 원소이다.

     • A[p...k-1]이 k-p개의 가장 작은 원소들을 갖고 있기 때문에, L[i]를 A[k]에 넣게 되면 A[p..k]는 k-p+1개의 가장 작은 원소들을 갖고 있게 된다.

     • 이제 다음 iteration 시작 시, k와 i가 증가하면 L.I가 다시 만족한다.

2. When L[i] > R[j]
   • 위의 경우와 같다.

따라서 Maintenance는 L.I를 만족한다.

Termination

• 루프 탈출 후 k = r + 1이다.
• 이를 L.I에 대입해보자.
  • the array A[p...r] contains the (r-p+1) smallest elements of L[1...n1+1] and R[1...n2+1], in sorted order.

  • L과 R의 총 사이즈는 n1 + n2 + 2 = r - p + 3 이다.

  • 아직 복사되지 않은 두 개의 원소들은 각 배열의 가장 큰 원소이자 sentinel인 원소들이다.

  • Moreover, L[n1+1] and L[n2+1] is the smallest element of their arrays that have not been copied back into A.

  • L[n1+1]과 R[n2+1]은 각각 Inf이며, 복사되지 않은 유일한 원소이다.

Merge Sort Time Complexity

• Divide : 항상 가운데 위치만 계산하므로 Theta(1)
• Conquer : 사이즈가 n/2인 부분문제 2개를 해결하므로 2 * T(n/2)
• Combine : MERGE procedure에서 본 바와 같이, n개의 element에 대해 Theta(n)이 걸린다.

-> T(1) = 1, T(n) = 2 * T(n/2) + n -> ... T(n) = nlog(n) + n

• Insertion sort, merge sort, quick sort 등의 다양한 정렬 알고리즘들이 있다.

Insertion Sort

• Incremental algorithm이다.
• 앞의 원소부터 차례대로 증가하며 체크한다.

그렇다면, 이 알고리즘 방식이 정말로 내가 원하는대로 정렬해주는가?

Loop Invariants

• 어떤 알고리즘이 주어졌을 때, 왜 이 알고리즘의 correctess를 보이기 위해 사용하는 방식
• 루프가 반복되는 동안 항상 유지되는 성질
• Initialization*
  • It is true prior to the first iteration of the loop.
• Maintenance*
  • If it is true before an iteration of the loop, it remains true before the next iteration. Termination
    • When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Insertion sort를 통해 Loop Invariant를 활용한 correctness 증명을 적용해보자.

Insertion Sort에서의 Loop invariant

At the start of the loop, the subarray A[1...j-1] consists of the elements originally in A[1...j-1] but in ascending order.

Initialization

• 첫 반복 전에 j는 2이다. 이를 loop invariant에 대입해보자.
  • At the start of the loop, A[1...1] consists of the elements originally in A[1..1] but in ascending order.

  • 참

Maintenance

• Maintenance에서 보여야 하는 성질의 핵심은 아래와 같다.
  • 루프 실행 전에도 참이라면, 다음 루프 실행 전에도 참이어야 한다.

  • 루프 실행 전에도 Loop invariant를 만족한다면, 다음 루프 실행 전에도 이 Loop invariant를 만족해야 한다.

• 그러므로, 루프 실행 전에 Loop invariant를 만족한다고 하자.
  • At the start of the j-th iteration of the loop, A[1...j-1] consists of the elements originally in A[1...j-1] but in ascending order.
• A[1...j-1]를 j까지로 확장하는 것이다.
  • 변수 i를 통해 A[j-1]부터 A[1]까지 순회하며 A[j]보다 큰 원소들을 오른쪽으로 옮긴다. 해당 과정이 멈춘 경우, A[j]는 멈춘 위치 +1인 곳(i+1)에 삽입된다. 따라서 정렬된 A[1...j-1]의 배열에 key를 올바른 위치에 삽입한다. 즉, 삽입된 위치에는 A[j]가 있고, A[j] 기준으로 왼쪽은 A[j]보다 작거나 같은 값들, 오른쪽은 A[j]보다 큰 값들이 존재하므로 기존 배열의 정렬성을 해치지 않고 올바르게 삽입된다.
• 이제, j를 증가시켜서 A[1...j]로 만들면, 이 배열은 다음 iteration 시작 시에도 정렬된 상태이므로 Loop Invariant가 유지된다.

• 따라서 Maintenance 역시 참이다.

Termination

• for loop이 종료되었을 때 j = n + 1이다.
• 이 j 값을 loop invariant에 넣어보자.
  • A[1...n] consists of the elements originally in A[1...j] but in ascending order.

  • correctness 증명 완료.

• 수행 시간 : 0ms
• 메모리 : 2024KB

Learnings

• DFS시 매번 독립된 분기 데이터들을 직접 다뤄야 하므로 & 잊지말자.

#include <iostream>
#include <vector>
using namespace std;

#define SHARK -1
#define EMPTY 0

const int ds[9][2] = {
    {},
    {-1, 0},
    {-1, -1},
    {0, -1},
    {1, -1},
    {1, 0},
    {1, 1},
    {0, 1},
    {-1, 1}
};

struct Fish {
    int i;
    int j;
    int id;
    int dir;
    bool onGrid;

    Fish() {}
    Fish(int _i, int _j, int _id, int _dir) :
        i(_i), j(_j), id(_id), dir(_dir), onGrid(true) { }
};

struct Shark {
    int i;
    int j;
    int dir;
    int score;

    Shark() {}
    Shark(int _i, int _j, int _dir, int _score) :
        i(_i), j(_j), dir(_dir), score(_score) { }
};

int grid[5][5];
vector<Fish> fishes;
Shark shark;
int maxScore;

bool InGrid(int i, int j) {
    return 1 <= i && i <= 4 && 1 <= j && j <= 4;
}

void DupGrid(int from[5][5], int to[5][5]) {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            to[i][j] = from[i][j];
        }
    }
}

void FishMove(int g[5][5], vector<Fish>& fs, Shark& s) {
    for (int f = 1; f <= 16; f++) {
        if (!fs[f].onGrid) continue;

        int ci = fs[f].i, cj = fs[f].j, cd = fs[f].dir;
        int ni = ci + ds[cd][0], nj = cj + ds[cd][1];
        int cnt = 0;
        while (!InGrid(ni, nj) || g[ni][nj] == SHARK) {
            cd = (cd + 1 > 8 ? 1 : cd + 1);
            ni = ci + ds[cd][0], nj = cj + ds[cd][1];
            cnt++;
            if (cnt >= 8) break;
        }
        if (cnt >= 8) continue;

        if (g[ni][nj] != EMPTY) {
            int temp = g[ni][nj];
            g[ni][nj] = f;
            fs[f].i = ni, fs[f].j = nj, fs[f].dir = cd;

            g[ci][cj] = temp;
            fs[temp].i = ci, fs[temp].j = cj;
        }
        else {
            g[ci][cj] = EMPTY;
            g[ni][nj] = f;
            fs[f].i = ni, fs[f].j = nj, fs[f].dir = cd;
        }
    }
}

void Dfs(int g[5][5], vector<Fish>& fs, Shark& s) {
    maxScore = max(maxScore, s.score);

    FishMove(g, fs, s);

    int ci = s.i, cj = s.j, cd = s.dir;

    for (int d = 1; d <= 3; d++) {
        int ni = ci + ds[cd][0] * d, nj = cj + ds[cd][1] * d;
        if (!InGrid(ni, nj)) continue;
        if (g[ni][nj] == EMPTY) continue;

        int tempGrid[5][5];
        DupGrid(g, tempGrid);
        vector<Fish> tempFishes = fs;
        Shark tempShark = s;

        tempGrid[tempShark.i][tempShark.j] = EMPTY;
        tempShark.i = ni, tempShark.j = nj, tempShark.dir = tempFishes[tempGrid[ni][nj]].dir;
        tempShark.score += tempGrid[ni][nj];
        tempFishes[tempGrid[ni][nj]].onGrid = false;
        tempGrid[ni][nj] = SHARK;

        Dfs(tempGrid, tempFishes, tempShark);
    }
}

int main() {
    fishes.resize(17);
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            int id, dir;
            cin >> id >> dir;
            grid[i][j] = id;
            fishes[id] = Fish(i, j, id, dir);
        }
    }

    shark = Shark(1, 1, fishes[grid[1][1]].dir, grid[1][1]);
    fishes[grid[1][1]].onGrid = false;
    grid[1][1] = SHARK;

    int tempGrid[5][5];
    DupGrid(grid, tempGrid);
    vector<Fish> tempFishes = fishes;
    Shark tempShark = shark;

    Dfs(tempGrid, tempFishes, tempShark);

    cout << maxScore;

    return 0;
}

BFS, Simulation

평균 : 180'

sol : 235' 27''

• 수행 시간 : 13ms
• 메모리 : 0MB

Learnings

• 두 번째 푸는데도 4시간 걸리는 미친 문제
• 주 병목은 부채꼴 진행

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <tuple>
#include <cmath>
using namespace std;

// 0-based
#define EMPTY 0
#define MAX_N 60
#define ROAD 0
#define NOT_ROAD 1

#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3

int roadGrid[MAX_N][MAX_N];
int solderNumGrid[MAX_N][MAX_N];
pair<int, int> fromWhere[MAX_N][MAX_N];
bool bestVision[MAX_N][MAX_N];
vector<pair<int, int>> bestStunned;

int movedDist, stoneCnt, attackCnt;

// 상, 하, 좌, 우
const int ds[4][2] = {
    {-1, 0},
    {1, 0},
    {0, -1},
    {0, 1}
};

int n, m;
struct Medusa {
    int si;
    int sj;
    int ei;
    int ej;
    pair<int, int> curPos;
    vector<pair<int, int>> path;

    Medusa() :
        si(-1), sj(-1), ei(-1), ej(-1), curPos({ -1, -1 }) {
    }
};

struct Solder {
    int i;
    int j;
    bool stone;
    bool onGrid;

    Solder() {};
};

Medusa medusa;
vector<Solder> solders;

void DebugVision(bool v[MAX_N][MAX_N]) {
    cout << endl << "VISION" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << v[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}

void Debug() {
    cout << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (solderNumGrid[i][j] > 0) cout << "1 ";
            else if (i == medusa.curPos.first && j == medusa.curPos.second) cout << "M ";
            else cout << "0 ";
        }
        cout << endl;
    }
    cout << endl;
}

void Init() {
    cin >> n >> m;

    cin >> medusa.si >> medusa.sj >> medusa.ei >> medusa.ej;

    solders.resize(m + 1);
    for (int s = 1; s <= m; s++) {
        int ai, aj;
        cin >> ai >> aj;
        solders[s].i = ai;
        solders[s].j = aj;
        solders[s].stone = false;
        solders[s].onGrid = true;
        solderNumGrid[ai][aj]++;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> roadGrid[i][j];
        }
    }
}

bool InGrid(int i, int j) {
    return 0 <= i && i < n && 0 <= j && j < n;
}

void InitFromWhere() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            fromWhere[i][j] = { -1, -1 };
        }
    }
}

void InitBestVision() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            bestVision[i][j] = false;
        }
    }
}

bool GetMedusaPath() {
    bool possible = false;
    InitFromWhere();

    queue<pair<int, int>> q;
    q.push({ medusa.si, medusa.sj });
    fromWhere[medusa.si][medusa.sj] = { medusa.si, medusa.sj };

    while (!q.empty()) {
        int ci, cj;
        tie(ci, cj) = q.front();
        q.pop();

        if (ci == medusa.ei && cj == medusa.ej) {
            possible = true;
            break;
        }

        for (int d = 0; d < 4; d++) {
            int ni = ci + ds[d][0], nj = cj + ds[d][1];

            if (!InGrid(ni, nj)) continue;
            if (fromWhere[ni][nj] != make_pair(-1, -1)) continue;
            if (roadGrid[ni][nj] == NOT_ROAD) continue;

            fromWhere[ni][nj] = { ci, cj };
            q.push({ ni, nj });
        }
    }

    if (!possible) return false;

    vector<pair<int, int>> reversePath;
    pair<int, int > curPos = { medusa.ei, medusa.ej };

    while (curPos != make_pair(medusa.si, medusa.sj)) {
        reversePath.push_back(curPos);
        curPos = fromWhere[curPos.first][curPos.second];
    }

    medusa.path.push_back({ medusa.si, medusa.sj });
    for (int i = reversePath.size() - 1; i >= 0; i--) {
        medusa.path.push_back(reversePath[i]);
    }

    return true;
}

int Oppos(int dir) {
    if (dir == UP) return DOWN;
    if (dir == DOWN) return UP;
    if (dir == LEFT) return RIGHT;
    if (dir == RIGHT) return LEFT;
}

void GetBestDir() {
    int bestCnt = 0;
    InitBestVision();

    // 상,하,좌,우 순으로 바라볼 때
    for (int curD = 0; curD < 4; curD++) {
        // 위치, 방향
        queue<tuple<int, int, int, int>> caught;

        bool visited[MAX_N][MAX_N];
        bool vision[MAX_N][MAX_N];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = false;
                vision[i][j] = false;
            }
        }

        // Phase 1. 전사 탐색
        queue<tuple<int, int, int, int>> q;
        int ci, cj;
        tie(ci, cj) = medusa.curPos;
        for (int sightD = 0; sightD < 4; sightD++) {
            if (sightD == Oppos(curD)) continue;
            int ni, nj;
            if (sightD == curD) {
                ni = ci + ds[sightD][0], nj = cj + ds[sightD][1];
            }
            else {
                ni = ci + ds[sightD][0] + ds[curD][0], nj = cj + ds[sightD][1] + ds[curD][1];
            }

            if (!InGrid(ni, nj)) continue;
            if (visited[ni][nj]) continue;
            visited[ni][nj] = true,    vision[ni][nj] = true;
            q.push(make_tuple(ni, nj, sightD, curD));
            if (solderNumGrid[ni][nj] > 0) caught.push(make_tuple(ni, nj, sightD, curD));
        }



        while (!q.empty()) {
            int ci, cj, sightD, curD;
            tie(ci, cj, sightD, curD) = q.front();
            q.pop();

            // 직선인 경우
            if (sightD == curD) {
                int ni = ci + ds[sightD][0], nj = cj + ds[sightD][1];
                if (!InGrid(ni, nj)) continue;
                if (visited[ni][nj]) continue;
                visited[ni][nj] = true, vision[ni][nj] = true;

                q.push({ ni, nj, sightD, curD });
                if (solderNumGrid[ni][nj] > 0) caught.push(make_tuple(ni, nj, sightD, curD));
            }
            // 대각인 경우
            else {
                int ni1 = ci + ds[curD][0], nj1 = cj + ds[curD][1];
                int ni2 = ni1 + ds[sightD][0], nj2 = nj1 + ds[sightD][1];

                if (InGrid(ni1, nj1) && !visited[ni1][nj1]) {
                    q.push({ ni1, nj1, sightD, curD });
                    visited[ni1][nj1] = true;
                    vision[ni1][nj1] = true;
                    if (solderNumGrid[ni1][nj1] > 0)    caught.push({ ni1, nj1, sightD, curD });
                }
                if (InGrid(ni2, nj2) && !visited[ni2][nj2]) {
                    q.push({ ni2, nj2, sightD, curD });
                    visited[ni2][nj2] = true;
                    vision[ni2][nj2] = true;
                    if (solderNumGrid[ni2][nj2] > 0)    caught.push({ ni2, nj2, sightD, curD });
                }
            }
        }

        // Phase 2. 전사 위치에서 다시 끄기
        vector<pair<int, int>> stunned;
        while (!caught.empty()) {
            int i, j, sightD, curD;
            tie(i, j, sightD, curD) = caught.front();

            caught.pop();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    visited[i][j] = false;
                }
            }

            // 뒤에 가려진 전사
            if (!vision[i][j]) continue;

            // 실제로 굳은 전사들의 위치
            stunned.push_back({ i, j });

            // 직선 방향인 경우
            if (sightD == curD) {
                int ci = i, cj = j;
                while (InGrid(ci, cj)) {
                    ci += ds[sightD][0], cj += ds[sightD][1];
                    vision[ci][cj] = false;
                }
                continue;
            }

            // 대각 방향인 경우
            queue<pair<int, int>> sq;
            sq.push({ i, j });
            visited[i][j] = true;

            while (!sq.empty()) {
                int ci, cj;
                tie(ci, cj) = sq.front();
                sq.pop();

                int    ni1 = ci + ds[curD][0], nj1 = cj + ds[curD][1];
                int ni2 = ni1 + ds[sightD][0], nj2 = nj1 + ds[sightD][1];

                if (InGrid(ni1, nj1) && !visited[ni1][nj1]) {
                    sq.push({ ni1, nj1 });
                    visited[ni1][nj1] = true;
                    vision[ni1][nj1] = false;
                }
                if (InGrid(ni2, nj2) && !visited[ni2][nj2]) {
                    sq.push({ ni2, nj2 });
                    visited[ni2][nj2] = true;
                    vision[ni2][nj2] = false;
                }
            }
        }

        int curCnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (vision[i][j]) {
                    curCnt += solderNumGrid[i][j];
                }
            }
        }

        if (curCnt > bestCnt) {
            bestCnt = curCnt;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    bestVision[i][j] = vision[i][j];
                }
            }
            bestStunned = stunned;
        }
    }
}

void Stun() {
    for (int a = 0; a < bestStunned.size(); a++) {
        for (int s = 1; s <= m; s++) {
            if (!solders[s].onGrid) continue;
            if (solders[s].i == bestStunned[a].first && solders[s].j == bestStunned[a].second) {
                solders[s].stone = true;
                stoneCnt++;
            }
        }
    }
}

int Dist(int si, int sj) {
    int mi, mj;
    tie(mi, mj) = medusa.curPos;

    return abs(si - mi) + abs(sj - mj);
}

void SoldersMove() {
    for (int s = 1; s <= m; s++) {
        if (!solders[s].onGrid) continue;
        if (solders[s].stone) {
            solders[s].stone = false;
            continue;
        }

        int ci = solders[s].i, cj = solders[s].j;
        int minDist = Dist(ci, cj);
        int best_i = -1, best_j = -1;
        // 1st move
        for (int d = 0; d < 4; d++) {
            int ni = ci + ds[d][0], nj = cj + ds[d][1];
            if (!InGrid(ni, nj)) continue;
            if (bestVision[ni][nj]) continue;
            if (Dist(ni, nj) >= minDist) continue;

            minDist = Dist(ni, nj);
            best_i = ni, best_j = nj;
        }

        if (best_i == -1) continue;
        solderNumGrid[solders[s].i][solders[s].j]--;
        solders[s].i = best_i, solders[s].j = best_j;
        solderNumGrid[solders[s].i][solders[s].j]++;
        movedDist++;

        // check
        if (solders[s].i == medusa.curPos.first && solders[s].j == medusa.curPos.second) {
            attackCnt++;
            solders[s].onGrid = false;
            solderNumGrid[solders[s].i][solders[s].j]--;
            continue;
        }

        // 2nd move
        int tempDs[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
        ci = solders[s].i, cj = solders[s].j;
        minDist = Dist(ci, cj);
        best_i = -1, best_j = -1;
        for (int d = 0; d < 4; d++) {
            int ni = ci + tempDs[d][0], nj = cj + tempDs[d][1];
            if (!InGrid(ni, nj)) continue;
            if (bestVision[ni][nj]) continue;
            if (Dist(ni, nj) >= minDist) continue;

            minDist = Dist(ni, nj);
            best_i = ni, best_j = nj;
        }

        if (best_i == -1) continue;
        solderNumGrid[solders[s].i][solders[s].j]--;
        solders[s].i = best_i, solders[s].j = best_j;
        solderNumGrid[solders[s].i][solders[s].j]++;
        movedDist++;

        // check
        if (solders[s].i == medusa.curPos.first && solders[s].j == medusa.curPos.second) {
            attackCnt++;
            solders[s].onGrid = false;
            solderNumGrid[solders[s].i][solders[s].j]--;
        }
    }
}

void MedusaMove(int t) {
    medusa.curPos = medusa.path[t];
    int ci, cj;
    tie(ci, cj) = medusa.curPos;
    if (solderNumGrid[ci][cj] > 0) {
        solderNumGrid[ci][cj] = 0;
        for (int s = 1; s <= m; s++) {
            if (!solders[s].onGrid) continue;
            if (solders[s].i == ci && solders[s].j == cj) {
                solders[s].onGrid = false;
            }
        }
    }
}

int main() {
    Init();

    if (!GetMedusaPath()) {
        cout << -1;
        return 0;
    }

    medusa.curPos = medusa.path[0];
    for (int t = 1; t < medusa.path.size() - 1; t++) {
        movedDist = 0, attackCnt = 0, stoneCnt = 0;

        MedusaMove(t);

        GetBestDir();

        Stun();

        SoldersMove();

        cout << movedDist << ' ' << stoneCnt << ' ' << attackCnt << '\n';
    }
    cout << 0;

    return 0;
}

BFS, Simulation

평균 : 180'

sol : 90' 18''

• 수행 시간 : 8ms
• 메모리 : 0MB

Learnings

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <queue>
#include <climits>
using namespace std;

// 1-base
#define MAX_N 31
#define EMPTY 0
#define BLOCK -1

int n, k, l;
int dustGrid[MAX_N][MAX_N];
int robotGrid[MAX_N][MAX_N];

// 우, 하, 좌, 상
const int ds[4][2] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0}
};

struct Robot {
    int i;
    int j;

    Robot() {}
    Robot(int _i, int _j) :
        i(_i), j(_j) { }
};

vector<Robot> robots;

void DebugDG() {
    cout << endl << "DEBUG DUST GRID" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dustGrid[i][j] == BLOCK) cout << "B ";
            else cout << dustGrid[i][j] << ' ';
        }
        cout << endl;
    }
    cout << "DEBUG FIN" << endl << endl;
}

void DebugRG() {
    cout << endl << "DEBUG ROBOT GRID" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dustGrid[i][j] == BLOCK) cout << "B ";
            else cout << robotGrid[i][j] << ' ';
        }
        cout << endl;
    }
    cout << "DEBUG FIN" << endl << endl;
}

bool InGrid(int i, int j) {
    return 1 <= i && i <= n && 1 <= j && j <= n;
}

void Init() {
    cin >> n >> k >> l;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> dustGrid[i][j];
        }
    }

    robots.resize(k + 1);
    for (int i = 1; i <= k; i++) {
        int r, c;
        cin >> r >> c;
        robots[i] = Robot(r, c);
        robotGrid[r][c] = i;
    }
}

pair<int, int> GetNextPos(int i, int j) {
    if (dustGrid[i][j] > 0) return make_pair(i, j);

    // 거리, 행, 열
    tuple<int, int, int> bestPos = {INT_MAX, INT_MAX, INT_MAX};
    bool visited[MAX_N][MAX_N];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            visited[i][j] = false;
        }
    }
    // 거리, 행, 열
    queue<tuple<int, int, int>> q;
    q.push({ 0, i, j });
    visited[i][j] = true;

    while (!q.empty()) {
        int cd, ci, cj;
        tie(cd, ci, cj) = q.front();
        q.pop();

        int bd;
        tie(bd, ignore, ignore) = bestPos;
        if (bd < cd) continue;

        for (int d = 0; d < 4; d++) {
            int ni = ci + ds[d][0], nj = cj + ds[d][1];

            if (!InGrid(ni, nj)) continue;
            if (visited[ni][nj]) continue;
            if (dustGrid[ni][nj] == BLOCK) continue;
            if (robotGrid[ni][nj] != EMPTY) continue;

            visited[ni][nj] = true;
            if (dustGrid[ni][nj] == EMPTY) q.push({ cd + 1, ni, nj });
            else if (dustGrid[ni][nj] > 0) {
                tuple<int, int, int> curPos = make_tuple(cd + 1, ni, nj);
                if (curPos < bestPos) bestPos = curPos;
            }
        }
    }

    int best_i, best_j;
    tie(ignore, best_i, best_j) = bestPos;
    return make_pair(best_i, best_j);
}

void RobotsMove() {
    for (int r = 1; r <= k; r++) {
        int ci = robots[r].i, cj = robots[r].j;
        pair<int, int> nextPos = GetNextPos(ci, cj);

        if (nextPos.first == INT_MAX) continue;

        int ni = nextPos.first, nj = nextPos.second;
        robotGrid[ci][cj] = EMPTY;
        robotGrid[ni][nj] = r;

        robots[r].i = ni, robots[r].j = nj;
    }
}

void Clean() {
    for (int r = 1; r <= k; r++) {
        int maxDust = 0, bestDir = -1;
        int ci = robots[r].i, cj = robots[r].j;
        dustGrid[ci][cj] = (dustGrid[ci][cj] > 20 ? dustGrid[ci][cj] - 20 : EMPTY);

        for (int d = 0; d < 4; d++) {
            int curDust = 0;
            for (int cd = 0; cd < 4; cd++) {
                if (cd == (d + 2) % 4) continue;

                int ni = ci + ds[cd][0], nj = cj + ds[cd][1];
                if (!InGrid(ni, nj)) continue;
                if (dustGrid[ni][nj] == BLOCK) continue;

                // 최대 20까지만 청소 가능
                curDust += (dustGrid[ni][nj] > 20 ? 20 : dustGrid[ni][nj]);
            }
            if (curDust > maxDust) {
                maxDust = curDust;
                bestDir = d;
            }
        }

        if (bestDir == -1) continue;

        for (int d = 0; d < 4; d++) {
            if (d == (bestDir + 2) % 4) continue;

            int ni = ci + ds[d][0], nj = cj + ds[d][1];
            if (!InGrid(ni, nj)) continue;
            if (dustGrid[ni][nj] == BLOCK) continue;

            dustGrid[ni][nj] = (dustGrid[ni][nj] > 20 ? dustGrid[ni][nj] - 20 : EMPTY);
        }
    }
}

void IncreaseDust() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dustGrid[i][j] == EMPTY || dustGrid[i][j] == BLOCK) continue;
            dustGrid[i][j] += 5;
        }
    }
}

void Diffuse() {
    int temp[MAX_N][MAX_N];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            temp[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dustGrid[i][j] != EMPTY) continue;

            int curDust = 0;
            for (int d = 0; d < 4; d++) {
                int ni = i + ds[d][0], nj = j + ds[d][1];

                if (!InGrid(ni, nj)) continue;
                if (dustGrid[ni][nj] == BLOCK) continue;

                curDust += dustGrid[ni][nj];
            }

            curDust /= 10;
            temp[i][j] = curDust;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dustGrid[i][j] += temp[i][j];
        }
    }
}

void PrintDust() {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dustGrid[i][j] == EMPTY || dustGrid[i][j] == BLOCK) continue;
            total += dustGrid[i][j];
        }
    }
    cout << total << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    Init();

    for (int turn = 1; turn <= l; turn++) {

        RobotsMove();

        Clean();

        IncreaseDust();

        Diffuse();

        PrintDust();
    }

    return 0;
}

Learnings

• 회전한 채로 그리드를 계속 생각하는 방식이 흥미로웠다.

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

#define BLUE 0
#define GREEN 1

int n, score;
bool grids[2][6][4];
bool blocks[4][2][2] = {
    {},

    {{1, 0},
    {0, 0}},

    {{1, 1},
    {0, 0}},

    {{1, 0},
    {1, 0}}
};

void Debug(int zone) {
    if (zone == BLUE) cout << endl << "BLUE DEBUG" << endl;
    else if (zone == GREEN) cout << endl << "GREEN DEBUG" << endl;

    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 4; j++) {
            cout << grids[zone][i][j] << ' ';
        }
        cout << endl;
    }
    cout << "DEBUG FIN" << endl;
}

bool InGrid(int i, int j) {
    return 0 <= i && i < 6 && 0 <= j && j < 6;
}

bool Fit(vector<pair<int, int>>& area, bool grid[6][4]) {
    for (int a = 0; a < area.size(); a++) {
        int ci = area[a].first, cj = area[a].second;
        if (!InGrid(ci, cj) || grid[ci][cj]) return false;
    }
    return true;
}

bool RowFull(int zone, int i) {
    for (int j = 0; j < 4; j++) {
        if (grids[zone][i][j] == false) {
            return false;
        }
    }
    return true;
}

void Downward(int zone, int i) {
    for (int ci = i - 1; ci >= 0; ci--) {
        for (int cj = 0; cj < 4; cj++) {
            if (!grids[zone][ci][cj]) continue;

            grids[zone][ci][cj] = false;
            grids[zone][ci + 1][cj] = true;
        }
    }
}

void PushDown(int zone) {
    for (int i = 5; i > 0; i--) {
        for (int j = 0; j < 4; j++) {
            grids[zone][i][j] = grids[zone][i - 1][j];
            grids[zone][i - 1][j] = false;
        }
    }
}

void Drop(int zone, int type, int x, int y) {
    vector<pair<int, int>> curArea;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            if (!blocks[type][i][j]) continue;

            int ci = x + i, cj = y + j;
            curArea.push_back({ ci, cj });
        }
    }

    for (int a = 0; a < curArea.size(); a++) {
        if (zone == BLUE) {
            int temp = curArea[a].first;
            curArea[a].first = curArea[a].second - y;
            curArea[a].second = 4 - temp - 1;
        }
        else {
            curArea[a].first -= x;
        }
    }

    while (true) {
        if (!Fit(curArea, grids[zone])) break;
        for (int a = 0; a < curArea.size(); a++) {
            curArea[a].first++;
        }
    }

    for (int a = 0; a < curArea.size(); a++) {
        grids[zone][--curArea[a].first][curArea[a].second] = true;
    }

    // 1. 만약 행이 가득 찼다면
    for (int i = 5; i >= 0; i--) {
        bool full = RowFull(zone, i);

        while (full) {
            score++;
            for (int j = 0; j < 4; j++) {
                grids[zone][i][j] = false;
            }
            Downward(zone, i);
            full = RowFull(zone, i);
        }
    }

    // 2. 연한 칸에 존재한다면
    int downNum = 0;
    for (int j = 0; j < 4; j++) {
        if (grids[zone][0][j]) {
            downNum = 2;
            break;
        }
    }
    if (downNum == 0) {
        for (int j = 0; j < 4; j++) {
            if (grids[zone][1][j]) {
                downNum = 1;
                break;
            }
        }
    }

    for (int d = 0; d < downNum; d++) PushDown(zone);
}

void PrintBlockNum() {
    int cnt = 0;
    for (int zone = 0; zone < 2; zone++) {
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 4; j++) {
                if (grids[zone][i][j]) cnt++;
            }
        }
    }

    cout << cnt;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;

    for (int turn = 1; turn <= n; turn++) {
        int t, x, y;
        cin >> t >> x >> y;

        Drop(GREEN, t, x, y);

        Drop(BLUE, t, x, y);
    }

    cout << score << '\n';
    PrintBlockNum();

    return 0;
}

Simulation

평균 : 180'

sol : 165' 24''

• 수행 시간 : 149ms -> 10ms
• 메모리 : 0MB

Learnings

• 직사각형이어서 좌표를 전부 가지고 다닐 필요가 없었다.

After revise

#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <algorithm>
using namespace std;

// 1-based
#define MAX_N 51
#define EMPTY 0
#define MAX_K 100

int n, m;
int grid[MAX_N][MAX_N];
int curTarget;

struct Post {
    int h;
    int w;
    int r;
    int c;
};

vector<Post> posts;

void Debug() {
    cout << endl << "DEBUG" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << grid[i][j] << ' ';
        }
        cout << endl;
    }
    cout << "DEBUG FIN" << endl;
}

bool InGrid(int i, int j) {
    return 1 <= i && i <= n && 1 <= j && j <= n;
}

bool Fit(Post p) {
    for (int i = p.r; i < p.r + p.h; i++) {
        for (int j = p.c; j < p.c + p.w; j++) {
            if (!InGrid(i, j) || grid[i][j] != EMPTY) return false;
        }
    }
    return true;
}

void Drop() {
    posts.resize(MAX_K + 1);

    for (int p = 1; p <= m; p++) {
        int k, h, w, c;
        cin >> k >> h >> w >> c;

        Post cur = { h, w, 1, c };

        while (true) {
            cur.r++;
            if (!Fit(cur)) break;
        }
        cur.r--;

        posts[k] = cur;

        for (int i = cur.r; i < cur.r + cur.h; i++) {
            for (int j = cur.c; j < cur.c + cur.w; j++) {
                grid[i][j] = k;
            }
        }
    }
}

bool Remained() {
    for (int j = 1; j <= n; j++) {
        if (grid[n][j] != EMPTY) return true;
    }
    return false;
}

bool CanLeftPick(int id) {
    Post p = posts[id];

    int cur_c = p.c;

    while (cur_c > 1) {
        cur_c--;

        for (int i = p.r; i < p.r + p.h; i++) {
            if (grid[i][cur_c] != EMPTY) return false;
        }
    }

    return true;
}

bool CanRightPick(int id) {
    Post p = posts[id];

    int cur_c = p.c + p.w - 1;

    while (cur_c < n) {
        cur_c++;

        for (int i = p.r; i < p.r + p.h; i++) {
            if (grid[i][cur_c] != EMPTY) return false;
        }
    }

    return true;
}

void LeftPick() {
    int target = INT_MAX;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (grid[i][j] == EMPTY) continue;
            if (grid[i][j] == target) break;

            if (CanLeftPick(grid[i][j])) {
                if (grid[i][j] < target) target = grid[i][j];
            }
            break;
        }
    }

    curTarget = target;
}

void RightPick() {
    int target = INT_MAX;
    for (int i = 1; i <= n; i++) {
        for (int j = n; j >= 1; j--) {
            if (grid[i][j] == EMPTY) continue;
            if (grid[i][j] == target) break;

            if (CanRightPick(grid[i][j])) {
                if (grid[i][j] < target) target = grid[i][j];
            }
            break;
        }
    }

    curTarget = target;
}

void Remove() {
    Post p = posts[curTarget];

    for (int i = p.r; i < p.r + p.h; i++) {
        for (int j = p.c; j < p.c + p.w; j++) {
            grid[i][j] = EMPTY;
        }
    }
}

void Fall(int id) {
    Post p = posts[id];

    int cur_r = p.r;
    bool moved = false;

    while (true) {
        int next_r = cur_r + 1;

        if (next_r + p.h - 1 > n) break;

        bool can = true;
        for (int j = p.c; j < p.c + p.w; j++) {
            if (grid[next_r + p.h - 1][j] != EMPTY) {
                can = false;
                break;
            }
        }

        if (!can) break;

        cur_r++;
        moved = true;
    }

    if (!moved) return;

    // 기존 위치 제거
    for (int i = p.r; i < p.r + p.h; i++) {
        for (int j = p.c; j < p.c + p.w; j++) {
            grid[i][j] = EMPTY;
        }
    }

    // 위치 갱신
    posts[id].r = cur_r;

    // 다시 배치
    for (int i = cur_r; i < cur_r + p.h; i++) {
        for (int j = p.c; j < p.c + p.w; j++) {
            grid[i][j] = id;
        }
    }
}

void FallPhase() {
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= n; j++) {
            if (grid[i][j] == EMPTY) continue;
            Fall(grid[i][j]);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;

    Drop();

    while (Remained()) {
        LeftPick();
        cout << curTarget << '\n';

        Remove();

        FallPhase();

        RightPick();
        cout << curTarget << '\n';

        Remove();

        FallPhase();
    }

    return 0;
}

• 수행 시간 : 4ms -> 0ms
• 메모리 : 2032KB

Learnings

• 다음엔 1시간 이내로 풀어보자.

#include <iostream>
#include <vector>
using namespace std;

#define MAX_N 13
#define WHITE 0
#define RED 1
#define BLUE 2

#define RIGHT 1
#define LEFT 2
#define UP 3
#define DOWN 4

int n, k, turn;
bool impossible, finish;
// 우, 좌, 상, 하
const int ds[5][2] = {
    {0, 0},
    {0, 1},
    {0, -1},
    {-1, 0},
    {1, 0}
};

struct Horse {
    int i;
    int j;
    int dir;

    Horse() {}
    Horse(int _i, int _j, int _dir) :
        i(_i), j(_j), dir(_dir) { }
};

vector<int> horseGrid[MAX_N][MAX_N];
int boardGrid[MAX_N][MAX_N];
vector<Horse> horses;
vector<bool> moved;

void Init() {
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> boardGrid[i][j];
        }
    }

    horses.resize(k + 1);
    for (int i = 1; i <= k; i++) {
        int r, c, dir;
        cin >> r >> c >> dir;
        horseGrid[r][c].push_back(i);
        horses[i] = Horse(r, c, dir);
    }

    moved.resize(k + 1);
}

bool InGrid(int i, int j) {
    return 1 <= i && i <= n && 1 <= j && j <= n;
}

int Oppos(int dir) {
    if (dir == LEFT) return RIGHT;
    if (dir == RIGHT) return LEFT;
    if (dir == UP) return DOWN;
    if (dir == DOWN) return UP;
    return -1;
}

void Move() {
    for (int h = 1; h <= k; h++) {
        moved[h] = false;

        int ci = horses[h].i, cj = horses[h].j, cd = horses[h].dir;
        int ni = ci + ds[cd][0], nj = cj + ds[cd][1];

        // 체스판을 벗어나거나 파란색인 경우
        if (!InGrid(ni, nj) || boardGrid[ni][nj] == BLUE) {
            cd = Oppos(cd);
            ni = ci + ds[cd][0], nj = cj + ds[cd][1];
            horses[h].dir = cd;
            if (!InGrid(ni, nj) || boardGrid[ni][nj] == BLUE) continue;
        }

        vector<int> stayer, mover;
        for (int i = 0; i < horseGrid[ci][cj].size(); i++) {
            if (horseGrid[ci][cj][i] != h) {
                stayer.push_back(horseGrid[ci][cj][i]);
            }
            else {
                for (int j = i; j < horseGrid[ci][cj].size(); j++) {
                    mover.push_back(horseGrid[ci][cj][j]);
                }
                break;
            }
        }
        horseGrid[ci][cj] = stayer;

        // 흰색인 경우
        if (boardGrid[ni][nj] == WHITE) {
            for (int i = 0; i < mover.size(); i++) {
                horseGrid[ni][nj].push_back(mover[i]);
                horses[mover[i]].i = ni, horses[mover[i]].j = nj;
            }
        }

        // 빨간색인 경우
        else if (boardGrid[ni][nj] == RED) {
            for (int i = mover.size() - 1; i >= 0; i--) {
                horseGrid[ni][nj].push_back(mover[i]);
                horses[mover[i]].i = ni, horses[mover[i]].j = nj;
            }
        }

        moved[h] = true;
        if (horseGrid[ni][nj].size() >= 4) {
            finish = true;
            return;
        }
    }
}

bool Impossible() {
    impossible = true;
    for (int i = 1; i <= k; i++) {
        if (moved[i]) impossible = false;
    }

    return impossible;
}

int main() {
    Init();

    while (++turn <= 1000) {
        Move();

        if (finish) {
            cout << turn;
            return 0;
        }

        if (Impossible()) break;
    }

    cout << -1;

    return 0;
}

• 수행 시간 : 4ms
• 메모리 : 2168KB

Learnings

• 깔끔하게 전부 정리하고 풀면 1시간 이내도 가능했을 것.
• 암산 절대금지

#include <iostream>
#include <vector>
#include <string>
using namespace std;

#define U 0
#define D 1
#define F 2
#define B 3
#define L 4
#define R 5

#define CW 0
#define CCW 1

int T;

struct Order {
    int face;
    int dir;
};

vector<Order> orders;

char colors[6] = { 'w', 'y', 'r', 'o', 'g', 'b' };
char cube[6][3][3];

int Translator(char order) {
    if (order == 'U') return U;
    if (order == 'D') return D;
    if (order == 'F') return F;
    if (order == 'B') return B;
    if (order == 'L') return L;
    if (order == 'R') return R;
    if (order == '+') return CW;
    if (order == '-') return CCW;
}

void RotateOutter(int face, int dir) {
    char tempFace[3][3];

    // 시계 회전 
    if (dir == CW) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                tempFace[j][2 - i] = cube[face][i][j];
            }
        }
    }
    // 반시계 회전
    else if (dir == CCW) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                tempFace[2 - j][i] = cube[face][i][j];
            }
        }
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cube[face][i][j] = tempFace[i][j];
        }
    }
}

void Rotater(int face, int dir) {
    RotateOutter(face, dir);

    if (face == U) {
        char temp[3] = { cube[R][0][0], cube[R][0][1], cube[R][0][2] };
        if (dir == CW) {    
            for (int x = 0; x < 3; x++) {
                cube[R][0][x] = cube[B][0][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[B][0][x] = cube[L][0][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[L][0][x] = cube[F][0][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[F][0][x] = temp[x];
            }
        }
        else if (dir == CCW) {
            for (int x = 0; x < 3; x++) {
                cube[R][0][x] = cube[F][0][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[F][0][x] = cube[L][0][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[L][0][x] = cube[B][0][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[B][0][x] = temp[x];
            }
        }
    }

    else if (face == D) {
        char temp[3] = { cube[R][2][0], cube[R][2][1], cube[R][2][2] };
        if (dir == CW) {
            for (int x = 0; x < 3; x++) {
                cube[R][2][x] = cube[F][2][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[F][2][x] = cube[L][2][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[L][2][x] = cube[B][2][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[B][2][x] = temp[x];
            }
        }
        else if (dir == CCW) {
            for (int x = 0; x < 3; x++) {
                cube[R][2][x] = cube[B][2][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[B][2][x] = cube[L][2][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[L][2][x] = cube[F][2][x];
            }
            for (int x = 0; x < 3; x++) {
                cube[F][2][x] = temp[x];
            }
        }
    }

    else if (face == F) {
        char temp[3] = { cube[U][2][0], cube[U][2][1], cube[U][2][2] };
        if (dir == CW) {
            for (int x = 0; x < 3; x++) {
                cube[U][2][x] = cube[L][2 - x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[L][2 - x][2] = cube[D][0][2 - x];
            }
            for (int x = 0; x < 3; x++) {
                cube[D][0][2 - x] = cube[R][x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[R][x][0] = temp[x];
            }
        }
        else if (dir == CCW) {
            for (int x = 0; x < 3; x++) {
                cube[U][2][x] = cube[R][x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[R][x][0] = cube[D][0][2 - x];
            }
            for (int x = 0; x < 3; x++) {
                cube[D][0][2 - x] = cube[L][2 - x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[L][2 - x][2] = temp[x];
            }
        }
    }

    else if (face == B) {
        char temp[3] = { cube[U][0][0], cube[U][0][1], cube[U][0][2] };
        if (dir == CW) {
            for (int x = 0; x < 3; x++) {
                cube[U][0][x] = cube[R][x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[R][x][2] = cube[D][2][2 - x];
            }
            for (int x = 0; x < 3; x++) {
                cube[D][2][2 - x] = cube[L][2 - x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[L][2 - x][0] = temp[x];
            }
        }
        else if (dir == CCW) {
            for (int x = 0; x < 3; x++) {
                cube[U][0][x] = cube[L][2 - x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[L][2 - x][0] = cube[D][2][2 - x];
            }
            for (int x = 0; x < 3; x++) {
                cube[D][2][2 - x] = cube[R][x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[R][x][2] = temp[x];
            }
        }
    }

    else if (face == L) {
        char temp[3] = { cube[U][0][0], cube[U][1][0], cube[U][2][0] };
        if (dir == CW) {
            for (int x = 0; x < 3; x++) {
                cube[U][x][0] = cube[B][2 - x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[B][2 - x][2] = cube[D][x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[D][x][0] = cube[F][x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[F][x][0] = temp[x];
            }
        }
        else if (dir == CCW) {
            for (int x = 0; x < 3; x++) {
                cube[U][x][0] = cube[F][x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[F][x][0] = cube[D][x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[D][x][0] = cube[B][2 - x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[B][2 - x][2] = temp[x];
            }
        }
    }

    else if (face == R) {
        char temp[3] = { cube[U][0][2], cube[U][1][2], cube[U][2][2] };
        if (dir == CW) {
            for (int x = 0; x < 3; x++) {
                cube[U][x][2] = cube[F][x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[F][x][2] = cube[D][x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[D][x][2] = cube[B][2 - x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[B][2 - x][0] = temp[x];
            }
        }
        else if (dir == CCW) {
            for (int x = 0; x < 3; x++) {
                cube[U][x][2] = cube[B][2 - x][0];
            }
            for (int x = 0; x < 3; x++) {
                cube[B][2 - x][0] = cube[D][x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[D][x][2] = cube[F][x][2];
            }
            for (int x = 0; x < 3; x++) {
                cube[F][x][2] = temp[x];
            }
        }
    }
}

void Init() {
    int r;
    cin >> r;
    orders.resize(r);

    for (int f = 0; f < 6; f++) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cube[f][i][j] = colors[f];
            }
        }
    }

    for (int i = 0; i < r; i++) {
        string order;
        cin >> order;


        orders[i].face = Translator(order[0]);
        orders[i].dir = Translator(order[1]);
    }
}

void PrintUpFace() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << cube[U][i][j];
        }
        cout << '\n';
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> T;
    for (int t = 1; t <= T; t++) {
        Init();

        for (int o = 0; o < orders.size(); o++) {
            Rotater(orders[o].face, orders[o].dir);
        }

        PrintUpFace();
    }

    return 0;
}

Simulation

평균 : 180'

sol : 108' 5''

• 수행 시간 : 7ms
• 메모리 : 0MB

Learnings

• 처음 풀었을 때는 9ms였는데 이번에 7ms가 나왔다.
• 상태관리를 적재적소에서 잘한 것 같다.
• 재귀가 약점이었는데 상태 관리를 위한 분기를 명확하게 처리했다.

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

// 1-based
const int MAX_N = 51;
const int RUDOLP = -1;
const int EMPTY = 0;
int n, m, p, c, d;
int turn;
const int ds[8][2] = {
    {-1, 0},
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, -1},
    {-1, 1},
    {1, -1},
    {1, 1}
};

struct Santa {
    int r;
    int c;
    int stun;
    bool onGrid;
    int score;

    Santa() { }
};

struct Rudolp {
    int r;
    int c;

    Rudolp() :
        r(-1), c(-1) { }
};

vector<Santa> santas;
Rudolp rudolp;
int grid[MAX_N][MAX_N];

void Debug() {
    cout << endl << "DEBUG" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (grid[i][j] == RUDOLP) cout << 'R' << ' ';
            else cout << grid[i][j] << ' ';
        }
        cout << endl;
    }
    cout << "DEBUG FIN" << endl << endl;
}

void Init() {
    cin >> n >> m >> p >> c >> d;

    cin >> rudolp.r >> rudolp.c;
    grid[rudolp.r][rudolp.c] = RUDOLP;

    santas.resize(p + 1);
    for (int i = 1; i <= p; i++) {
        int id, r, c;
        cin >> id >> r >> c;
        santas[id].r = r, santas[id].c = c, santas[id].score = 0;
        santas[id].onGrid = true, santas[id].stun = 0;

        grid[r][c] = id;
    }
}

bool InGrid(int i, int j) {
    return 1 <= i && i <= n && 1 <= j && j <= n;
}

int Dist(int r1, int c1, int r2, int c2) {
    return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}

void Correlation(int id, int dir) {
    int ni = santas[id].r + ds[dir][0];
    int nj = santas[id].c + ds[dir][1];

    if (!InGrid(ni, nj)) {
        santas[id].onGrid = false;
        return;
    }

    santas[id].r = ni, santas[id].c = nj;

    if (grid[ni][nj] > 0) {
        int nextId = grid[ni][nj];
        grid[ni][nj] = id;
        Correlation(nextId, dir);
        return;
    }

    if (grid[ni][nj] == EMPTY) {
        grid[ni][nj] = id;
        return;
    }
}

void CollideRtoS(int id, int dir) {
    santas[id].score += c;
    santas[id].stun = turn + 2;

    int ni = santas[id].r + ds[dir][0] * c;
    int nj = santas[id].c + ds[dir][1] * c;

    if (!InGrid(ni, nj)) {
        santas[id].onGrid = false;
        return;
    }

    santas[id].r = ni, santas[id].c = nj;

    if (grid[ni][nj] > 0) {
        int nextId = grid[ni][nj];
        grid[ni][nj] = id;
        Correlation(nextId, dir);
        return;
    }

    if (grid[ni][nj] == EMPTY) {
        grid[ni][nj] = id;
        return;
    }
}

void RudolpMove() {
    int minDist = INT_MAX;
    // r-max, c-max, id
    vector<tuple<int, int, int>> targets;
    for (int s = 1; s <= p; s++) {
        if (!santas[s].onGrid) continue;

        int curDist = Dist(rudolp.r, rudolp.c, santas[s].r, santas[s].c);
        if (curDist < minDist) {
            minDist = curDist;
            targets.clear();
            targets.push_back(make_tuple(-santas[s].r, -santas[s].c, s));
        }
        else if (curDist == minDist) {
            targets.push_back(make_tuple(-santas[s].r, -santas[s].c, s));
        }
    }
    sort(targets.begin(), targets.end());

    int bestDist = INT_MAX, best_ni = -1, best_nj = -1, best_dir = -1;
    int ti, tj, tid;
    tie(ti, tj, tid) = targets[0];
    ti *= -1, tj *= -1;

    for (int d = 0; d < 8; d++) {
        int ni = rudolp.r + ds[d][0], nj = rudolp.c + ds[d][1];
        if (!InGrid(ni, nj)) continue;

        int curDist = Dist(ni, nj, ti, tj);
        if (curDist < bestDist) {
            bestDist = curDist;
            best_ni = ni, best_nj = nj;
            best_dir = d;
        }
    }

    grid[rudolp.r][rudolp.c] = EMPTY;
    rudolp.r = best_ni, rudolp.c = best_nj;
    if (grid[rudolp.r][rudolp.c] != EMPTY) {
        int nextId = grid[rudolp.r][rudolp.c];
        grid[rudolp.r][rudolp.c] = RUDOLP;
        CollideRtoS(nextId, best_dir);
    }
    else {
        grid[rudolp.r][rudolp.c] = RUDOLP;
    }
}

void CollideStoR(int id, int dir) {
    santas[id].score += d;
    santas[id].stun = turn + 2;
    int opposDir = (dir + 2) % 4;

    int ni = santas[id].r + ds[opposDir][0] * d;
    int nj = santas[id].c + ds[opposDir][1] * d;

    if (!InGrid(ni, nj)) {
        santas[id].onGrid = false;
        return;
    }

    santas[id].r = ni, santas[id].c = nj;
    if (grid[ni][nj] > 0) {
        int nextId = grid[ni][nj];
        grid[ni][nj] = id;
        Correlation(nextId, opposDir);
        return;
    }

    if (grid[ni][nj] == EMPTY) {
        grid[ni][nj] = id;
        return;
    }
}

void SantasMove() {
    for (int s = 1; s <= p; s++) {
        // 탈락한 산타는 움직이지 않음.
        if (!santas[s].onGrid) continue;
        // k턴에서 기절한 산타는 k+1턴까지는 움직이지 않음.
        if (santas[s].stun > turn) continue;

        int ci = santas[s].r, cj = santas[s].c;
        int bestDist = Dist(rudolp.r, rudolp.c, ci, cj);
        int best_i = -1, best_j = -1, best_dir = -1;

        for (int d = 0; d < 4; d++) {
            int ni = ci + ds[d][0], nj = cj + ds[d][1];

            if (!InGrid(ni, nj)) continue;
            if (grid[ni][nj] > 0) continue;
            int curDist = Dist(rudolp.r, rudolp.c, ni, nj);
            if (curDist < bestDist) {
                bestDist = curDist;
                best_i = ni, best_j = nj, best_dir = d;
            }
        }
        // 가까워질 수 있는 방법이 없다면 움직이지 않는다.
        if (best_i == -1) continue;

        grid[ci][cj] = EMPTY;
        santas[s].r = best_i, santas[s].c = best_j;
        if (grid[santas[s].r][santas[s].c] == RUDOLP) {
            CollideStoR(s, best_dir);
        }
        else {
            grid[santas[s].r][santas[s].c] = s;
        }
    }
}

bool Finish() {
    for (int s = 1; s <= p; s++) {
        if (santas[s].onGrid) return false;
    }
    return true;
}

void PrintScore() {
    for (int s = 1; s <= p; s++) {
        cout << santas[s].score << ' ';
    }
    cout << endl;
}

void Salary() {
    for (int s = 1; s <= p; s++) {
        if (!santas[s].onGrid) continue;
        santas[s].score++;
    }
}

int main() {
    Init();

    while(++turn <= m) {
        RudolpMove();

        SantasMove();

        if (Finish()) break;

        Salary();
    }

    PrintScore();

    return 0;
}

• 수행 시간 : 8ms
• 메모리 : 2028KB

Learnings

• 전처리를 하면 좋은 문제였다.
• 실전에서도 이렇게 전처리 생각이 먼저 떠오르려나.
  • 미지의 영역 탈출도 같은 논리였다.
• 전처리를 하고 수행하니까 8ms에서 0ms로 줄었다.

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;
// 1-based
#define MAX_N 21
#define MAX_M 21

#define EAST 0
#define SOUTH 1
#define WEST 2
#define NORTH 3

int n, m, k;
int score;
int scoreBoard[MAX_N][MAX_M];
bool visited[MAX_N][MAX_M];
int preprocessedBoard[MAX_N][MAX_M];

struct Dice {
    int r;
    int c;
    int dir;
    int top;
    int front;
    int right;

    Dice() :
        r(1), c(1), dir(EAST), top(1), front(5), right(3) {
    }
};
Dice dice;

// 동, 남, 서, 북
const int ds[4][2] = {
    {0,1},
    {1,0},
    {0,-1},
    {-1,0}
};

void Init() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> scoreBoard[i][j];
        }
    }
}

bool InGrid(int i, int j) {
    return 1 <= i && i <= n && 1 <= j && j <= m;
}

void ScoreBFS(int i, int j) {
    int curNum = scoreBoard[i][j];
    queue<pair<int, int>> q;
    vector<pair<int, int>> curArea;

    q.push({ i, j });
    curArea.push_back({ i, j });
    visited[i][j] = true;

    while (!q.empty()) {
        int ci = q.front().first, cj = q.front().second;
        q.pop();

        for (int d = 0; d < 4; d++) {
            int ni = ci + ds[d][0], nj = cj + ds[d][1];

            if (!InGrid(ni, nj) || visited[ni][nj] || scoreBoard[ni][nj] != curNum) continue;

            visited[ni][nj] = true;
            q.push({ ni, nj });
            curArea.push_back({ ni, nj });
        }
    }

    for (int i = 0; i < curArea.size(); i++) {
        preprocessedBoard[curArea[i].first][curArea[i].second] = curNum * curArea.size();
    }
}

void ScoreBoardPreprocess() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (visited[i][j]) continue;
            ScoreBFS(i, j);
        }
    }
}

void Translator(int dir) {
    int ct = dice.top, cf = dice.front, cr = dice.right;
    if (dir == EAST) {
        dice.top = 7 - cr;
        dice.right = ct;
    }
    else if (dir == WEST) {
        dice.top = cr;
        dice.right = 7 - ct;
    }
    else if (dir == SOUTH) {
        dice.front = ct;
        dice.top = 7 - cf;
    }
    else if (dir == NORTH) {
        dice.front = 7 - ct;
        dice.top = cf;
    }
}

void Roll() {
    int cd = dice.dir;
    int ni = dice.r + ds[cd][0], nj = dice.c + ds[cd][1];
    if (!InGrid(ni, nj)) {
        cd = (cd + 2) % 4;
        ni = dice.r + ds[cd][0], nj = dice.c + ds[cd][1];

    }

    dice.r = ni, dice.c = nj, dice.dir = cd;
    Translator(cd);
}

void NextDir() {
    int A = 7 - dice.top, B = scoreBoard[dice.r][dice.c];
    if (A > B) dice.dir = (dice.dir + 1 == 4) ? 0 : dice.dir + 1;
    else if (A < B) dice.dir = (dice.dir - 1 == -1) ? 3 : dice.dir - 1;
}

int main() {
    Init();

    ScoreBoardPreprocess();

    for (int turn = 1; turn <= k; turn++) {
        Roll();

        score += preprocessedBoard[dice.r][dice.c];

        NextDir();
    }

    cout << score;

    return 0;
}