[풀이]백준 풀이(XIV/16988 등)

문제풀이

[Re]Baaaaaaaaaduk2 - Easy(16988)

일반 바둑과 다르게 돌을 2개씩 둔다.
일반 바둑과 동일하게 자신의 돌로 상대방의 그룹을 빈틈없이 에워싸면 갇힌 돌을 죽일 수 있다. (그룹 내에 빈칸과 인접해 있는 돌이 하나도 없다.)
모든 비어있는 칸에 돌을 둘 수 있다.(돌을 두어서 죽어도 상관 없음)
일단 그룹화를 시키고나서 시작인 것 같다.

예외1. 둘러쌓였지만 빈 칸이 포함된 경우.. 예외2. 예외1의 상황에서 빈 칸에 돌을 채우면 내가 상대방을 죽일 수도 있다…

결론적으로 현재 판이 주어질 때 바둑돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 구하자.

ㅎㅎ진짜 쉽넹…

라고 말한 나는 미친사람이었다.

회고

삽질1. next_permutation… 그냥 2중포문으로 받으면 된다.
삽질2. kCoor로 queue를 만든 것.
삽질3. cin을 잘못 받은 것
삽질4. calc함수를 생각하지 못했다…

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

int n, m, zCnt=0, kCnt =0, Answer=0;

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

int map[21][21];
int mapTemp[21][21];
int visited[21][21];
vector<pair<int,int>> zCoor;
queue<pair<int,int>> kCoor;
vector<pair<int,int>> kCoorTemp;


bool isInside(int a, int b){
	if(a>=0 && b>=0 && a<n && b<m) return true;
	else return false;
}

void initVisited(){
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			visited[i][j] = false;
		}
	}
}

void loadMap(){
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			map[i][j] = mapTemp[i][j];
		}
	}
}

int calc(pair<int,int> m1, pair<int,int> m2){
	//m1, m2를 1로 변경하고 돌리는 bfs
	int ret = 0;

	map[m1.first][m1.second]=1;
	map[m2.first][m2.second]=1;
	initVisited();

	//모든 점 중 필요한 점에서 bfs 다돌린다.
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			//방문했거나 상대방 돌이면 다음꺼 확인
			if(visited[i][j] or map[i][j] != 2) continue;
			bool isdead = true; // 연결된 돌 중에 빈 칸과 닿아있는게 하나라도 있다면 이 변수를 false로 만들 것이다.

			//bfs
			queue<pair<int, int> > q;
			q.push(make_pair(i,j));
			visited[i][j] = true;
			int area = 0;

			while(!q.empty()){
				area++;
				pair<int, int> cur = q.front(); q.pop();

				for(int i=0; i<4; i++){
					int nx = cur.first + dx[i];
					int ny = cur.second + dy[i];
					//범위를 벗어나지 않아야한다.
					if(!isInside(nx,ny)) continue;
					//빈 칸이 있으면 안죽어
					if(map[nx][ny] == 0) isdead = false;
					//방문했거나 상대방 돌이 아니면 pass
					if(visited[nx][ny] or map[nx][ny] != 2) continue;
					q.push(make_pair(nx,ny));
					visited[nx][ny] = true;
				}
			}
			if(isdead) ret += area;
	  }
	}
	loadMap();
	return ret;
}

int main(){
	cin >> n >> m;

	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> map[i][j];
			mapTemp[i][j] = map[i][j];
		}
	}
	zCoor.clear();

	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(map[i][j]==0) {
				pair<int,int> tmp = make_pair(i,j);
				zCoor.push_back(tmp);
				zCnt++;
			}
		}
	}
	//입력완료
	//뻘짓을 했네
	for(int i=0; i<zCnt; i++){
		for(int j=i; j<zCnt; j++){
			if(i!=j){
				//1. 맵 변경 완료

				pair<int,int> m1 = make_pair(zCoor[i].first, zCoor[i].second);
				pair<int,int> m2 = make_pair(zCoor[j].first, zCoor[j].second);

				//2 맵 변경 후 bfs시작
				Answer = max(Answer,calc(m1,m2));
			}
		}
	}

	cout << Answer;
}

[RE]Count Circle Groups(10216)

2차원평면위 N곳에 적군의 진영이 있다.
진영마다 통신탑이 하나씩 있다.
i번째 적군의 통신탑은 설치위치로부터 Ri 이내거리에 포함되는 모든지역을 자신의 통신영역 Ai로 가지게 된다.
통신영역 Ai와 Aj에서 겹치는 부분이 있다면 진영 i와 j는 직접 통신이 가능하다.
꼭 직접 통신이 되지않더라도 몇 다리 건너서라도 통신이 가능하면 i와 j는 통신이 가능한 것으로 본다.
서로 통신이 가능한 그룹의 개수를 출력하자.
거리니까 원형의 거리를 출력해야하네..

틀린 답

아래 코드도 예쁘게 나오긴한다.. 반례를 못 찾아서 PASS..

tip ;

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

int t, n, m, Answer=0;
int rMax = 0, xMax= 0, yMax = 0, group;

int map[5000][5000];
bool visited[5000][5000];
int dx[] = {0, 0, 1, -1};
int dy[] = {1,-1, 0,  0};

//tuple<x,y,r>
vector<tuple<int,int,int>> coor;
queue<pair<int,int>> q;

