[풀이]백준 풀이(XVI/11729 등)

문제풀이

아기상어(16236, 시뮬레이션 & BFS)

  • N*N 배열
  • 물고기 M마리 (한 칸에는 1마리만)
  • 아기상어 1마리

  • 상어, 물고기는 크기를 가지고 있다. (Tuple 사용?)

  • 상어는 크기 2로 시작, 1초에 상하좌우 1칸씩 이동가능 (dx, dy)

  • 더이상 먹을 수 있는 물고기가 없다면 아기상어는 엄마상어에게 도움을 청한다.
  • 먹을 수 있는 물고기가 1마리라면 그 물고기를 먹으러 간다.

  • 먹을 수 있는 물고기가 많다면 거리가 가장 가까운 물고기를 먹으러 간다.

  • 거리는 지나야하는 칸의 개수이다.
  • 거리가 같은 물고기가 있다면 가장위의 물고기를 그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기를 먹는다.

(같은 거리에 있는 경우 왼쪽부터 ) (같은 높이에 여러마리 있는 경우 왼쪽부터)

«^ »^ »> 이렇게 있으면

  • 아기상어가 엄마에게 도움을 청할때 까지 걸리는 시간.

  • 왔던 곳을 다시 방문할 수 있다. 물고기를 잡아먹은 곳에서 함수를 실행해서 가능한지 안한지 판별 반복한다.

물고기 피해가는거 구현,,,, 크기가 같은 물고기는 지나갈 수 있다

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <tuple>

#define INF 987654321

using namespace std;
int map[21][21];
int Answer = 0;
int n, jawsSize = 2, currentJawsX, currentJawsY, currentFishX, currentFishY;
int eaten = 0, minDist = INF, minDistTemp, compare;
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1,-1,  0, 0 };
int bfsDist[21][21];
bool visited[21][21];
queue<pair<int, int>> nxt;

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map[i][j] = -1;
			bfsDist[i][j] = -1;
			visited[i][j] = false;
		}
	}
}
bool isSizeup() {
	if (eaten == jawsSize) return true;
	else return false;
}
bool isInside(int x, int y) {
	if (x >= 0 && y >= 0 && x < n && y < n) return true;
	else return false;
}
bool isEmpty() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] > 0) {
				//상어가 아닌 0이상의 정수(물고기)가 하나라도 있으면 false
				if (map[i][j] != 9) return false;
			}
		}
	}
	return true;
}
bool isNext(int origin, int compare) {
	//비교한 거리가 더 가까우면 후보변경
	if (origin >= compare) return true;
	else return false;
}
int calcDist(int i, int j) {
	//상어와 물고기의 맨하탄 디스탄스 리턴
	int x = abs(currentJawsX - i);
	int y = abs(currentJawsY - j);
	return x + y;
}
//물고기를 찾는다.
//만약 없다면-> 엄마상어 호출 or 다먹은 경우(isEmpty)
//만약 있다면-> 어떤 물고기 먹을지 고르는 함수();
//반복주기 -> findFish() -> selectFish() -> isSizeup()
void printMap() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
void bfs(int sx, int sy) {
	queue<pair<int, int>> q;
	q.push(make_pair(sx, sy));
	visited[sx][sy] = true;
	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			//방문한 적 없고,
			if (!visited[nx][ny] && isInside(nx, ny)) {
				//지나갈 수 있으면
				if (jawsSize >= map[nx][ny]) {
					q.push(make_pair(nx, ny));
					visited[nx][ny] = true;
					bfsDist[nx][ny] = bfsDist[cx][cy] + 1;
				}
			}
		}
	}
}
void selectFish() {
	minDist = INF;
	minDistTemp = minDist;
	//init visited;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visited[i][j] = false;
			bfsDist[i][j] = 0;
		}
	}
	bfs(currentJawsX, currentJawsY);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			//물고기이고
			if (map[i][j] > 0) {
				//상어가아니고
				if (map[i][j] != 9) {
					//상어보다 작은 물고기이며 범위안이며니
					if (map[i][j] < jawsSize) {
						if (isInside(i, j)) {
							//만약 [i][j]를 갈 수 잇으면
							if (visited[i][j]) {
								//거리를 계산한 뒤
								//가까운지를 확인하고(거리가 작거나 같음)
								if (minDist > bfsDist[i][j]) {
									//거리의 최소값을 갱신한다.
									minDist = min(minDist, bfsDist[i][j]);
									//만약 거리가 작다면 잡아먹을 물고기후보 변경!
									currentFishX = i;
									currentFishY = j;
								}
								//만약 이전 최소와 거리가 같다면
								else if (minDist == bfsDist[i][j]) {
									//가장 위인지 비교 
									//만약 다음물고기가 더 위라면
									if (currentFishX > i) {
										currentFishX = i;
										currentFishY = j;
									}
									//만약 둘의 높이가 같다면
									else if (currentFishX == i) {
										//좌 우를 비교하여 잡아먹을 물고기후보 변경!
										if (currentFishY > j) {
											currentFishX = i;
											currentFishY = j;
										}
									}
								}
							}
						}
						//예외(거리1)
					}
				}
			}
		}
	}
}

