uang's blog

https://www.acmicpc.net/problem/17144

요즘은 시뮬레이션 문제 푸는게 재밌는 것 같다..

복잡한 알고리즘 고민없이 코딩할 수 있어서 그런가,,

마냥 구현만 하면 풀 수 있는 문제들이라 아무 생각없이 풀 수 있어 좋은 것 같다(생각없이 풀다보니 코드는 개판이 된다)

미세먼지 안녕! 문제는 1) 확산 2) 공기 순환을 구현하면 풀 수 있다.

확산에서 중요한 점은 확산 전 원본 배열을 기준으로 계산을 쭉 진행해야 하기 때문에, 새로운 배열이 필요하다.

나는 memcpy를 이용해 새로운 배열을 만들었고, O(n*2), n 이 1000 이하라 시간안에는 돌아가지만,

예전에 어떤 문제를 풀면서 memcpy가 상당히 느리다는 것을 알았다.. 직접 for문 돌린게 더 빨랐던 것 같기도

공기 순환은 rotate 라는 이름(함수 이름 짓기가 젤 어렵다)으로 구현했는데, 사실 실수가 많이 발생할 법한 구현이다.

left, right, up, down 으로 각각 쪼개서 구현해서, 시계방향은 down -> right -> up -> left 순서로 덮어써가고,
반시계방향은  up -> right -> down -> left 순서로 덮어써가면 실수를 줄일 수 있을 것 같다.

시뮬레이션 문제의 핵심은 구현 중 발생할 수 있는 실수를 최대한 줄이는게 핵심일 것 같다..

사실 좋은 코드는 실무에서 굉장히 중요하지만, 알고리즘을 풀면서 코드의 질이 크게 중요한 가 싶다 (변명 아님..)

소스코드

#include<stdio.h>
#include<string.h>
int arr[1111][1111], r,c,t;
int dy[4] = {-1,1,0,0}, dx[4] = {0,0,-1,1};
 
void rotate(int y, int x, int y_dir){
  arr[y+y_dir][x] = 0;
 
  for(int i=y+y_dir; i != (y_dir == -1 ? 0 : r-1); i += y_dir){
    arr[i][x] = arr[i+y_dir][x];
  }
 
  int y_ = y_dir == -1 ? 0 : r-1;
  for(int i=0; i<c-1; i++){
    arr[y_][i] = arr[y_][i+1];
  }
 
  for(int i=y_; i != y; i-= y_dir){
    arr[i][c-1] = arr[i-y_dir][c-1];
  }
 
  for(int i=c-1; i-1>0; i--){
    arr[y][i] = arr[y][i-1];
    arr[y][i-1] = 0;
  }
}
 
void spread(){
  int new_arr[1111][1111] = {0};
  memcpy(new_arr, arr, sizeof(arr));
  for(int i=0; i<r; i++){
    for(int j=0; j<c; j++){
      if(arr[i][j] >= 5){
        int cnt = 0;
        for(int d=0; d<4;d++){
          int ny = i+dy[d], nx = j+dx[d];
          if(ny>=0 && ny< r&& nx>=0 && nx< c && arr[ny][nx] != -1){
            cnt+=1;
            new_arr[ny][nx] += arr[i][j]/5;
          }
        }
        new_arr[i][j] -= arr[i][j]/5 * cnt;
      }
    }
  }
  memcpy(arr, new_arr, sizeof(arr));
}
int main(){
  int src_y = -1;
  scanf("%d%d%d", &r,&c,&t);
 
  for(int i=0;i<r;i++){
    for(int j=0; j<c; j++){
      scanf("%d", &arr[i][j]);
    }
    if(arr[i][0] == -1 && src_y == -1)
      src_y = i;
  }
 
  for(int i=0; i<t; i++){
    spread();
    rotate(src_y, 0, -1);
    rotate(src_y+1, 0, 1);
  }
  int ans= 0;
  for(int i=0;i<r;i++){
    for(int j=0; j<c;j++){
      ans += arr[i][j];
    }
  }
 
  printf("%d\n", ans+2);
  return 0;
}
 

https://www.acmicpc.net/problem/14891

위 문제는 시뮬레이션 문제로 자성을 가진 톱니바퀴의 극에 따라 k번 회전 시켰을 때,

톱니바퀴의 변화를 잘 구현해야하는 문제이다.

톱니바퀴는 다음과 같이 반시계방향 / 시계방향으로 회전할 수 있다.

톱니바퀴의 수는 다음과 같이 4개로 고정돼 있다. 그리고 맞닿아 있는 극이 다를 경우 회전이 영향받는다. 즉, 만약 1 번 톱니바퀴가 반시계방향으로 회전하는 경우 2번째 톱니바퀴의 맞닿아 있는 극이 서로 다르므로, 2번 째 톱니바퀴는 반대방향인 시계방향으로 회전한다. 그리고 2번 톱니바퀴와 3번 톱니바퀴의 맞닿아 있는 극은 같기 때문에 2번이 회전할 때 3번 톱니바퀴는 회전하지 않는다.

