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 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04

+ Recent posts