void findFish(int x, int y, int size) {
	currentJawsX = x;
	currentJawsY = y;
	//물고기위치도 처음위치로 가자.
	currentFishX = INF;
	currentFishY = INF;
	if (isEmpty()) {
		return;
	}
	//사이즈가 커져야하면
	if (isSizeup()) {
		jawsSize++;
		eaten = 0;
	}

	//모든점을 돌아 최소거리의 물고기를 선택한 상태
	selectFish();
	//다 돌았는데 고를 수 있는 물고기가 없다?
	if (INF == currentFishX && INF == currentFishY) {
		return;
	}
	else {
		Answer += bfsDist[currentFishX][currentFishY];
		//원래 상어가 있던 자리를 0으로 변경하고
		map[currentJawsX][currentJawsY] = 0;
		//물고기 잡아먹기
		currentJawsX = currentFishX;
		currentJawsY = currentFishY;

		//상어 위치변경과 먹은 수 증가
		map[currentJawsX][currentJawsY] = 9;
		eaten++;
		//새로 탐색
		findFish(currentJawsX, currentJawsY, size);
	}
}

int main() {

	cin >> n;
	//초기화
	init();
	int x, y;
	//우선순위  크기 > 거리 > 높이 > 왼쪽
	//상어크기는 자신과 크기가 같은 수의 물고기를 먹을 때 1증가한다.
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				x = i;
				y = j;
			}
		}
	}
	findFish(x, y, jawsSize);
	cout << Answer << endl;
}

유기농 배추(1012, BFS)

  • 지렁이는 배추근처에 서식하며 해충을 잡아먹는다.
  • 어떤 배추에 지렁이가 있는 경우 지렁이는 인접한 칸으로 이동할 수 있다. (상,하,좌,우)
  • 배추들이 곳곳에 퍼져있을 때 필요한 지렁이의 최소마리수

풀이

단순 그룹화를 하는 문제이다. ezez

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

int test_case, m, n, k,group=0;
int map[51][51];
int dist[51][51];
int dx[] = {0, 0, 1, -1};
int dy[] = {1,-1, 0,  0};
bool visited[51][51];

bool isInside(int x, int y){
	if(x>=0 && y>=0 && x<n && y<m) return true;
	else return false;
}
void init(){
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			map[i][j] = 0;
			dist[i][j] = 0;
			visited[i][j] = false;
			group = 0;
		}
	}
}
void printMap(){
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
}

void bfs(int sx, int sy){
	queue<pair<int,int>> q;
	q.push(make_pair(sx,sy));
	visited[sx][sy] = true;

	while(!q.empty()){
		int cx, cy;
		cx = q.front().first;
		cy = q.front().second;
		q.pop();
		for(int i=0; i<4; i++){
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if(!visited[nx][ny] && map[nx][ny]==1 && isInside(nx,ny)){
				q.push(make_pair(nx,ny));
				visited[nx][ny]=true;
			}
		}
	}
}
int main(){
	cin >> test_case;
	for(int i=0; i<test_case; i++){
		//초기화
		init();
		//m=가로길이, n=세로길이, k=배추 갯수
		cin >> m >> n >> k;

		//배추 세팅
		for(int a=0; a<k; a++){
			int x, y;
			cin >> x >> y;
			map[y][x] = 1;
		}

		for(int a=0; a<n; a++){
			for(int b=0; b<m; b++){
				if(map[a][b]>0 && !visited[a][b]) {
					bfs(a,b);
					group++;
				}
			}
		}
		cout << group << endl;
	}
}

[RE]경로 찾기(11403, DFS/BFS)

  • 가중치 없는 방향 그래프 G
  • 모든 정점(i,j)에 대해 i to j가 가능한지 구하는 프로그램을 작성

회고

  • BFS로 하다가 뻘짓을 많이했다..
  • DFS가 훨씬 편한데.. BFS로 다시 풀어보긴하자
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int n;
int graph[100][100];
int visited[100];
int result[100][100];

void initVisit(){
	for(int i=0; i<n; i++){
		visited[i]=0;
	}
}
void init(){
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			graph[i][j] = 0;
			result[i][j] = 0;
		}
	}
}
//반복을 많이하네
void dfs(int s){
	for(int i=0; i<n; i++){
		if(graph[s][i]>0 && !visited[i]){
			visited[i]++;
			dfs(i);
		}
	}
}
int main(){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);


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

	for(int i=0; i<n; i++){
		initVisit();
		dfs(i);

        for(int j=0;j<n;j++){
            if(visited[j])
                graph[i][j]=1;
        }
	}

	cout << "\n";
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout << graph[i][j] << " ";
		}
		cout << "\n";
	}
}

