PS) 1012, 2583, 2468, 2644번 (유기농 배추, 영역 구하기, 안전 영역, 촌수 계산)

 

1012 유기농 배추

 

//CC를 구해라
#include<stdio.h>
#include<queue>
using namespace std;
int m, n, k;
int arr[55][55];
queue<pair<int, int>> q;
int tox[4] = {0,0,1,-1};	int toy[4] = {1,-1,0,0};
void bfs(int x, int y) { //가로,세로,배추의 개수
	q.push({ x,y }); 
	pair<int, int> node;
	while (q.empty()==false) {
		node = q.front();  arr[node.first][node.second] = 0;
		for (int i = 0; i < 4; i++) {
			int newx = tox[i] + node.first;
			int newy = toy[i] + node.second;
			if (newx>0 && newx<=n && newy>0 && newy<=m && arr[newx][newy] == 1) {
				arr[newx][newy] = 0; q.push({ newx,newy });
			}
		}
		q.pop();
	}
}
int main() {
	int t; scanf("%d", &t);
	int x, y; int cc = 0;
	for (int i = 1; i <= t; i++) {
		scanf("%d%d%d", &m, &n, &k);
		for (int j = 1; j <= k; j++) {
			scanf("%d%d", &x, &y);
			arr[y+1][x+1] = 1;
		}
		for (int j = 1; j <= n; j++) {
			for (int u = 1; u <= m; u++) {
				if (arr[j][u] == 1) {
					bfs(j, u); cc++;
				}
			}
		}
		printf("%d\n", cc); 
		cc = 0;
	}
}

 

 

2583번 영역 구하기 ★

 

bfs문제이지만 bfs부분은 어렵지 않았고, 좌표를 배열로 옮기는 과정이 너무 헷갈려서 혼났다..... 푸는 와중에 너무 헷갈려서 다음에 풀까 생각했었지만 결국 풀었고 나중에 다시 한번 꼭 풀어볼꺼다.....

이렇게 복잡한 문제는 아이패드에 꼭 그려가면서 변수를 확실히 하자. 확실히 안해주면 시간 배로 걸리고 더 헷갈림. 실제로 그려보고 하나씩 정리해주면 훨 쉽고 정확하다. 크게 보면 훨씬 시간 적게 걸림... 정신건강에도 좋아요

 

//CC를 구해라
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int m, n, k;
int arr[105][105];
queue<pair<int, int>> q;
vector<int>v;
int tox[4] = {0,0,1,-1};	int toy[4] = {1,-1,0,0};

void bfs(int x, int y) { 
	int sum = 0;
	q.push({ x,y }); 
	pair<int, int> node;
	while (q.empty()==false) { //first is y / second is x
		node = q.front();  arr[node.first][node.second] = 1;
		for (int i = 0; i < 4; i++) {
			int newx = tox[i] + node.second;
			int newy = toy[i] + node.first;
			if (newx>0 && newx<=n && newy>0 && newy<=m && arr[newy][newx] == 0) {
				arr[newy][newx] = 1; q.push({ newy,newx }); 
			}
		}
		sum++;
		q.pop();
	}
	v.push_back(sum);
}
int main() {
	int sx, sy, ex, ey; int cc = 0;
	scanf("%d%d%d", &m, &n, &k);
	for (int j = 1; j <= k; j++) {
		scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
		for (int i = m-ey+1; i <= m-sy; i++) {
			for (int u = sx + 1; u <= ex; u++) {
				arr[i][u] = 1;
			}
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int u = 1; u <= n; u++) {
			if (arr[j][u] == 0) {
				bfs(j, u); cc++;
			}
		}
	}
	//printans
	printf("%d\n", cc);
	sort(v.begin(), v.end());
	int index = 0;
	while (index < v.size()) {
		printf("%d\n", v[index]);
		index++;
	}
}

 

 

2468번 안전 영역

 

그래프 탐색은 푸는 법이 다들 비슷비슷하다. 

 

//시간 괜찮?
#include<stdio.h>
#include<queue>
using namespace std;
int arr[105][105];
int hei[105][105];
queue<pair<int, int>> q;
int tox[4] = { 0,0,-1,1 };	int toy[4] = { 1,-1,0,0};

bool init_arr(int n, int h) {
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (hei[i][j] <= h) { //잠긴 영역은 0
				arr[i][j] = 0; sum++;
			}
		}
	}
	if (sum == n*n) return false;
	return true;
}
void set_arr(int n) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			arr[i][j] = 1;
		}
	}
}
void bfs(int x,int y,int h,int n) {
	q.push({ x,y }); 
	arr[x][y] = 0;
	pair<int, int> node;
	while (q.empty()==false) {
		node = q.front();
		for (int i = 0; i < 4; i++) {
			int nx = node.first + tox[i];
			int ny = node.second + toy[i];
			if (nx > 0 && nx <= n && ny > 0 && ny <= n && arr[nx][ny] == 1) {
				arr[nx][ny] = 0; q.push({ nx,ny });
			}
		}
		q.pop();
	}
}
int main() {
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &hei[i][j]);
		}
	}
	int max = 1; int sum;
	for (int i = 1; i <= 100; i++) { //높이
	sum = 0;
	set_arr(n);
	if (init_arr(n, i) == false) {
		break;
	}
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= n; k++) {
			if (arr[j][k] == 1) {
				bfs(j, k, i, n); sum++;
			}
		}
	}
	if (max < sum) max = sum;
}
	printf("%d", max);
}

생각해보니 비가 내리는 양은 범위로 주어져 있지 않다. 그러므로 비가 안 올 수도 있다.

따라서 

2

1 1

1 1

같은 입력에서 0(무조건 잠긴다)가 아닌, 1이 출력되어야 한다. 비가 안올 경우 잠기지 않으므로 영역은 한개이다.

문제에 "아무 지역도 물에 잠기지 않을 수도 있다" 라고 적혀 있다.. 비가 안 올 수도 있다라고 힌트를 줬으면 좋았을 텐데 굳이 저렇게 주는 이유 무엇

 

시간복잡도?

 

 

 

2644번 촌수계산

 

한 노드에서 다른 노드로 이동하는 방법은 하나밖에 없다. (노드의 관계는 트리이기 때문에) 따라서 그냥 탐색해주고 발견하면 반복횟수를 프린트해주면 된다.

 

• 트리는 DAG(Directed Acyclic Graphs) 방향성 있는 비순환 그래프이다.

 

#include<stdio.h>
#include<queue>
using namespace std;
queue<int>q;
int edge[105][105];
int isvisit[105];
int n;
int bfs(int x, int y) {
	if (x == y) return 0;
	q.push(x); isvisit[x] = 1;
	int prev = 1; int sum = 0; 
	int cycle = 0;
	int node;
	while (q.empty()==false) {
		while (prev > 0) {
			node = q.front();
			for (int i = 1; i <= n; i++) {
				if (edge[i][node] == 1 && isvisit[i] == 0) {
					isvisit[i] = 1; sum++; q.push(i);
				}
			}
			prev--;
			q.pop();
		}
		cycle++;
		prev = sum; sum = 0;
		if (isvisit[y] == 1) {
			return cycle;
		}
	}
	return -1;
}
int main() {
	scanf("%d", &n); //사람 수
	int a, b; scanf("%d%d", &a, &b);
	int t; scanf("%d", &t);
	int x, y;
	for (int i = 1; i <= t; i++) {
		scanf("%d%d", &x, &y);
		edge[x][y] = 1; edge[y][x] = 1;
	}
	int ans = bfs(a, b);
	printf("%d", ans);
}