백준 2667 //단지번호붙이기

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

 

사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다.
지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성

 

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
vector<vector<int>> maze;
vector<vector<bool>> visited;
vector<int> cluster_sizes;

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

int DFS(int x, int y)
{
	visited[x][ y] = true;
	int size = 1;

	for (int i = 0; i < 4; i++)//상하좌우 검색하기
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		//지도범위안에서, 방문한적 없고, 값이 1일때
		if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && maze[nx][ny] == 1)
		{
			size += DFS(nx, ny);//DFS(1,1)
		}
	}

	return size;
}

int main()

{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	
	cin >> n;
	maze.resize(n, vector<int>(n));
	visited.resize(n, vector<bool>(n, false));
	
	for (int i = 0; i < n; i++)
	{
		string row;
		cin >> row;
		for (int j = 0; j < n; j++)
		{
			//0110100의 경우
            //maze[0][0] = row[0] - '0' = 48-48= 0(int) 
            //maze[0][1] = row[1] - '0' = 49-48= 1(int).......
            
            maze[i][j] = row[j] - '0';
			//cout << maze[i][j];
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			//maze[0][1] -> DFS(0,1)
            if (maze[i][j] == 1 && !visited[i][j])
			{
				cluster_sizes.push_back(DFS(i, j));
			}
		}
	}

	sort(cluster_sizes.begin(), cluster_sizes.end());

	cout << cluster_sizes.size() << "\n";
	for (int size : cluster_sizes)
	{
		cout << size << "\n";
	}


	return 0;
}

 

 

처음에 아스키코드값 처리를 안해줬더니,, 저장되어있던 숫자들 48, 49등이 출력되어서 -'0'처리를 해줘야 했다.

 

입력을 문자열로 받은 뒤 각 문자를 숫자로 변환하는 방식(row[j] - '0')을 사용하는 이유??????

처음에 테스트 예제 복붙했는데 뭔가 이상한 답들이 나왔다...가만 보니 예제에 띄어쓰기가 없다

이런 경우는 string으로 각각 입력을 받아서 vector에 숫자로 입력을 다시 넣어주어야 한다.

---

테스트입력에 띄어쓰기가 없다~~~ 와~~~ 엄청 헷갈렸다!!

2차원 배열의 입력이 숫자 간에 공백이 없는 문자열 형태로 주어지는 경우:

0110100
0110101
1110101

 

숫자를 공백으로 구분하여 입력받는 경우:

공백 처리 불필요

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cin >> maze[i][j];
    }
}

 

문자(char)와 아스키 코드

• 컴퓨터는 문자를 내부적으로 아스키 코드라는 숫자로 저장합니다.
  • 예를 들어, 문자 '0'의 아스키 코드 값은 48, '1'의 아스키 코드 값은 49입니다.
  • 따라서 '0' ~ '9'까지의 문자는 각각 48 ~ 57의 아스키 코드 값을 가집니다.

---

문자에서 숫자로 변환

• row[j]는 문자열(string)의 j번째 문자입니다. 이 문자가 '0', '1' 등의 문자 형태로 저장되어 있습니다.
• 문자 '0'에서 문자 '0'의 아스키 코드 값(48)을 빼면, 다음과 같은 결과를 얻습니다:
  • '0' - '0' → 48 - 48 → 0
  • '1' - '0' → 49 - 48 → 1
  • '2' - '0' → 50 - 48 → 2

 (0, 1)에서 시작

1. 탐색 순서:
   • DFS는 상하좌우를 탐색하며, 연결된 노드가 있으면 해당 노드로 이동.
   • **(0, 1)**에서 탐색 가능한 방향

 

• 위쪽: (x - 1, y) = (-1, 1) → 범위를 벗어남, 탐색하지 않음.
• 아래쪽: (x + 1, y) = (1, 1) → maze[1][1] = 1, 탐색 가능.
• 왼쪽: (x, y - 1) = (0, 0) → maze[0][0] = 0, 탐색하지 않음.
• 오른쪽: (x, y + 1) = (0, 2) → maze[0][2] = 1, 탐색 가능.

첫 번째 탐색:

• DFS는 **(0, 2)**로 이동합니다. 다음 단계:
  • (0, 2)에서도 상하좌우 탐색을 반복하며, 연결된 노드만 탐색.