그럼 문제는 이해했고, 회전을 어떻게 구현할까.

CPP 에는 rotate 라는 함수를 지원한다. 입력에서 8개의 정수로 N,S 극을 표현하기 때문에, 회전 시 rotate함수로 배열을 적절히 회전시킬 수 있다. 만약 rotate를 사용하지 않는다면, 각 톱니바퀴의 현재 left / right 의 극 index를 저장하는 방법이 있겠다. 

개인적으로 시뮬레이션 문제를 풀 때는 직관적인 것이 풀기 편해 rotate를 사용했다.

# rotate 사용법

#include <vector>
#include <iostream>
#include <algorithm>
 
auto print = [](auto const& remark, auto const& v) {
    std::cout << remark;
    for (int n: v)
        std::cout << n << ' ';
    std::cout << '\n';
};
 
int main()
{
    std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};
 
    print("before sort:\t\t", v);
 
    // insertion sort
    for (auto i = v.begin(); i != v.end(); ++i) {
        std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);
    }
 
    print("after sort:\t\t", v);
 
    // simple rotation to the left
    std::rotate(v.begin(), v.begin() + 1, v.end());
 
    print("simple rotate left:\t", v);
 
    // simple rotation to the right
    std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());
 
    print("simple rotate right:\t", v);
}

Output :

before sort:            2 4 2 0 5 10 7 3 7 1 
after sort:             0 1 2 2 3 4 5 7 7 10 
simple rotate left:     1 2 2 3 4 5 7 7 10 0 
simple rotate right:    0 1 2 2 3 4 5 7 7 10

k 번 톱니바퀴를 회전 시키는데, 각 회전마다 왼쪽 / 오른쪽 회전이 전파돼야 한다. 

전파를 위해 propagate 함수를 정의 했다. propagate의 역할은 현재 회전한 톱니바퀴의 다음(왼쪽 / 오른쪽) 톱니바퀴의 회전여부를 검사하고, 만약 회전할 경우 그 다음 톱니바퀴로 전파한다.

소스코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define LEFT_T 6 // 왼쪽 톱니바퀴 index
#define RIGHT_T 2 // 오른쪽 톱니바퀴 index
using namespace std;
int k;
vector< vector<int> >t(4);
 
void left(vector<int>& v){
  rotate(v.begin(), v.begin()+1, v.end());
}
 
void right(vector<int>& v){
  rotate(v.rbegin(), v.rbegin()+1, v.rend());
}
 
void rotate(vector<int>& v, int t_dir){
  if(t_dir == 1) right(v);
  else left(v);
}
 
void propagate(int prev_idx, int t_dir, int prop_dir){
  // prev_idx : 회전을 전파한 톱니바퀴
  // t_dir : 이전 톱니바퀴가 회전한 방향
  // prop_dir : propagation의 방향
 
  int cur_t = prev_idx + prop_dir;
  if(cur_t < 0 || cur_t > 3) return;
 
  int prev_tl = t[prev_idx][LEFT_T], prev_tr = t[prev_idx][RIGHT_T];
  int cur_tl = t[cur_t][LEFT_T], cur_tr = t[cur_t][RIGHT_T];
 
  if(prop_dir == -1){ //left propagation
    if(cur_tr != prev_tl){
      propagate(cur_t, -t_dir, prop_dir);
    } else return;
  } else {
    if(prev_tr != cur_tl){ // right propagation
      propagate(cur_t, -t_dir, prop_dir);
    } else return;
  }
  rotate(t[cur_t], -t_dir);
}
 
int main(){
  for(int i=0;i<4;i++){
    for(int j=0; j<8; j++){
      int m;
      scanf("%1d", &m);
      t[i].push_back(m);
    }
  }
  scanf("%d", &k);
  for(int i=0; i<k; i++){
    int cur_t, rot;
    scanf("%d%d", &cur_t, &rot);
    cur_t -= 1;
 
    // 왼쪽 전파
    propagate(cur_t, rot, -1);
    // 오픈쪽 전파
    propagate(cur_t, rot, 1);
 
    // 현재 톱니바퀴 회전
    rotate(t[cur_t], rot);
  }
 
  int ans = 0;
  for(int i=0;i<4;i++){
    ans += t[i][0] << i;
  }
  printf("%d\n",ans);
  return 0;
}
 

https://www.acmicpc.net/problem/14503

위 문제는 시뮬레이션 문제이며, 구현만 잘 하면 쉽게 풀 수 있다.

시뮬레이션 문제를 푸는 것에 있어 가장 중요한 점은 동작과정을 정확히 이해하고, 그대로 구현해야 한다는 점인 것 같다.

위 로봇 청소기 문제는 동작은 간단하지만 현재 바라보고 있는 방향이 가장 중요하다.

2번 째 행동이 a, b, c, d 4가지 경우가 있는데, 크게 a,b 와 c,d 로 묶을 수 있을 것 같다.

