안녕하세요! 점심으로 피자를 먹은 GCOCO입니다!

---

잡설 한 COOKIE🍪

맛있는 피자를 점심으로 먹었음에도 불구하고 방금까지도 우울했습니다.
이유인 즉슨 이 문제를 푸는데 계속하여 segmentation fault가 발생하여 스트레스를 받았기 때문이죠!
논리는 맞는것 같은데 어째서 segmentation fault계속 발생하지 뭐지?! 하고 디버깅을 돌려보다가
아차차,,,,,,,실수한 곳을 찾았습니다.
인덱스의 문제가 있었더군요.

문제와 함께 코드를 보시죠!

---

문제는 다음과 같습니다.

1. 길이가 n인 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
2. 이 지도를 가지고 연결된 집의 수와 단지를 세려고 한다.
3. 연결된 집이란 상 하 좌 우로 연결된 것을 말한다. 대각선상의 경우는 연결된 것이 아니다.
4. 지도를 입력하고, 단지의 수의 수와 각 단지에 속하는 집의 수를 오름차순으로 출력하시오.

입력은 다음과 같이 주어집니다!

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

해당하는 출력은 다음과 같습니다.

3
7
8
9

---

풀이

제목에도 써 있다 싶이 아래의 코드는 DFS를 사용하여 푼 풀이입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//좌 우 상 하 탐색
int dx[4] = { 0,0,-1,1};
int dy[4] = { -1,1,0,0};

void dfs(int row, int col, vector<vector<int>>& v,
    vector<vector<bool>>& visited, int& size, int& count) {
    //범위를 벗어나거나 방문한 곳이면 종료
    if (col<0 || col>=size || row<0 || row>=size || visited[row][col])
        return;
    //방문 표시
    visited[row][col] = true;
	//지도에서 값이 0이면 종료
    if (v[row][col] == 0)
        return;
    //지도에서 값이 1이면 다시 사방 탐색
    else {
        count++;
        for (int i = 0; i < 4; i++) {
            dfs(row + dx[i], col + dy[i], v, visited, size, count);
        }
    }
}


int main(void) {
    int n;
    cin >> n;//n입력
    vector<vector<int>> v(n, vector<int>(n, 0));//지도 만들기
    vector<vector<bool>> visited(n, vector<bool>(n, false));//방문표시
    vector<int> answer;//답을 담을 vector answer

	//지도 입력
    for (int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        for (int j = 0; j < n; j++) {
            v[i][j] = tmp[j] - '0';
        }
    }
    
    //지도를 돌며 dfs 실행
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int count = 0;
            dfs(i, j, v, visited, n, count);
            if (count)
                answer.emplace_back(count);
        }
    }
    //answer 정렬
    sort(answer.begin(),answer.end());
    cout<<answer.size()<<endl;
    for (auto i : answer)
        cout << i << endl;

    return 0;
}

STEP은 다음과 같습니다.

1. 지도를 입력받고, 방문을 표시할 또 하나의 지도를 만든다.
2. 지도를 돌며 DFS를 실행한다.
3. DFS내부에서 범위 밖이나 방문한 곳이면 종료
4. 방문한 곳이 아니고 범위 내의 값이라면 해당 지점을 방문 표시
5. 또한 지도에서 0으로 표기된 곳이라면 종료
6. 지도에서 1로 표기된 곳이라면 사방(상하좌우) 탐색.
7. count 변수를 이용하여, 연결된 집이 있는 경우라면 answer에 담아주기.
8. answer을 오름차순으로 sort, size 출력, 원소 출력

이 정도가 되겠네요~

제가 곤란함을 겪었던 부분은 바로.........

 if (col<0 || col>=size || row<0 || row>=size || visited[row][col])
        return;

이 부분이었습니다!

더 자세하게 어느 부분이였냐면, col>=size , row>=size 이 부분이었죠.
해당 부분을 col>size , row>size로 적었지 뭡니까 하하하하하하하ㅏ하
그러니 당연히 segmentation fault가 발생할 수 밖에 없었습니다!
지도 상에 size를 인덱스로 갖는곳은 존재하지 않으니까요!

앞으로 이런 디테일에 주의해야겠습니다. 😁😁

---

작은 도움이 되었길 바라며, 포스팅 마치겠습니다!