bool isInside(int a, int b){
	if(a>=0 && b>=0 && a<=5000 && b<=5000) return true;
	else return false;
}
void initMap(){
	for(int i=0; i<5000; i++){
		for(int j=0; j<5000; j++){
			map[i][j] = 0;
			visited[i][j] = false;
		}
	}
}
bool isCommunicated(int cx, int cy, int nx, int ny, int r){
	int x = abs(nx-cx);
	int y = abs(ny-cy);
	if((r*r) >= (x*x)+(y*y)) {
		return true;
	}

	else {
		return false;
	}
}

void makeMap(tuple<int,int,int>enemy){
	int x, y, r;
	tie(x,y,r) = enemy;
	//최대 거리가 r이니까 가로든 세로든 r보다 더갈필요는 없음
	//모든 점에 대해서 적기지에서 r보다 가까운 곳은 1로 변경!
	for(int nx=0; nx<=x+r; nx++){
		for(int ny=0; ny<=y+r; ny++){
			if(isCommunicated(x,y,nx,ny,r)) map[nx][ny]=1;
		}
	}
}
void printMap(){
	for(int i=0; i<=xMax+rMax; i++){
		for(int j=0; j<=yMax+rMax; j++){
			cout << map[i][j] << " ";
		}
	cout << endl;
	}
}
void bfs(int sx, int sy, int group){
	queue<pair<int,int>> nq;
	nq.push(make_pair(sx,sy));
	visited[sx][sy] = true;
	while(!nq.empty()){
		int cx, cy;
		pair<int,int> tmp = nq.front();
		nq.pop();
		tie(cx,cy) = tmp;
		map[cx][cy] = group;

		for(int i=0; i<4; i++){
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			//범위 밖이면 빠이 (0~5000)
			if(!isInside(nx,ny)) continue;
			//방문했으면 빠이
			if(visited[nx][ny]) continue;
			if(map[nx][ny]==1){
				nq.push(make_pair(nx,ny));
				visited[nx][ny] = true;
				map[nx][ny] = group;
			}
		}
	}
}

int main(){
	cin >> t;
	bool zCheck = false;
	for(int i=0; i<t; i++){
		cin >> n;
		initMap();
		group = 1;
		for(int i=0; i<n; i++){
			int x, y, z;
			cin >> x >> y >> z;
			tuple<int,int,int> tmp(x,y,z);
			coor.push_back(tmp);
			q.push(make_pair(x,y));
			//맵을 만들자.
			rMax = max(rMax,z);
			xMax = max(xMax,x);
			yMax = max(yMax,y);
			makeMap(tmp);
		}
		if(rMax==0) zCheck=true;
		while(!q.empty() && !zCheck){
			pair<int,int> tmp = q.front();
			q.pop();
			if(!visited[tmp.first][tmp.second]){
				group++;
				bfs(tmp.first, tmp.second, group);
			}
		}
		printMap();
		if(zCheck) {
			cout << 0;
			return 0;
		}
		cout << group-1 << endl;
		//시간/메모리 줄일 수 있을듯
	}
}

정답

블로그를 참조했다.

중심이(A1,B1)이고 반지름은 r1인 원 A
중심이(A2,B2)이고 반지름은 r2인 원 B

겹치는 것 확인 = (A-C)^2 + (B-D)^2 <= (R1+R2)^2 임을 확인하면 된다…

따라서 각각의 진영정보를 토대로 서로 겹치는지만 확인하면 아주 쉽게 끝난다.

#define getDist(x0,y0,x1,y1) ((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1))
#define dbl(r) (r*r)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
int testcases;
int N; int
enemy[3001][3];
bool isVisit[3001];
int enemyNum;
int adj[3001][3001];
int adjSize[3001];
int main()
{
	cin >> testcases;
	while (testcases--) {
		enemyNum = 0;
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 3; j++) {
				cin >> enemy[i][j];
			}
			isVisit[i] = false;
			adjSize[i] = 0;
			for (int j = 0; j < N; j++) {
				adj[i][j] = -1;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (i == j) continue;
				int dist = getDist(enemy[i][0], enemy[i][1], enemy[j][0], enemy[j][1]);
				int bound = dbl((enemy[i][2] + enemy[j][2]));
				if (dist <= bound ){
					adj[i][adjSize[i]] = j;
					adj[j][adjSize[j]] = i;
					adjSize[i]++; adjSize[j]++;
				}
			}
		}
		for (int i = 0; i < N; i++) {
			if (!isVisit[i]) {
				enemyNum++;
				queue<int> bfs;
				bfs.push(i);
				while (!bfs.empty()) {
					int now = bfs.front();
					bfs.pop();
					for (int iter = 0; iter < adjSize[now]; iter++) {
						int next = adj[now][iter];
						if (!isVisit[next]) {
							bfs.push(next);
							isVisit[next] = true;
						}
					}
				}
			}
		}
		cout << enemyNum << endl;
	}
	return 0;
}

Twitter Facebook Google+ LinkedIn

[풀이]백준 풀이(XIV/16988 등)

문제풀이

[Re]Baaaaaaaaaduk2 - Easy(16988)

[RE]Count Circle Groups(10216)

공유하기

댓글남기기

참고

[TIL]20220629 SIDE PROJECT

[TIL]20220620 SIDE PROJECT

[TIL]20220618 REACT

[TIL]20220617 REACT