급하게임개발

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

이 문제의 경우 쉬운 전형적인 bfs문제이다. 모든 정점을 시작점으로 bfs를 돌린다 그 후 정점을 시작점으로 돌리는 케이스마다의 각 정점의 layer의 합을 저장한 후 이를 비교하여 최솟값을 갖는 정점의 값을 출력해 주면 되는 문제였다

bfs의 기본적이 풀이 로직은 이 블로그의 다른글들에 있다. 코드는 아래와 같다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M;
vector<int> bfsv[101];
int arr[101] = { 0, };
int main() {
	queue<pair<int, int>> bfsq;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		bfsv[temp1].push_back(temp2);
		bfsv[temp2].push_back(temp1);
	}
	for (int i = 1; i <= N; i++) {
		int start = i;
		bfsq.push({ start,0 });
		bool isVisited[101] = { 0, };
		while (!bfsq.empty()) {
			int front = bfsq.front().first;
			int second = bfsq.front().second;
			arr[front] += second;
			isVisited[front] = true;
			bfsq.pop();
			for (int j = 0; j < bfsv[front].size(); j++) {
				if (!isVisited[bfsv[front][j]]) {
					bfsq.push({ bfsv[front][j], second + 1 });
					isVisited[bfsv[front][j]] = true;
				}
			}
		}
	}
	int min=5001;
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (min > arr[i]) {
			ans = i;
			min = arr[i];
		}
	}
	cout << ans;
}

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

이 문제는 전형적인 bfs문제이다 일단 예시로 주어지는 그림부터가 이문제는 bfs로 푸는 것이다라고 알려주고 있다. 이에 이문제는 bfs로 풀어주면 된다 bfs 문제는 queue를 많이 사용한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M;
int arr[1002][1002] = { 0,};
int answer[1002][1002] = {0,};
int startX, startY;
queue <pair<int,int>> bfsq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			int temp;
			cin >> temp;
			arr[i][j] = temp;
			if (temp == 2) {
				startX = i;
				startY = j;
			}
		}
	}
	bfsq.push(make_pair(startX, startY));
	answer[startX][startY] = 0;
	while (!bfsq.empty()) {
		startX = bfsq.front().first;
		startY = bfsq.front().second;
		bfsq.pop();
		if (arr[startX][startY + 1] == 1 && answer[startX][startY + 1] == 0) {
			bfsq.push(make_pair(startX, startY + 1));
			answer[startX][ startY + 1] = 1 + answer[startX][startY];
		}
		if (arr[startX][startY-1] == 1 && answer[startX][startY - 1] == 0) {
			bfsq.push(make_pair(startX, startY - 1));
			answer[startX][startY - 1] = 1 + answer[startX][startY];
		}
		if (arr[startX+1][startY] == 1 && answer[startX+1][startY] == 0) {
			bfsq.push(make_pair(startX+1, startY));
			answer[startX+1][startY] = 1 + answer[startX][startY];
		}
		if (arr[startX-1][startY ] == 1 && answer[startX-1][startY] == 0) {
			bfsq.push(make_pair(startX-1, startY));
			answer[startX-1][startY] = 1 + answer[startX][startY];
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (answer[i][j] == 0&& arr[i][j] == 1) {
				cout << -1 << " ";
			}
			else {
				cout << answer[i][j] << " ";
			}
		}
		cout << endl;
	}
}

전체 코드는 이렇게 되고 하나하나 설명을 하도록 하겠다.

bfsq.push(make_pair(startX, startY));
	answer[startX][startY] = 0;
	while (!bfsq.empty()) {
		startX = bfsq.front().first;
		startY = bfsq.front().second;
		bfsq.pop();
		if (arr[startX][startY + 1] == 1 && answer[startX][startY + 1] == 0) {
			bfsq.push(make_pair(startX, startY + 1));
			answer[startX][ startY + 1] = 1 + answer[startX][startY];
		}
		if (arr[startX][startY-1] == 1 && answer[startX][startY - 1] == 0) {
			bfsq.push(make_pair(startX, startY - 1));
			answer[startX][startY - 1] = 1 + answer[startX][startY];
		}
		if (arr[startX+1][startY] == 1 && answer[startX+1][startY] == 0) {
			bfsq.push(make_pair(startX+1, startY));
			answer[startX+1][startY] = 1 + answer[startX][startY];
		}
		if (arr[startX-1][startY ] == 1 && answer[startX-1][startY] == 0) {
			bfsq.push(make_pair(startX-1, startY));
			answer[startX-1][startY] = 1 + answer[startX][startY];
		}
	}

일단 위 코드의 이부분은 pair로 이루어진 큐에서 값을 뽑고 그값을 기준으로 상하좌우의 값을 큐에다가 다시 넣어준다 그후 넣어준큐의 순서에대한 값이 저장되어있는 answer배열에 나의 방문번째수 +1을 넣어서 해준다 즉 내가 2번 layer에 자식이라면 나의 상하좌우는 3번 layer 에 자식이된다

트리로 그리게 되면 이런 구조가 된다. 그후 내가 몇번째 layer에 있는지를 answer배열에 저장해주면 된다.