1012 : 유기농 배추 - DFS, BFS, 인접리스트, 연결 컴포넌트

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

1012번: 유기농 배추

문제요약

connected component 개수 찾기

 

난이도

Silver 2

---

풀이 포인트

 

• 깊이우선탐색(DFS)
  
  • 리프 노드에 닿을 때까지 재귀 실행하는 특성을 이용하여, 연결 요소(coonnected component)의 개수를 구할 수 있음
  • 2차원 좌표 탐색에 DFS 사용시, 매개변수만 두개로 늘려주어 2차원 배열 요소 접근하면 됌.
• fill을 이용한 초기화
  • fill(array_name, array_name + array_size, value)
  • fill(from, to, value)

// 2차원 배열을 0으로 채우기

//01. fill(arrName, arrName + arrSize, value)
   
const int rows = 3;
const int cols = 4;
int arr[rows][cols];

for (int i = 0; i < rows; ++i) {
    fill(arr[i], arr[i] + cols, 0);
}

//02. fill(from, to, value)

fill(&arr[0][0], &arr[0][0] + 3*4, 0);

---

REVIEW

1차 시도

우선, 오늘 인접행렬과 인접리스트 개념을 공부한지라 인접리스트를 이용해서 풀어보려고 했다.

 

cnt를 vertex 수로 초기화해두고, 

해당 vertex와 이어진 vertex의 idx를 저장하는 인접리스트를 생성한다.

go 함수로 해당 vertex에 방문한 적이 없다면 이동, 방문한 적이 있다면 패스.

그리고 go 재귀함수가 끝날 때까지 즉, 한 덩어리 안을 이동할 때 cnt--;를 해줬다.

 

여차저차 테스트 케이스까지는 통과했는데 제출했더니 오답이었다.

전역변수로 변수를 선언하는 습관을 들이다보니, 여러가지 테스트 케이스가 주어졌을 때,

그때그때 초기화하는 것을 놓쳤나 보다.

 

디버깅 수차례에 테스트 케이스는 통과한 나름의 노력이 가상한 코드를 짰기에,

제쳐두고 모범답안 봤더니 DFS로 풀면 용이한 문제였나보다.

 

아직 배운  범위 내에서 풀이를 고려하다 보니 자꾸 bfs,dfs 풀이는 제외하고 생각하게 되는데,

우선 개념 공부 전에 코드로 먼저 아이디어를 이해는 해둬야겠다.

---

CODE

//connected component의 갯수를 찾는 문제
//dfs,bfs 
//배열 꼭 초기화해주는 것이 중요!

#include <bits/stdc++.h>
using namespace std;

int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};

int m,n,k,y,x,ret,ny,nx,t;

int a[51][51];
bool visited[51][51];

void dfs(int y, int x){
    visited[y][x] = 1;

    for(int i = 0; i < 4; i++){
        ny = y + dy[i];
        nx = x + dx[i];

        if(ny < 0 || ny >=n|| nx >= m) continue;
        if(a[ny][nx]==1 && !visited[ny][nx]){
            dfs(ny,nx);
        }
    }
    return;
}

int main(){
    cin.tie(NULL); cout.tie(NULL);

    cin >> t;

    while(t--){
        fill(&a[0][0], &a[0][0] + 51 *51 , 0);
        fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);
        ret = 0;
        cin >> m >> n >> k;

        for(int i = 0; i < n; i++){
            for(int j =0; j<m;j++){
                if(a[i][j]== 1 && !visited[i][j]){
                    dfs(i,j);
                    ret++;
                }
            }
        }

        cout << ret << "\n";
    }

}