Feel Coding

www.acmicpc.net/problem/16234

DFS로 풀었다. BFS나 DFS나 아무거나로 풀어도 된다.

DFS는 연합을 만드는 과정이다. 상하좌우 탐색하면서 l개 이상 r개 이하로 차이가 나면 스택에 넣어주었다.

탐색을 하면서 그 연합에 속하는 나라의 행과 열을 pair로 묶어서 countries라는 벡터에 넣어줬다.

또한 그 연합에 속하는 나라의 인구 수를 sum에 누적해서 더해줬다.

그렇게 연합을 만든 후에 sum을 countries.size()로 나눠서 인구 수를 갱신해주었다.

countries.size()가 1이면 인구 이동이 일어나지 않는 것이고 1보다 크면 인구 이동이 일어났다는 것이므로 flag = true로 해준다.

flag가 false라는 것은 더 이상 인구 이동이 일어나지 않는다는 것이므로 while문을 빠져나온다.

가장 바깥쪽 while문은 인구이동이 몇 번 일어났는지를 세어준다.

#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, l, r;
	cin >> n >> l >> r;
	vector<vector<int>> v(n, vector<int>(n));
	vector<vector<bool>> visited(n, vector<bool>(n, false));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	int moveCount = 0;
	while (true) {
		visited = vector<vector<bool>>(n, vector<bool>(n, false));
		bool flag = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					stack<pair<int, int>> stack;
					stack.push(make_pair(i, j));
					int sum = 0;
					vector<pair<int, int>> countries;
					while (!stack.empty()) {
						pair<int, int> cur = stack.top();
						stack.pop();
						int row = cur.first;
						int col = cur.second;
						if (!visited[row][col]) {
							visited[row][col] = true;
							sum += v[row][col];
							countries.push_back(cur);
							if (row + 1 < n && abs(v[row][col] - v[row + 1][col]) >= l && abs(v[row][col] - v[row + 1][col]) <= r) {
								stack.push(make_pair(row + 1, col));
							}
							if (row - 1 >= 0 && abs(v[row][col] - v[row - 1][col]) >= l && abs(v[row][col] - v[row - 1][col]) <= r) {
								stack.push(make_pair(row - 1, col));
							}
							if (col + 1 < n && abs(v[row][col] - v[row][col + 1]) >= l && abs(v[row][col] - v[row][col + 1]) <= r) {
								stack.push(make_pair(row, col + 1));
							}
							if (col - 1 >= 0 && abs(v[row][col] - v[row][col - 1]) >= l && abs(v[row][col] - v[row][col - 1]) <= r) {
								stack.push(make_pair(row, col - 1));
							}
						}
					}
					if (countries.size() > 1) {
						flag = true;
						for (int k = 0; k < countries.size(); k++) {
							int row = countries[k].first;
							int col = countries[k].second;
							v[row][col] = sum / countries.size();
						}
					}
				}
			}
		}
		if (!flag)
			break;
		moveCount++;
	}
	cout << moveCount;
	return 0;
}

C++에서 배열을 선언하고 초기화를 해주지 않으면 배열은 쓰레기 값으로 채워져있다.

아래의 코드를 실행해보면

#include <iostream>
using namespace std;

int main() {
	int arr[5];
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

이렇게 쓰레기 값으로 채워져있는 것을 볼 수 있다.

따라서 배열을 선언하면 초기화를 꼭 해주는 것이 좋다.

배열 arr의 원소를 모두 0으로 초기화하고 싶다면

int arr[5] = {};

이렇게 해주면 된다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = {};
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

배열 arr의 원소 5개가 모두 0으로 초기화된 것을 볼 수 있다.

만약에 배열의 0번째 원소만 10으로 초기화하고 나머지는 다 0으로 초기화하고 싶다면?

int arr[5] = { 10 };

또는

int arr[5] = { 10, };

이렇게 해주면 된다.

여기에서 주의할 점은 위 코드는 모든 원소를 10으로 초기화하는 것이 아니라 첫 번째 원소만 10으로 초기화하는 것이라는 것이다. 이 부분을 잘못 알고 있기 쉬우므로 꼭 기억하자.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 10 };
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

첫 번째 원소만 10으로 초기화된 것을 볼 수 있다.

첫 번째 원소를 10으로, 두 번째 원소를 3으로, 나머지는 0으로 초기화하고 싶다면

int arr[5] = { 10, 3 }

이렇게 하면 된다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 10, 3 };
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

첫 번째 원소가 10, 두 번째 원소가 3으로, 나머지는 0으로 초기화 된 것을 볼 수 있다.

그런데 만약 모든 원소를 0이 아닌 특정 값으로 초기화하고 싶다면?

