공통 정보 정의하고 재사용하는 방법

'개발 > YAML' 카테고리의 다른 글

YAML 간단 팁 정리  (0) 2021.04.17

www.acmicpc.net/problem/17472

 

17472번: 다리 만들기 2

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

www.acmicpc.net

 

이 문제는 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

 

 

소스코드

  1. #include<stdio.h>
  2. #include<vector>
  3. #include<queue>
  4. #include<string.h>
  5. using namespace std;
  6.  
  7. struct node{
  8. pair<int,int> cur;
  9. int cnt_bridge, is_vertical;
  10. node(pair<int,int> cur, int cnt, int is_v) : cur(cur), cnt_bridge(cnt), is_vertical(is_v) {};
  11. };
  12.  
  13. int n,m, dx[4]= { -1,1,0,0}, dy[4] = {0,0,-1,1}, arr[11][11];
  14. bool visited[11][11][2];
  15. vector< pair<int,int> > island[7];
  16.  
  17. void find_island(int idx, int y,int x){
  18. visited[y][x][0] = 1;
  19. island[idx].push_back(make_pair(y,x));
  20. arr[y][x] = idx+1;
  21. for(int i=0;i<4;i++){
  22. int ny = y + dy[i], nx = x+dx[i];
  23. if(ny>=0 && nx >=0 && nx < m && ny < n){
  24. if(!visited[ny][nx][0] && arr[ny][nx]){
  25. find_island(idx, ny, nx);
  26. }
  27. }
  28. }
  29. }
  30.  
  31. void push_queue(queue< node >& q, int island_idx=1){
  32. int idx = island_idx-1; // 1번 그룹
  33.  
  34. for(int i=0; i< island[idx].size(); i++){
  35. q.push(node(island[idx][i], 0, -1));
  36. }
  37. // printf("push queue #%d, queue_size : %d\n", island_idx, q.size());
  38. }
  39.  
  40. void Union(int found_island_idx){
  41. int& idx = found_island_idx;
  42. for(int i=0;i<n; i++){
  43. for(int j=0; j<m;j++){
  44. if(arr[i][j] == idx){
  45. island[0].push_back(make_pair(i,j));
  46. arr[i][j] = 1;
  47. }
  48. }
  49. }
  50.  
  51. // printf("union between 1 and %d\n\n", idx);
  52. // for(int i=0;i<n; i++){
  53. // for(int j=0; j<m;j++){
  54. // printf("%d ",arr[i][j]);
  55. // }
  56. // printf("\n");
  57. // }
  58. }
  59.  
  60. int main(){
  61. scanf("%d%d",&n,&m);
  62. for(int i=0;i<n;i++){
  63. for(int j=0; j<m; j++){
  64. scanf("%d", &arr[i][j]);
  65. }
  66. }
  67. int cnt_island = 0;
  68. for(int i=0; i<n;i++){
  69. for(int j=0; j<m;j++){
  70. if(!visited[i][j][0] && arr[i][j]){
  71. find_island(cnt_island, i,j);
  72. cnt_island += 1;
  73. }
  74. }
  75. }
  76.  
  77. // printf("\n");
  78. // for(int i=0; i<n;i++){
  79. // for(int j=0; j<m;j++){
  80. // printf("%d ", arr[i][j]);
  81. // }
  82. // printf("\n");
  83. // }
  84. // cnt_islend-1 edges are needed to connect all island
  85. int ans = 0, edges = 0;
  86. for(int i=0; i<cnt_island-1; i++){
  87. memset(visited, 0, sizeof(visited));
  88. queue< node > q;
  89. push_queue(q, 1);
  90.  
  91. while(!q.empty()){
  92. node cur = q.front(); q.pop();
  93. int cury = cur.cur.first, curx = cur.cur.second;
  94.  
  95. // another island check
  96. if(arr[cury][curx] > 1 && cur.cnt_bridge >= 2) {
  97. // printf("found another island#%d at (%d,%d): %d\n", arr[cury][curx], cury,curx, cur.cnt_bridge);
  98. int island_idx = arr[cury][curx];
  99. ans += cur.cnt_bridge;
  100. edges += 1;
  101. Union(island_idx);
  102. break;
  103. }
  104.  
  105. // cannot pass through another island
  106. if(arr[cury][curx] > 1){
  107. continue;
  108. }
  109.  
  110. if(cur.is_vertical == -1){
  111. visited[ cury ][ curx ][0] = visited[ cury ][ curx ][1] = 1;
  112. } else {
  113. visited[ cury ][ curx ][cur.is_vertical] = 1;
  114. }
  115.  
  116. // build bridge to search island
  117. for(int d=0; d<4;d++){
  118. int ny = cury + dy[d], nx = curx + dx[d];
  119. if(ny >= 0 && nx >=0 && nx < m && ny < n && arr[ny][nx] != 1 && !visited[ny][nx][cury!=ny]){
  120. if( cur.is_vertical == -1 ){ // all directions
  121. q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), cury != ny));
  122. } else if (cur.is_vertical == 1 && cury != ny){
  123. q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), 1));
  124. } else if (cur.is_vertical == 0 && cury == ny) { // horizontal
  125. q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), 0));
  126. }
  127. }
  128. }
  129. }
  130. }
  131. printf("%d\n", (ans == 0 || edges != cnt_island-1) ? -1 : ans);
  132. return 0;
  133. }
  134.  

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04

www.acmicpc.net/problem/1305

 

1305번: 광고

첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다. L은 백만보다 작거나 같은 자연수이다.

www.acmicpc.net

 

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

 

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

 

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

i 부분 문자열 pi[i]
0 A 0
1 AB 0
2 ABA 1
3 ABAD 0
4 ABADA 1
5 ABADAB 2
6 ABADABC 0

 

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

 

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

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

 

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

 

 

소스코드

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

  1. #include<iostream>
  2. #include<string>
  3. #include<vector>
  4. using namespace std;
  5.  
  6. vector<int> get_pi_array(string s){
  7. int n = s.size();
  8. vector<int>pi(n);
  9. pi[0] = 0;
  10. int j = 0;
  11. for(int i=1; i < n; i++){
  12. while(j>0 && s[i] != s[j]){
  13. j = pi[j-1];
  14. }
  15. if(s[i] == s[j]){
  16. pi[i] = j + 1;
  17. j += 1;
  18. } else {
  19. pi[i] = 0;
  20. }
  21. }
  22. return pi;
  23. }
  24.  
  25. int main(){
  26. int n;
  27. string s;
  28. cin >> n >> s;
  29. vector<int> pi = get_pi_array(s);
  30. cout << n - pi[n-1] << '\n';
  31. return 0;
  32. }

 

 

관련 사이트:

bowbowbow.tistory.com/6

m.blog.naver.com/kks227/220917078260

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04
BOJ 2407 조합  (0) 2020.09.04

+ Recent posts