[dfs] [연결 요소] 단지번호붙이기 2667

단지번호붙이기 2667

 

풀이코드 ( 입출력 틀림 )

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 2667 단지번호붙이기

int board[25][25];
bool isVisit[25][25];
int n;

int dfs(int y, int x){
	isVisit[y][x] = true;
	
	int ret = 0;
	
	vector<pair<int, int>> np;
	
	np.push_back(pair<int, int>(y + 1, x));
	np.push_back(pair<int, int>(y - 1, x));
	np.push_back(pair<int, int>(y, x - 1));
	np.push_back(pair<int, int>(y, x + 1));
	
	for(int i = 0; i < 4; i++){
	
		int ny = np[i].first;
		int nx = np[i].second;
		
		if (0 <= nx && nx < n && 0 <= ny && ny < n) {
        if (a[nx][ny] == 1 && d[nx][ny] == 0) {
			ret += dfs(ny, nx) + 1;
		}
	}
		
	
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 

	cin >> n;
	cin.ignore();
	
	fill(&isVisit[0][0], &isVisit[24][25], false);
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> board[i][j];
		}
		cin.ignore();
	}
	vector<int> ret(1, 0);
	for(int y = 0; y < n; y++){
		for(int x = 0; x < n; x++){
			if(isVisit[y][x]) continue;
			if(board[y][x] != 1) continue;
			
			ret[0] += 1;
			ret.push_back(dfs(y,x));
		}
	}
	sort(ret.begin() + 1, ret.end());
	for(int a : ret) cout << a << '\n';
}

풀이코드 (DFS)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 2667 단지번호붙이기

int board[25][25];
bool isVisit[25][25];
int n;

int dfs(int y, int x){
	isVisit[y][x] = true;
	
	int ret = 0;
	
	vector<pair<int, int>> np;
	
	np.push_back(pair<int, int>(y + 1, x));
	np.push_back(pair<int, int>(y - 1, x));
	np.push_back(pair<int, int>(y, x - 1));
	np.push_back(pair<int, int>(y, x + 1));
	
	for(int i = 0; i < 4; i++){
	
		int ny = np[i].first;
		int nx = np[i].second;
		
		if (0 <= nx && nx < n && 0 <= ny && ny < n) {
        	if (board[ny][nx] == 1 && isVisit[ny][nx] == 0) {
			ret += dfs(ny, nx) + 1;
			}
		}
	}
		
	
	return ret;
}

int main(){

	scanf("%d", &n);

	fill(&isVisit[0][0], &isVisit[24][25], false);
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			scanf("%1d", &board[i][j]);
		}
	}
	vector<int> ret(1, 0);
	for(int y = 0; y < n; y++){
		for(int x = 0; x < n; x++){
			if(isVisit[y][x]) continue;
			if(board[y][x] != 1) continue;
			
			ret[0] += 1;
			ret.push_back(1 + dfs(y,x));
		}
	}
	sort(ret.begin() + 1, ret.end());
	for(int a : ret) cout << a << '\n';
}

해설

---

적용한 레시피 / 방법론 + 접근법

1. 비슷한 문제를 풀어본 적이 있던가?

  형태가 비슷하거나 관련 문제를 풀어보았다면, 같은 방법을 사용할 거라고 예측할 수 있다. 그러나, 완전히 같은 문제를 만날 가능성은 없기에 문제의 목적을 보고 적절한 접근 방법을 선택할  수 있어야 한다. 이를 위해, 해당 문제가 어떤 문제인지 분류하는 힘을 익히고 우리가 익히는 알고리즘들이 어느 경우에 사용될 수 있는지 체계적으로 알아가야 한다.

연결 요소의 개수

 

풀이

1. 탐색을 어떻게 할 것인가?

- dfs bfs 모두 사용가능할 듯 하다.

2. 인접 리스트?

- 인접 리스트를 구현할 필요가 없다. 무조건 4개 이하의 인접 집을 가지기 때문에 4개에 대해서 조건만 충족하면 dfs 를 실행하면 된다.

3. 조건

3-1. 범위를 벗어나지 않았는가

3-2. 해당 좌표에 집이 있는가 (1인가)

3-3. 방문하지 않았었는가

를 만족하면 다음 좌표에 대해서 dfs 를 실행해준다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 매우 멍청한 입출력 실수가 있었다.

7 0110100 0110101 1110101 0000111 0100000 0111110 0111000

입력이 이렇게 들어오므로, 맨 위의 코드와 같이 cin 으로 한 숫자를 받으려고 한 것은 큰 실수였다.

cin 으로 0,0 의 수를 받는 것이 아니라, cin 은 띄어쓰기 단위로 받기 때문에 cin 한번에 0110100 이 입력으로 들어온다.

scanf 를 사용하거나 string 으로 받았어야만 했다.

2. 오름차순으로 정렬하기

문제의 조건에 나와있다. 출력 조건을 잘 읽자.

입출력을 잘못해서 모두 틀렸다.. 더 생각해보고 내자