a,b 는 왼쪽 방향으로 돌아가며 순차적으로 탐색해나가는 과정의 조건이고, c,d는 4방향을 모두 탐색한 후의 행동이다.



시뮬레이션 문제에서 동작은 하나씩 모두 잘게 쪼개는 것이 중요하다. 이 문제에서는 현재 바라보는 방향이 가장 중요하므로, 

신경쓰도록 하자.

직접 동작을 쪼개보면 알겠지만, 로봇이 c 조건에 부합돼 후진해야 할 때 현재 바라보는 방향은 처음 진입한 방향의 오른쪽 방향이다. 로봇은 현재 바라보는 방향에서 왼쪽 방향을 탐색하기 때문에 4방향 모두 탐색하는 시점은 3번 회전한 뒤이다.

(처음 북쪽을 봤다면 : 서쪽탐색 후 왼쪽 회전 ->  남쪽 탐색 후 왼쪽 회전 -> 동쪽 탐색 후 왼쪽 회전 -> 북쪽 탐색하면 4방향 모두 탐색조건 부합하므로 현재 방향은 동쪽)

d 조건에 부합되는 순간 모든 탐색과정이 종료해야 한다.

소스코드

#include<stdio.h>
int n,m,src_y, src_x, src_d, arr[55][55];
int dy[4] = {-1,0,1,0}, dx[4] = {0, 1, 0, -1};
int visited[55][55], ans;
 
int turn_left(int d){
  return d-1 >= 0 ? d-1 : 3;
}
int solve(int y,int x, int d){
  visited[y][x] = 1; // num 1
 
  int clean = 0;
  for(int i = 0; i < 4; i++){ // num 2
    int left = turn_left(d);
    int ny = y + dy[left], nx = x + dx[left];
    if(!arr[ny][nx] && !visited[ny][nx] && ny >=0 && nx >=0 && nx < m && ny < n){
      d = left;
      if(solve(ny, nx, d) == -1) return -1;
      clean = 1;
    } else
      d = left;
  }
  if(!clean){
    int ny = y-dy[d], nx= x-dx[d];
    if(!arr[ny][nx] && ny >= 0 && nx >= 0 && nx < m && ny < n){
      if(solve(ny, nx, d) == -1) return -1;
    } else {
      return -1;
    }
  }
  return 0;
}
int main(){
  scanf("%d%d %d %d %d",&n,&m,&src_y, &src_x, &src_d);
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      scanf("%d", &arr[i][j]);
    }
  }
 
  solve(src_y, src_x, src_d);
 
  for(int i=0; i < n; i++){
    for(int j=0; j < m; j++){
      ans += visited[i][j];
    }
  }
  printf("%d\n", ans);
  return 0;
}

https://www.acmicpc.net/problem/1969

이 문제는 brute force 문제이다

DNA 염기 { A, C, G, T } 로 구성된 문자열이 N개 주어졌을 때, 각 자리수의 가장 빈도수가 많은 문자만 뽑으면 된다

문제에서는 Hamming distance 등 생소한 용어로 혼란을 주지만 문제 자체만 보면 각 자리수의 빈도수가 가장 높은 문자만

뽑으면 그것이 전체 DNA sequence 중 가장 차이가 적은 문자열이 된다

counting을 위해서 map 자료구조를 이용했고, 사전 순을 맞추기 위해 max 를 검사할 때 사전 순으로 검사하도록 한다

소스코드

#include<stdio.h>
#include<vector>
#include<string>
#include<map>
using namespace std;
int n,m;
char buf[55];
char order[4] = { 'A', 'C', 'G', 'T'};
 
int main(){
  scanf("%d %d",&n,&m);
  vector<string> v;
  for(int i=0;i<n;i++){
    scanf(" %s", buf);
    v.push_back(string(buf));
  }
  vector< pair<char, int> > ans;
  for(int i=0; i<m; i++){
    map<char, int> c;
    for(int o=0; o<4; o++)
      c[order[o]] = 0;    
    for(int j=0; j<n; j++){
      c[v[j][i]] += 1;
    }
    int max_ = 0, diff = 0;
    char d;
    for(int o=0; o<4; o++){
      diff += c[order[o]];
      if(max_ < c[order[o]]){
        max_ = c[order[o]];
        d = order[o];
      }
    }
    ans.push_back(make_pair(d, diff-max_));
  }
  int cnt = 0;
  for(int i=0;i<ans.size();i++){
    printf("%c", ans[i].first);
    cnt += ans[i].second;
  }
  printf("\n%d\n", cnt);
  return 0;
}

https://www.acmicpc.net/problem/2529

문제의 조건 

1. k 는 2보다 크거나 같고, 9보다 작거나 같다

2. k+1개의 숫자는 서로 다른 숫자이다

3. k개의 부등호에 맞는 값 중 최대값, 최소값을 구해야 한다

부등호에 '<=', '>=' 이 존재하고 서로 다른 숫자라는 조건이 없었다면, 경우의 수가 1e10 이 돼 TLE이 나겠지만, 

