[Softeer] 장애물 인식 프로그램 (C++)

입력

• N: 크기
• N x N 블록

 

출력

• 블록 수
• 블록 별 장애물 수 (오름차순)

 

풀이과정

https://koharinn.tistory.com/441 문제와 매우 유사. 이전에 많이 풀이본 유형의 풀이라서 바로 생각해낼 수 있었다.
입력 처리: 숫자가 붙어있어서 일단 string으로 받은 후, string의 각 원소는 char이므로 char-’0’으로 숫자로 변환 후 이 값을 배열에 저장
한 지점을 방문했을 때, 그 지점에서 갈 수 있는 방향은 상(x,y-1), 하(x,y+1), 좌(x-1,y), 우(x+1,y)이다.
이떄 상,하,좌,우가 유효한 지점인지(0보다 작지 않은지, 그리고 n보다 크거나 같지 않은지) 확인하고 방문해야 한다. 이렇게 각 지점에서 상,하,좌,우의 유효한 지점을 방문하면서 DFS를 호출해간다.
만약 처음 호출한 DFS까지 리턴한다면, 한번의 방문이 완료된 것이다.
그럼 cnt를 result 벡터에 저장한 후 다음 block에서의 장애물을 카운트하기 위해 cnt를 0으로 초기화한다.
이후 이어서 i와 j를 반복문으로 돌리면서 visited가 아니면서 block에 값이 있는 그래프 내 노드를 방문해가고 앞선 과정을 반복한다.

 

코드

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

using namespace std;

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

void DFS(int x, int y, vector<int> *block, vector<int> *visited, int N, int *cnt){
	visited[x][y] = 1;
	(*cnt)++;
	for(int i=0; i<4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
		else{
			if(visited[nx][ny] == 0 && block[nx][ny] != 0) DFS(nx, ny, block, visited, N, cnt);
		}
 	}
}

int main(int argc, char** argv)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;
	vector<int> block[N];
	vector<int> visited[N];
	vector<int> result;
	int cnt=0;

	for(int i=0; i<N; i++){
		string s; cin >> s; // get line in string
		for(int j=0; j<N; j++){
			block[i].push_back(s[j]-'0'); // convert char per line to int & save
			visited[i].push_back(0);
		}
	}

	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(!visited[i][j] && block[i][j] != 0) {
				DFS(i,j,block, visited, N, &cnt);
				result.push_back(cnt);
				cnt=0;
			}
		}
	}
	// sort in ascending
	sort(result.begin(), result.end());
	// print number of blocks
	cout << result.size() << endl;
	for(int num : result) cout << num << endl;
	return 0;