배열의 크기가 5 정도로 작다면

int arr[5] = { 10, 10, 10, 10, 10 }

이렇게 직접 초기화 해줄 수 있지만 배열의 크기가 1000, 10000, 100000 등 큰 수라면 이렇게 직접 초기화 하기에는 무리가 있다.

그럴 때 일반적으로 이렇게 반복문으로 초기화를 시킨다.

#include <iostream>
using namespace std;

int main() {
	int arr[5];
	for (int i = 0; i < 5; i++) {
		arr[i] = 10;
	}
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

이렇게 10으로 초기화된 것을 볼 수 있다.

하지만 함수를 이용해서 더 편리하게 초기화할 수 있는 방법이 있다.

바로 <algorithm> 헤더에 있는 fill 함수이다.

http://www.cplusplus.com/reference/algorithm/fill/

fill 함수를 사용하려면 일단 <algorithm> 헤더를 포함해줘야 한다.

사용 방법은

fill(초기화 시키고 싶은 부분의 시작 주소, 초기화시키고 싶은 부분의 끝 주소, 초기화할 값);

이렇게 사용하면 된다.

배열이라면

fill(arr, arr + 5, 10);

이렇게 하면 되고

벡터라면

fill(v.begin(), v.end(), 10);

이렇게 해주면 된다.

아래 코드를 실행하면

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

int main() {
	int arr[5];
	fill(arr, arr + 5, 10);
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

이렇게 모든 원소가 10으로 초기화되어 있는 것을 볼 수 있다.

즉

for(int i = 0; i < 5; i++) {
	arr[i] = 10;
}

이 for문을 사용한 코드와

fill(arr, arr + 5, 10);

이 한 줄은 같은 역할을 한다.

fill(arr, arr + 2, 10);
fill(arr + 2, arr + 5, 20);

이렇게 부분 부분씩 초기화시켜줄 수도 있다.

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

int main() {
	int arr[5];
	fill(arr, arr + 2, 10);
	fill(arr + 2, arr + 5, 20);
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

전체 코드이다.

벡터도 마찬가지이다.

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

int main() {
	vector<int> v(5);
	fill(v.begin(), v.end(), 10);
	for (int i = 0; i < 5; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	return 0;
}

이 코드를 실행하면

이렇게 10으로 초기화된다.

하지만 벡터는 굳이 fill 함수를 안 쓰고

vector<int> v(5, 10);

이렇게 선언과 동시에 10으로 초기화하는 것이 더 편할 것이다.

(벡터 초기화 및 사용법↓)

https://breakcoding.tistory.com/139

단계별로 풀어보기 DFS와 BFS의 4단계 문제이다

3단계 문제인 2667번과 입출력 방법 말고는 거의 같아서 쉽게 풀 수 있었다.

오히려 배추 개수를 출력할 필요가 없어서 더 쉬웠다.

def dfs(row, col):
    if li[row][col] == 0 or visited[row][col]:
        return 0
    stack = []
    stack.append((row, col))
    while stack:
        cur = stack.pop()
        visited[cur[0]][cur[1]] = True
        if li[cur[0] - 1][cur[1]] == 1 and not visited[cur[0] - 1][cur[1]]:
            if 1 <= cur[0] - 1 <= n and 1 <= cur[1] <= m:
                stack.append((cur[0] - 1, cur[1]))
        if li[cur[0] + 1][cur[1]] == 1 and not visited[cur[0] + 1][cur[1]]:
            if 1 <= cur[0] + 1 <= n and 1 <= cur[1] <= m:
                stack.append((cur[0] + 1, cur[1]))
        if li[cur[0]][cur[1] - 1] == 1 and not visited[cur[0]][cur[1] - 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] - 1 <= m:
                stack.append((cur[0], cur[1] - 1))
        if li[cur[0]][cur[1] + 1] == 1 and not visited[cur[0]][cur[1] + 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] + 1 <= m:
                stack.append((cur[0], cur[1] + 1))
    return 1

test_case = int(input())
from sys import stdin

for i in range(test_case):
    m, n, k = list(map(int, stdin.readline().split()))
    li = [[0] * m for j in range(n)]
    for j in range(0, k):
        rawInput = list(map(int, stdin.readline().split()))
        li[rawInput[1]][rawInput[0]] = 1
    li.insert(0, [0] * (m + 2))
    li.append([0] * (m + 2))
    for j in range(1, n + 1):
        li[j].insert(0, 0)
    for j in range(1, n + 1):
        li[j].append(0)
    visited = [[False for j in range(m + 2)] for i in range(n + 2)]
    count = 0
    for j in range(1, n + 1):
        for l in range(1, m + 1):
            count += dfs(j, l)
    print(count)