서로 다른 k+1 개의 수를 찾기 때문에 (k+1)! 의 경우의 수만 찾으면 된다.

처음에는 재귀함수를 통해 백트랙킹으로 풀었다.

소스코드 (백트랙킹)

숫자가 최대 10개이므로 비트마스크로 사용한 숫자를 체크하며, 조건이 맞지 않으면 재귀를 탈출하고, 

k+1 개의 숫자를 다 채우면 1을 리턴하면서 종료된다.

최솟값은 0부터 시작해서 찾아야하고, 최댓값은 9부터 시작해서 내려가며 찾아야하기 때문에

같은 재귀라도 반복문을 달리 사용해야하는 번거로움이 있었다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
int k;
char karr[11];
string min_="", max_="";
bool inline chk(int a, char c, int b){
    return c == '>' ? a>b : a<b;
}
string num(vector<int>& ans){
    string s = "";
    for(int i=0; i < ans.size(); i++){
        s += ans[i] + '0';
    }
    return s;
}
int solve(vector<int>& ans, int visited, int p, int ismax){
    if(p == k) {
        return 1;
    }
    int cur = ans[p];
    int init = ismax ? 9 : 0;
    int iter = ismax ? -1 : 1;
    int end = ismax ? -1 : 10;
    for(int pp1=init; pp1 != end; pp1+=iter){
        if(visited & (1<<pp1))
            continue;
 
        if(chk(cur, karr[p], pp1)){
            ans.push_back(pp1);
            if(solve(ans, visited | (1<<pp1), p+1, ismax))
                return 1;
            ans.pop_back();
        }
    }
    return 0;
}
string solve_(int i, int ismax){
    int visited = 0;
    vector<int>ans;
 
    ans.push_back(i);
    visited |= (1<<i);
    if(solve(ans, visited, 0, ismax)){
        return num(ans);
    }
    return "";
}
int main(){
    scanf("%d", &k);
    for(int i=0;i<k;i++){
        scanf(" %c", &karr[i]);
    }
 
    for(int i=0; i<10; i++){
        min_ = solve_(i, 0);
        if(min_ != "") break;
    }
 
    for(int i=9; i>=0; i--){
        max_ = solve_(i, 1);
        if(max_ != "") break;
    }
    printf("%s\n%s\n", max_.c_str(), min_.c_str());
    return 0;
}

풀다보니 최소값은 0~k 의 숫자, 최대값은 9~9-k 까지의 숫자만 사용하면 부등호를 만족하는 순서를 찾을 수 있기 때문에,

k 가 9인 경우 최대 10! 까지만 돌기 때문에 조합으로 풀 수 있겠다 생각됐다.

소스코드 (조합)

조합으로 푸니 코드가 깔끔해졌다.. 진작 이렇게 풀걸

처음부터 조합으로 풀 생각을 할 수 있도록 문제 해결 전략을 잘 세워야겠다..

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int k;
char karr[10];
bool inline chk_(int a, char c, int b){
    return c == '>' ? a>b : a<b;
}
int chk(vector<int>& cand){
    for(int i=0; i<k; i++){
        if(!chk_(cand[i], karr[i], cand[i+1]))
            return 0;
    }
    return 1;
}
int main(){
    scanf("%d", &k);
    for(int i=0; i<k;i++)
        scanf(" %c", &karr[i]);
 
    vector<int> min_ = vector<int>(k+1), max_ = vector<int>(k+1);
    for(int i=0; i<=k; i++){
        min_[i] = i;
        max_[i] = 9-i;
    }
 
    do{
        if(chk(min_)) break;
    }while(next_permutation(min_.begin(), min_.end()));
 
    do{
        if(chk(max_)) break;
    }while(prev_permutation(max_.begin(), max_.end()));
 
    for(int i=0; i<=k; i++)
        printf("%d",max_[i]);
    printf("\n");
    for(int i=0; i<=k; i++)
        printf("%d",min_[i]);
    printf("\n");
    return 0;
}

www.acmicpc.net/problem/17472

이 문제는 DFS, MST(최소신장트리) 를 이용해 푸는 문제이다. 질문 게시판을 보니 삼성 코딩테스트 기출문제인듯 하다. 위 문제 풀이 방법 중 핵심은 인접한 셀들을 "섬"으로써 잘 Grouping 하여, 다른 "섬"(group)과의 최단거리를 찾아야 한다. 

일단 필요한 알고리즘들을 생각해보면,

   1. DFS : 섬의 개수 세기

   2. MST(최소신장트리) : 모든 섬들을 연결하는 최단 간선 구하기 

이다.

MST 에는 크루스칼(Kruskal) 알고리즘, 프림(prim) 알고리즘이 있다. 

크루스칼 알고리즘

간선의 가중치를 정렬해 작은 것 부터 차례로 선택해나가는 방법

1. 간선들을 가중치의 오름차순으로 정렬한다
2. 정렬된 간선 중 사이클을 형성하지 않는 간선을 선택
3. 해당 간선을 현재 MST 집합에 추가
4. 1~3 과정을 "|정점 수| - 1" 번 반복  // V 개의 정점을 연결하기 위해 필요한 간선은 V-1개 이므로

