이것 저것 &

문제링크: https://www.acmicpc.net/problem/2234

비트마스킹문제입니다.

접근방식

1. 입력값이 1,2,4,8의 합으로 들어오기 때문에 비트마스킹을 사용하기로 생각

2. 성에 있는 방의 개수는 bfs를 통해 구현

3. 가장 넓은 방의 넓이도 bfs과정에서 함께 도출

4. 하나의 벽을 제거하는 과정은 반복문을 사용한 브루트포스로 구현

문제풀이 

1. bfs를 통해서 1,2번 결과 도출

   비트마스킹값을 보며 진행! if (visited[ny][nx] == 0 && (((1 << i) & arr[cy][cx]) == 0)) 일때만 탐색!

for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny >= 0 && ny < m && nx >= 0 && nx < n)
				if (visited[ny][nx] == 0 && (((1 << i) & arr[cy][cx]) == 0)) {
					visited[ny][nx] = one;
					two_count++;
					que.push(make_pair(ny, nx));
				}
		}

2. 3번은 모든 점에서 4방향을 다 체크해주며 진행!

n,m둘다 <= 50 이라서 시간 괜찮다.

아래는 정답 코드

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

int arr[51][51] = { 0, };
int visited[51][51] = { 0, };
int two_arr[2600] = { 0, };
int n, m;
int one = 0, two = 0, three = 0;
int y_ar[4] = { 0,-1,0,1 };
int x_ar[4] = { -1,0,1,0 };
int bfs(int y, int x) {
	int two_count = 1;
	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = one;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny >= 0 && ny < m && nx >= 0 && nx < n)
				if (visited[ny][nx] == 0 && (((1 << i) & arr[cy][cx]) == 0)) {
					visited[ny][nx] = one;
					two_count++;
					que.push(make_pair(ny, nx));
				}
		}
	}
	return two_count;

}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++)
			if (visited[i][j] == 0) {
				one++;
				two_arr[one] = bfs(i, j);
				if (two_arr[one] > two)
					two = two_arr[one];
			}
	}


	//3. 
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++) {
			
			for (int k = 0; k < 4; k++) {
				
				if (((1 << k) & arr[i][j]) != 0){
					
					int ny = i + y_ar[k];
					int nx = j + x_ar[k];
					if (ny >= 0 && ny < m && nx >= 0 && nx < n) {
						
						if(visited[i][j] != visited[ny][nx])
							three = max(three, two_arr[visited[i][j]] + two_arr[visited[ny][nx]]);
						
					}
					
				}
			}
			
		}
	
	cout << one << endl;
	cout << two << endl;
	cout << three << endl;
	return 0;
}

문제풀이: www.acmicpc.net/problem/14567

전형적인 비트마스킹(up-down) 문제입니다.

재귀함수를 사용하되, 배열에 방문값들을 저장하는 형태로 풀어나가면 됩니다! 

아래는 정답코드입니다.

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

int n = 0, m = 0;
vector <int> vec[1001];
int dp[1001] = {0, };

int solved(int num) {
	if (vec[num].size() == 0)
		return 1;
	int& ret = dp[num];
	if (ret != 0) return ret;

	ret = 1;
	for (int i = 0; i < vec[num].size(); i++) {
		ret = max(ret, solved(vec[num][i]) + 1);
	}

	return ret;
}

int main() {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		vec[t2].push_back(t1);
	}

	for (int i = 1; i <= n; i++) {
		cout << solved(i) << ' ';
	}
	cout << endl;
}