[C++, 코딩테스트] Softeer : 장애물 인식 프로그램 with DFS

 

이 문제는 딱봐도 DFS느낌이 바로 왔다. 맵에서 1을 만나는 경우 DFS를 이용해서 개수를 찾으면 될 것 같은 느낌이 왔다.

이 아이디어만 있으면 구현부분에서 잘하면 쉽게 풀 수 있는 문제이다.

// 딱봐도 DFS
#include<iostream>
#include<vector>
#include<sstream>
#include<algorithm>

using namespace std;
vector<vector<int>> arr;
vector<int> collect;
vector<int> dx = {1,0,-1,0};
vector<int> dy = {0,1,0,-1};
int howMany = 0;
int N;

vector<int> split(string &str){
    vector<int> line;
    for (char c : str){
        line.push_back(stoi(string(1, c)));
    }
    return line;
}

void dfs(int x, int y, int &count){
    arr[y][x] = 2; // 이미 들어온 곳을 2로 표현
    count++;
    for (int i = 0; i < 4; i++){
        int X = x + dx[i];
        int Y = y + dy[i];
        if (X < 0 || X >= N || Y < 0 || Y >= N) // range 체크
            continue;
        if (arr[Y][X] != 1) // 이미 카운트한 곳인지 체크
            continue;
        dfs(X, Y, count);
    }
}

int main(int argc, char** argv)
{
    cin >> N;
    for (int i = 0; i < N; i++){
        string line;
        cin >> line; 
        arr.push_back(split(line));
    }
    for (int y = 0; y < N; y++){
        for (int x = 0; x < N; x++){
            if (arr[y][x] == 1){
                int count = 0;
                howMany++; // 총 블록 개수 + 1
                dfs(x, y, count);
                collect.push_back(count); // 블록 개수 추가
            }
        }
    }
    cout << howMany << endl;
    sort(collect.begin(), collect.end()); // 정렬
    for (int i = 0; i < collect.size(); i++){
        cout << collect[i] << endl;
    }
    return 0;
}

 

 

여기서 짚고 넘어가야할 부분은 split를 구현하는 방법이다. 나같은 경우에는 for (char c : str) 을 이용해서 char 하나씩 분리해서 했지만

 

많은 사람들은 읽을 때부터

for (int i = 0; i < N; i++)
{
	for (int j = N - 1; j >= 0; j--)
	{
		scanf("%01d", &map[i][j]);
	}
}

 

이런식으로 scanf를 사용해서 한글자씩만 읽는 코드를 사용했다. 나같은 경우에는 c++니까 최대한 c코드를 사용하지말자라는 42스러운 고집이 아직 남아있어서 최대한 c 함수를 사용안해서 코드를 작성했다.