프림 알고리즘

하나의 정점을 선택해 가장 가중치가 작은 간선들을 차례로 연결해나가는 방법

1.  시작 노드(어떤 노드든 상관없음) 를 MST 집합에 포함
2.  1단계에서 만들어진 MST 집합에 인접한 노드들 중 최소 간선으로 연결된 노드를 선택해 MST 집합에 포함
3.  1~2 과정을 "|정점 수| - 1" 번 반복  // V 개의 정점을 연결하기 위해 필요한 간선은 V-1개 이므

프림알고리즘의 구현을 위해선 priority_queue(우선순위 큐)가 필요할 수 있지만, 본 문제에서는 간선을 우리가 만들어가며 찾아야하기 때문에 BFS(너비우선탐색)를 통해 찾는 것이 적절하다. 같은 이유로 Kruskal 알고리즘을 사용하기 복잡하다.

대략 알고리즘을 설명하면 다음과 같다.

1. 섬의 갯수 찾기 (DFS)

    - 각 섬의 Grouping을 위해 ID 를 부여한다.

2. 섬의 갯수-1 번 반복하여 다른 그룹의 섬을 잇는 간선 찾기 (BFS)

    - 1번 섬을 기준으로 BFS를 통해 최단거리의 다른 섬(그룹)을 찾으면 1번 그룹에 병합 (Union-Find 개념)

    * 탐색 할 때는 가로/세로 방향 유지

* Union-Find 알고리즘 참고 : https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

소스코드

#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
 
struct node{
    pair<int,int> cur;
    int cnt_bridge, is_vertical;
    node(pair<int,int> cur, int  cnt, int is_v) : cur(cur), cnt_bridge(cnt), is_vertical(is_v)  {};
};
 
int n,m, dx[4]= { -1,1,0,0}, dy[4] = {0,0,-1,1}, arr[11][11];
bool visited[11][11][2];
vector< pair<int,int> > island[7];
 
void find_island(int idx, int y,int x){
    visited[y][x][0] = 1;
    island[idx].push_back(make_pair(y,x));
    arr[y][x] = idx+1;
    for(int i=0;i<4;i++){
        int ny = y + dy[i], nx = x+dx[i];
        if(ny>=0 && nx >=0 && nx < m && ny < n){
            if(!visited[ny][nx][0] && arr[ny][nx]){
                find_island(idx, ny, nx);
            }
        }
    }
}
 
void push_queue(queue< node >& q, int island_idx=1){
    int idx = island_idx-1; // 1번 그룹 
 
    for(int i=0; i< island[idx].size(); i++){
        q.push(node(island[idx][i], 0, -1));
    }
    // printf("push queue #%d, queue_size : %d\n", island_idx, q.size());
}
 
void Union(int found_island_idx){
    int& idx = found_island_idx;
    for(int i=0;i<n; i++){
        for(int j=0; j<m;j++){
            if(arr[i][j] == idx){
                island[0].push_back(make_pair(i,j));
                arr[i][j] = 1;
            }
        }
    }
 
    // printf("union between 1 and %d\n\n", idx);
    // for(int i=0;i<n; i++){
    //     for(int j=0; j<m;j++){
    //         printf("%d ",arr[i][j]);
    //     }
    //     printf("\n");
    // }
}
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0; j<m; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    int cnt_island = 0;
    for(int i=0; i<n;i++){
        for(int j=0; j<m;j++){
            if(!visited[i][j][0] && arr[i][j]){
                find_island(cnt_island, i,j);
                cnt_island += 1;
            }
        }
    }
 
    // printf("\n");
    // for(int i=0; i<n;i++){
    //     for(int j=0; j<m;j++){
    //         printf("%d ", arr[i][j]);
    //     }
    //     printf("\n");
    // }
    // cnt_islend-1 edges are needed to connect all island
    int ans = 0, edges = 0;
    for(int i=0; i<cnt_island-1; i++){
        memset(visited, 0, sizeof(visited));
        queue< node > q;
        push_queue(q, 1); 
 
        while(!q.empty()){
            node cur = q.front(); q.pop();
            int cury = cur.cur.first, curx = cur.cur.second;
 
            // another island check
            if(arr[cury][curx] > 1 && cur.cnt_bridge >= 2) {
                // printf("found another island#%d at (%d,%d): %d\n", arr[cury][curx], cury,curx, cur.cnt_bridge);
                int island_idx = arr[cury][curx];
                ans += cur.cnt_bridge;
                edges += 1;
                Union(island_idx);
                break;
            }
 
            // cannot pass through another island
            if(arr[cury][curx] > 1){
                continue;
            }
 
            if(cur.is_vertical == -1){
                visited[ cury ][ curx ][0] = visited[ cury ][ curx ][1] = 1;
            } else {
                visited[ cury ][ curx ][cur.is_vertical] = 1;
            }
 
            // build  bridge to search island
            for(int d=0; d<4;d++){
                int ny = cury + dy[d], nx = curx + dx[d];
                if(ny >= 0 && nx >=0 && nx < m && ny < n && arr[ny][nx] != 1 && !visited[ny][nx][cury!=ny]){
                    if( cur.is_vertical == -1 ){ // all directions
                        q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), cury != ny));
                    } else if (cur.is_vertical == 1 && cury != ny){
                        q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), 1));
                    } else if (cur.is_vertical == 0 && cury == ny) { // horizontal
                        q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), 0));
                    }
                }
            }
        }
    }
    printf("%d\n", (ans == 0 || edges != cnt_island-1) ? -1 : ans);
    return 0;
}
 

