전형적인 네트워크 플로우 문제이다. 다만.. 조건을 꼼꼼하게 읽지 않아서 대문자와 소문자가 구분되는지를 놓쳤고, 그로 인해 단순하게 대문자 A ~ Z까지의 최대 유량을 구하는 문제인줄 알았다. 또한 추가적으로 이 문제에서 교훈이 있는데, 단순 그래프가 아닐 경우에는 capacity를 계산할 때 += 처리를 해주어야 한다는 것이다. 이 지점만 주의해주면 된다. 코드 자체는 종만북에 있는 에드몬드 카프 알고리즘 코드를 차용하였다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define INF 987654321; using namespace std; typedef long long ll; int ARR_NUM;..

앞의 술레잡기 문제와 비슷하게 가중치가 동일한 문제의 최단거리는 BFS로 처리할 수 있다. (만약 그렇지 않은 경우는 Dijikstra로 처리해야 한다.) 이 문제의 경우는 숫자가 겹칠 일이 없으므로 딱히 visited를 처리해서 진행해주지 않아도 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; typedef long long ll; typedef pair pll; int main(void){ fastio; queue data_store; int a, b; cin >> a >> b; data_store.push(make_pair(a, 0)); while(data_sto..

이 문제와 숨바꼭질1과의 차이점은 중복되는 것의 유무를 어떻게 처리할 것인가에 대한 유무이다. 앞 문제에서는 queue에 넣을 때 visited를 처리하였다. 왜냐하면 어차피 동일한 시간이 걸리는 것이 존재해도 어차피 시간이 같으므로 지워도 무방하기 때문이다. 다만, 이 문제의 경우 최소일 때 몇 가지 인지 체크해야하는 문제이므로 동일한 시간이 걸리는 경우에는 모두 다 살려주어야 한다. 즉, visited처리하는 순간이 그 이후 타이밍이어야 한다. 즉, pop시키는 순간에 visited처리해 주면 1번과 근본적으로 동일하게 접근할 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespa..

처음에 단순히 3가지 케이스를 큐에다가 넣고 처리하려고 하였다. 하지만, 문제점이 데이터가 너무 많다.. 최악의 경우 3^100000인데 너무너무 크다. 이러한 문제점이 나타나는 근본적인 이유는 중복이 되기 때문이다. 잘 생각해보면 나중에 중복되는 숫자는 이전에 나온 것 보다 무조건 시간이 더 느릴 수 밖에 없으므로 기존에 방문한 것을 제외하고 처리해주면 된다. 일종의 DP 아이디어를 활용한다고 생각해도 무방하다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; typedef pair pii; int main(void){ fastio; int N, K; cin >> N >> ..

처음에 루트노드가 0으로 고정인줄 알고 실수하였다.. 문제 자체는 되게 단순하다. 1. 트리를 구성하고 2. 특정 노드를 끊는다.(위 기준으로 끊으면 어차피 아래에 접근이 안된다.) 즉, parent node를 기준으로 해당 node를 끊어주기만 하면 된다. 다만, 가장 최상단 root node를 제거하는 경우는 따로 예외처리하도록 하자. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int arr[51][51]; int N; int dfs(int start){ bool check = true; int count = 0; for(int i = 0; i < N; i ++){ ..

대략적으로 그래프를 타고 넘어가면서 전파하는 양상이라는 것을 문제를 읽어보면 쉽게 판단할 수 있다. 처음에 생각한 방법은 DFS인데, 중간에 문제점이 있다는 것을 파악하고 포기하였다. 예를들어 DFS를 타고 넘어가면서 8분 정도에 특정 노드에 전파할 때 절반을 넘었다고 가정해보자. 단순하게 8분을 전파시점으로 생각하기 쉬우나, 이렇게 단순하게 접근하면 안된다. 예를 들어 다른 간선에서는 4분에 해당 노드에 접근을 시도했을 수도 있기 때문이다. 즉, 해당 간선을 기준으로 만족한다고 하여 그것이 가장 짧은 시간임을 보장할 수가 없게 된다. 따라서 이 부분에서 BFS를 강구한 것이다. 즉, 같은 시간에 전파되는 것들을 모두 다 처리하고 넘어가야 해당 노드에 전파되는 시점의 대소비교가 가능해진다. 귀찮아서 BF..

간단한 DFS문제이다. 사실 생각해보면 M을 기준으로 사이클 돌때를 판단해주면 된다. 주의해야할 지점은 바라보는 지점과 처리해야 하는 지점이 다르다는 것이다. 반복여부를 판단하기 위해서는 시작지점을 봐야하고, 문제에서 필요로하는 데이터는 1사이클의 마지막 데이터이기 때문이다. 다만, 일반적으로는 끝나는 데이터가 다시 시작지점이 되므로 이 부분을 핸들링해주면 되지만, 만약 1이 끝나는 지점의 경우는 예외 케이스가 발생할 수 있으므로 따로 처리해주면 된다. 추가적으로 가장 골치 아픈 지점이 다시 1로 돌아오는 것이 아니라 다른 지점으로 사이클을 형성하는 것이다. 이 부분을 해결하기 위해서 여러가지 방법이 있을 수 있다. pair 자료구조 등을 활용해서 처리할 수 있고 여러가지 방법이 존재한다. 따로 뺴서 계..

백준 16993번과 매우 유사하다. 다만 차이점이 2개 존재한다. 백준 16993번의 경우에는 단순한 금광 세그라면, 이 문제의 경우에는 U와 V를 곱해주는 과정을 수반하게 된다. 추가적으로 이 문제에서는 세그 트리를 중간에 수정함으로써 update과정을 진행해주어야 한다. 일단 처음에 고전했던 부분은 U와 V를 곱해주는 과정을 어떻게 처리할 것인지에 대한 아이디어이다. U의 경우에는 16993번에서 한 결과값에 U만 곱해주면 되는데 V의 경우가 처리하기가 처음에 껄끄러웠다. j - i를 처리해주어야 하기에 처음에는 왼쪽을 기준으로 연산했을 때와 오른쪽을 기준으로 연산했을 때의 갯수를 구조체 안에 넣을 생각을 먼저 했는데 너무 비효율적인 것 같아서 포기하였다. 사실 고민을 좀 해보면, V를 처음 init..