나무 재테크(16235)

  • N*N크기의 땅 구매 (r,c)로 위치표기
  • r>=1 c>=1
  • 땅의 기본 양분은 5이다.
  • 땅에 M개의 나무를 심는다.
  • (한 칸에 여러그루의 나무가 있을 수도 있다.)

봄

  • 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가한다.
  • 여러그루의 나무가 있을 경우 어린나무부터 양분을 먹는다.
  • 양분이 부족할 경우 나무는 즉시 죽는다.

여름

  • 봄에 죽은 나무가 영양분으로 변한다.(죽은 나무의 나이 /2, 버림연산)

가을

  • 나이가 5의 배수인 나무가 번식한다.
  • 번식할 경우 인접한 8칸에 나이가 1인 나무가 생긴다.

겨울

  • 로봇이 돌아다니며 양분을 추가한다. A[r][c]만큼씩 추가.

K년이 지난 후 살아있는 나무의 개수는?

tip - tuple은 정렬이 어렵다.

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

int n, m, k;
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1,  0,  1,-1, 1,-1, 0, 1 };
//<x, y, age>
vector<int> tree[10][10];
vector<int> treeTemp[10][10];
queue<tuple<int, int, int>> forAdd;
queue<tuple<int, int, int, int>> forNut;
//땅-양분정보
int treeCount[10][10];
int nut[10][10];
//1년이 지날 때마다 추가될 양분
int a[10][10];

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			//기본양분 세팅
			nut[i][j] = 5;
			a[i][j] = 0;
		}
	}
}
void addNut() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			nut[i][j] += a[i][j];
		}
	}
}
int calcTree() {
	int Answer = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int treeSize = tree[i][j].size();
			if (treeSize > 0) {
				for (int k = 0; k < tree[i][j].size(); k++) {
					if (tree[i][j].at(k) > 0) {
						Answer++;
					}

				}
			}
		}
	}
	return Answer;
}
bool isInside(int x, int y) {
	if (x >= 0 && y >= 0 && x < n && y < n) return true;
	else return false;
}
void afterYear() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int treeSize = tree[i][j].size();
			if (treeSize > 0) {
				//소팅부터해놓고 (나이가 어린 나무부터 처리하기 위해서)
				sort(tree[i][j].begin(), tree[i][j].end());
				for (int k = 0; k < treeSize; k++) {
					//각 칸에 위치한 나무만큼 반복

					//양분이 충분할 경우  && 죽지않은 나무에 한해서 (봄)
					//tree[i][j].at(k) = (i,j)에 위치한 k번째 (나이순) 나무의 나이
					if (nut[i][j] >= tree[i][j].at(k) && tree[i][j].at(k) > 0) {
						nut[i][j] -= tree[i][j].at(k);
						tree[i][j].at(k)++;

						//(가을)살아남아야만 번식이가능하므로
						if (tree[i][j].at(k) % 5 == 0 && tree[i][j].at(k) != 0 ) {
							for (int l = 0; l < 8; l++) {
								//인접한 방향에 1짜리 나무를 집어넣는다
								if (isInside( i + dx[l], j + dy[l] )) {
									forAdd.push(tuple<int, int, int>(i + dx[l], j + dy[l], 1));
								}
							}
						}
					}
					//죽음
					else {
						//양분보충
						forNut.push(tuple<int, int, int, int>(i , j, floor(tree[i][j].at(k) / 2), k));
					}
				}
				//양분이 부족한 경우 (여름)
				while (!forNut.empty()) {
					int ti, tj, ta, tk;
					tie(ti, tj, ta, tk) = forNut.front();
					forNut.pop();
					nut[ti][tj] += ta;
					tree[ti][tj].pop_back();
					//tree[ti][tj].at(tk) = 0;
				}
			}
		}
	}
	//가을 번식
	while (!forAdd.empty()){
		int ti, tj, tk;
		tie(ti, tj, tk) = forAdd.front();
		forAdd.pop();
		tree[ti][tj].push_back(tk);
	}
	//겨울.. 
	addNut();
}


int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	//n =땅크기, m = 나무수, k= 지난 연도수
	cin >> n >> m >> k;
	//초기화
	init();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y, age;
		cin >> x >> y >> age;
		tree[x-1][y-1].push_back(age);
	}
	for (int i = 0; i < k; i++) {
		afterYear();
	}
	cout << calcTree() << endl;
}

댓글남기기

참고