www.acmicpc.net/problem/1305

위 문제는 길이가 N 인 광고판에 문자열 길이가 L 인 광고가 왼쪽 쉬프트를 하며 무한히 나타날 때, 가능한 문자열의 최소 길이를 구하는 문제이다. 즉, 광고판 길이가 6이고 현재 광고판의 문자열이 "aabaaa" 일때, 가능한 문자열 후보는 "aaba", "aaab", "abaa", "aabaa", "abaaa" 등 다양하지만, 가장 짧은 길이는 4이다.

이 문제는 KMP 알고리즘에서 사용하는 pi 배열을 이용하여 풀 수 있다. pi 배열은 접두사(prefix) 와 접미사(suffix)가 같은 부분 문자열 중 가장 길이가 긴 것을 저장한다.

"ABADABC" 라는 문자열이 있을 때, pi는 다음과 같이 저장된다.

KMP는 이 pi배열을 이용해 문자열 검색의 시간 복잡도를 O( |S| * |P| ), (S : 전체 문자열, P : 전체 문자열에서 찾고자하는 패턴(검색) 문자열) 에서 O( |S|+|P| ) 로 줄이는 알고리즘이다.

1305 광고문제는 검색까지는 필요없고, Pi만 배열만 있으면 풀 수 있다.

길이가 N인 광고판과 길이가 L (L <= N) 인 문자열이 있을 때, 앞의 X개의 문자열(진한 파란색)은 광고 문자열 L번째 문자 뒤에 반복된다.

즉, N길이의 광고판 문자열에 대해 pi 를 구한 후, N-pi[N]을 구하면 답을 구할 수 있다.

소스코드

소스는 백준님 풀이 방식을 기반으로 구현했습니다.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
vector<int> get_pi_array(string s){
    int n = s.size();
    vector<int>pi(n);
    pi[0] = 0;
    int j = 0;
    for(int i=1; i < n; i++){
        while(j>0 && s[i] != s[j]){
            j = pi[j-1];
        }
        if(s[i] == s[j]){
            pi[i] = j + 1;
            j += 1;
        } else {
            pi[i] = 0;
        }
    }
    return pi;
}
 
int main(){
    int n;
    string s;
    cin >> n >> s;
    vector<int> pi = get_pi_array(s);
    cout << n - pi[n-1] << '\n';
    return 0;
}

관련 사이트:

bowbowbow.tistory.com/6

m.blog.naver.com/kks227/220917078260

https://www.acmicpc.net/problem/10826

이 문제는 BOJ2407 조합 문제와 같이 피보나치 10000 의 자릿수가 2000 이 넘어가기 때문에 c++ 표준 자료형의 범위로는 표현할 수 없다. 마찬가지로 string 덧셈으로 풀 수 있는데, 이전 BOJ2407 번에서 구현한 string 덧셈이 비효율적이라 시간초과가 난다. 따라서 string 덧셈과정에서 역순으로 += 연산을 최대한 이용할 수 있도록 구현하여 시간제한 안에 풀 수 있도록 구현하였다.

새롭게 안 사실인데, 피보나치 4 문제의 질문 게시글 에서 문자열의 덧셈 방법 s = s + "string" 과 s += "string" 이 다르다는 것을 설명한다. 첫 번째 방법(s = s + "string") 은 string 을 새롭게 복사하기 때문에 O(s.size()^2) 의 시간이 걸린다고 한다. 두 번째 방법은 단순히 이어 붙이기 때문에, 시간적으로 매우 차이가 날 수 있다.

소스코드

https://www.acmicpc.net/problem/1516

이 문제는 위상정렬로 풀 수 있는 문제이다. 위상 정렬은 주로 게임에서 스킬트리와 같은 즉, 선행되어야 하는 작업이 있을 때의 순서를 어떻게 처리해야 빠른지를 풀 때 사용하는 알고리즘이다. 위상정렬의 구현은 그래프 구조에서 in-direction 의 갯수를 저장하는 배열이 가장 핵심이다. 즉 어떤 노드 K 번에 들어오는 간선의 수가 3개가 있을 때, ind[K] = 3 처럼 저장한 뒤, ind[i] 값이 0인 정점부터 큐(queue)에 넣고 순차적으로 탐색해가면 된다.

위 그림으로 설명하면

 1. ind 값이 0 인 1번 3번 노드가 queue에 넣는다.
 2. 큐에 가장 앞에 있는 노드를 방문(1 번) 한 후, 이 노드에 연결된 (2 번으로의)간선을 돌면서 ind[ graph[cur][next] ] 의 값을 -1 해준다.
     ( 그림에선 2번으로의 간선이므로, ind[2]--; )
 3. 만약 2번의 과정을 통해서 ind 값이 0 이 되면(ind[ graph[cur][next] ] == 0) 해당 노드를 queue에 push 한다.
 4. 2~3번을 반복

소스코드

https://www.acmicpc.net/problem/2407

이 문제는 100 C 50 조합 값이 long long int 를 벗어나는 약 30자리 수 정도이기 때문에, 다른 방법으로 덧셈을 계산해야 한다. 따라서 덧셈을 위해 string 클래스를 이용해 문자열끼리의 더하기를 구현하였다.

다음은 100_C_n 의 조합의 결과 : 

(100C1) : 1 + 99 = 100
(100C2) : 99 + 4851 = 4950
(100C3) : 4851 + 156849 = 161700
(100C4) : 156849 + 3764376 = 3921225
(100C5) : 3764376 + 71523144 = 75287520
(100C6) : 71523144 + 1120529256 = 1192052400
(100C7) : 1120529256 + 14887031544 = 16007560800
(100C8) : 14887031544 + 171200862756 = 186087894300
(100C9) : 171200862756 + 1731030945644 = 1902231808400
(100C10) : 1731030945644 + 15579278510796 = 17310309456440
(100C11) : 15579278510796 + 126050526132804 = 141629804643600
(100C12) : 126050526132804 + 924370524973896 = 1050421051106700
(100C13) : 924370524973896 + 6186171974825304 = 7110542499799200
(100C14) : 6186171974825304 + 38000770702498296 = 44186942677323600
(100C15) : 38000770702498296 + 215337700647490344 = 253338471349988640
(100C16) : 215337700647490344 + 1130522928399324306 = 1345860629046814650
(100C17) : 1130522928399324306 + 5519611944537877494 = 6650134872937201800
(100C18) : 5519611944537877494 + 25144898858450330806 = 30664510802988208300
(100C19) : 25144898858450330806 + 107196674080761936594 = 132341572939212267400
(100C20) : 107196674080761936594 + 428786696323047746376 = 535983370403809682970
(100C21) : 428786696323047746376 + 1613054714739084379224 = 2041841411062132125600
(100C22) : 1613054714739084379224 + 5719012170438571889976 = 7332066885177656269200
(100C23) : 5719012170438571889976 + 19146258135816088501224 = 24865270306254660391200
(100C24) : 19146258135816088501224 + 60629817430084280253876 = 79776075565900368755100
(100C25) : 60629817430084280253876 + 181889452290252840761628 = 242519269720337121015504
(100C26) : 181889452290252840761628 + 517685364210719623706172 = 699574816500972464467800
(100C27) : 517685364210719623706172 + 1399667836569723427057428 = 1917353200780443050763600
(100C28) : 1399667836569723427057428 + 3599145865465003098147672 = 4998813702034726525205100
(100C29) : 3599145865465003098147672 + 8811701946483283447189128 = 12410847811948286545336800
(100C30) : 8811701946483283447189128 + 20560637875127661376774632 = 29372339821610944823963760
(100C31) : 20560637875127661376774632 + 45764000431735762419272568 = 66324638306863423796047200
(100C32) : 45764000431735762419272568 + 97248500917438495140954207 = 143012501349174257560226775
(100C33) : 97248500917438495140954207 + 197443926105102399225573693 = 294692427022540894366527900
(100C34) : 197443926105102399225573693 + 383273503615787010261407757 = 580717429720889409486981450
(100C35) : 383273503615787010261407757 + 711793649572175876199757263 = 1095067153187962886461165020
(100C36) : 711793649572175876199757263 + 1265410932572757113244012912 = 1977204582144932989443770175
(100C37) : 1265410932572757113244012912 + 2154618614921181030658724688 = 3420029547493938143902737600
(100C38) : 2154618614921181030658724688 + 3515430371713505892127392912 = 5670048986634686922786117600
(100C39) : 3515430371713505892127392912 + 5498493658321124600506947888 = 9013924030034630492634340800
(100C40) : 5498493658321124600506947888 + 8247740487481686900760421832 = 13746234145802811501267369720
(100C41) : 8247740487481686900760421832 + 11868699725888281149874753368 = 20116440213369968050635175200
(100C42) : 11868699725888281149874753368 + 16390109145274293016493707032 = 28258808871162574166368460400
(100C43) : 16390109145274293016493707032 + 21726423750712434928840495368 = 38116532895986727945334202400
(100C44) : 21726423750712434928840495368 + 27651812046361280818524266832 = 49378235797073715747364762200
(100C45) : 27651812046361280818524266832 + 33796659167774898778196326128 = 61448471214136179596720592960
(100C46) : 33796659167774898778196326128 + 39674339023040098565708730672 = 73470998190814997343905056800
(100C47) : 39674339023040098565708730672 + 44739148260023940935799206928 = 84413487283064039501507937600
(100C48) : 44739148260023940935799206928 + 48467410615025936013782474172 = 93206558875049876949581681100
(100C49) : 48467410615025936013782474172 + 50445672272782096667406248628 = 98913082887808032681188722800
(100C50) : 50445672272782096667406248628 + 50445672272782096667406248628 = 100891344545564193334812497256
(100C51) : 50445672272782096667406248628 + 48467410615025936013782474172 = 98913082887808032681188722800
(100C52) : 48467410615025936013782474172 + 44739148260023940935799206928 = 93206558875049876949581681100
(100C53) : 44739148260023940935799206928 + 39674339023040098565708730672 = 84413487283064039501507937600
(100C54) : 39674339023040098565708730672 + 33796659167774898778196326128 = 73470998190814997343905056800
(100C55) : 33796659167774898778196326128 + 27651812046361280818524266832 = 61448471214136179596720592960
(100C56) : 27651812046361280818524266832 + 21726423750712434928840495368 = 49378235797073715747364762200
(100C57) : 21726423750712434928840495368 + 16390109145274293016493707032 = 38116532895986727945334202400
(100C58) : 16390109145274293016493707032 + 11868699725888281149874753368 = 28258808871162574166368460400
(100C59) : 11868699725888281149874753368 + 8247740487481686900760421832 = 20116440213369968050635175200
(100C60) : 8247740487481686900760421832 + 5498493658321124600506947888 = 13746234145802811501267369720
(100C61) : 5498493658321124600506947888 + 3515430371713505892127392912 = 9013924030034630492634340800
(100C62) : 3515430371713505892127392912 + 2154618614921181030658724688 = 5670048986634686922786117600
(100C63) : 2154618614921181030658724688 + 1265410932572757113244012912 = 3420029547493938143902737600
(100C64) : 1265410932572757113244012912 + 711793649572175876199757263 = 1977204582144932989443770175
(100C65) : 711793649572175876199757263 + 383273503615787010261407757 = 1095067153187962886461165020
(100C66) : 383273503615787010261407757 + 197443926105102399225573693 = 580717429720889409486981450
(100C67) : 197443926105102399225573693 + 97248500917438495140954207 = 294692427022540894366527900
(100C68) : 97248500917438495140954207 + 45764000431735762419272568 = 143012501349174257560226775
(100C69) : 45764000431735762419272568 + 20560637875127661376774632 = 66324638306863423796047200
(100C70) : 20560637875127661376774632 + 8811701946483283447189128 = 29372339821610944823963760
(100C71) : 8811701946483283447189128 + 3599145865465003098147672 = 12410847811948286545336800
(100C72) : 3599145865465003098147672 + 1399667836569723427057428 = 4998813702034726525205100
(100C73) : 1399667836569723427057428 + 517685364210719623706172 = 1917353200780443050763600
(100C74) : 517685364210719623706172 + 181889452290252840761628 = 699574816500972464467800
(100C75) : 181889452290252840761628 + 60629817430084280253876 = 242519269720337121015504
(100C76) : 60629817430084280253876 + 19146258135816088501224 = 79776075565900368755100
(100C77) : 19146258135816088501224 + 5719012170438571889976 = 24865270306254660391200
(100C78) : 5719012170438571889976 + 1613054714739084379224 = 7332066885177656269200
(100C79) : 1613054714739084379224 + 428786696323047746376 = 2041841411062132125600
(100C80) : 428786696323047746376 + 107196674080761936594 = 535983370403809682970
(100C81) : 107196674080761936594 + 25144898858450330806 = 132341572939212267400
(100C82) : 25144898858450330806 + 5519611944537877494 = 30664510802988208300
(100C83) : 5519611944537877494 + 1130522928399324306 = 6650134872937201800
(100C84) : 1130522928399324306 + 215337700647490344 = 1345860629046814650
(100C85) : 215337700647490344 + 38000770702498296 = 253338471349988640
(100C86) : 38000770702498296 + 6186171974825304 = 44186942677323600
(100C87) : 6186171974825304 + 924370524973896 = 7110542499799200
(100C88) : 924370524973896 + 126050526132804 = 1050421051106700
(100C89) : 126050526132804 + 15579278510796 = 141629804643600
(100C90) : 15579278510796 + 1731030945644 = 17310309456440
(100C91) : 1731030945644 + 171200862756 = 1902231808400
(100C92) : 171200862756 + 14887031544 = 186087894300
(100C93) : 14887031544 + 1120529256 = 16007560800
(100C94) : 1120529256 + 71523144 = 1192052400
(100C95) : 71523144 + 3764376 = 75287520
(100C96) : 3764376 + 156849 = 3921225
(100C97) : 156849 + 4851 = 161700
(100C98) : 4851 + 99 = 4950
(100C99) : 99 + 1 = 100

소스코드