굳건하게

문제 : https://www.acmicpc.net/problem/1194

비트마스킹 BFS 그래프탐색

[문제해석]

  '0' 지점에서 '1' 지점까지 탐색을 진행하는데 'a','b','c','d','e','f' 는 열쇠고 'A','B','C','D','E','F'는 각각 소문자 열쇠로 열 수 있는 문이다. 문을 열려면 열쇠가 있는 지점을 먼저 방문해서 열쇠를 가지고 방문해야된다.

[알고리즘풀이]

 전형적인 비트마스킹을 활용한 그래프 탐색 문제로 열쇠가 6 종류 밖에 없는 점에 집중해 비트마스킹으로 현재 어떤 열쇠들을 가지고 있는지 표현해주면 된다. 

 visited[X][Y][curS] := (X, Y) 지점에 curS 열쇠 상태로 방문했을 때 최소 이동 횟수 라고 정의하면 문제를 쉽게 해결할 수 있다.

 1) 다음에 이동할 지점이 '.' 거나 '1' 이면 현재 이동 횟수 + 1 이 해당 지점에 현재 상태로 방문한 가장 작은 값이라면 이동을 진행한다.

 2) 다음에 이동할 지점이 열쇠가 있고 현재 이동 횟수 + 1 이 해당 지점에 현재 상태로 방문한 가장 작은 값이라면 이동을 진행한다. 그 후, 현재 상태에 해당 지점의 열쇠를 갱신해준다.

 | (OR) 연산을 이용하면 쉽게 갱신할 수 있다.

 ( curS | (1 << key) ) 

 3) 다음에 이동할 지점이 문이 있고 현재 이동 횟수 + 1 이 해당 지점에 현재 상태로 방문한 가장 작은 값이고, 현재 열쇠 상태가 해당 문을 열 수 있다면 이동을 진행한다.

 & (AND) 연산을 이용하면 현재 열쇠 상태로 문을 열 수 있는지 쉽게 확인할 수 있다.

 ( curS & (1 << door) )

[ 주의사항 ]

 열쇠가 총 6종류 이므로 비트마스킹을 (1 << 7) 로 진행해야되는데, (1 << 6) 으로 셋팅해서 개고생을 했다....! 조심, 또 조심!

[ 정답코드 ]

문제 : https://www.acmicpc.net/problem/17025

BFS DFS 탐색

[문제해석]

'.' 은 빈 공간, '#' 은 아이스크림을 나타낼 때, #이 연결된 부분은 하나의 아이스크림 덩어리가 된다. 이때, 아이스크림 덩어리의 Area(영역너비)와 Perimeter(둘레)를 구해서 영역너비가 가장 크고, 가장 큰 값이 여러개라면 가장 둘레가 작은 아이스크림 덩어리를 찾아달라.

[알고리즘]

 BFS 탐색을 진행하며 아이스크림 덩어리를 하나하나 탐색한다. 이때, 영역너비는 BFS 탐색을 진행하며 탐색하는 칸의 수가 영역너비가 된다. 둘레는 현재 탐색 중인 '#' 의 위, 아래, 오른쪽, 왼쪽을 탐색해 범위 밖이거나 '.' 라면 경계가 존재하므로 둘레로 카운트한다.

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

using namespace std;

int N, dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
int ansArea = -1, ansPerimeter = -1;
char map[1000][1001];
bool visited[1000][1000];
vector<pair<int, int>> ans;

bool checkRange(int x, int y) {
	return (0 <= x && x < N && 0 <= y && y < N);
}

int getPerimeter(int x, int y) {
	int res = 0;
	if (!checkRange(x + 1, y) || (checkRange(x + 1, y) && map[x + 1][y] == '.')) res++;
	if (!checkRange(x, y + 1) || (checkRange(x, y + 1)&& map[x][y + 1] == '.')) res++;
	if (!checkRange(x - 1, y) || (checkRange(x - 1, y) && map[x - 1][y] == '.')) res++;
	if (!checkRange(x, y - 1) || (checkRange(x, y - 1) && map[x][y - 1] == '.')) res++;
	return res;
}

void BFS(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x, y });
	visited[x][y] = 1;

	int area = 0, perimeter = 0;
	while (!q.empty()) {
		int curX = q.front().first, curY = q.front().second;
		area++, perimeter += getPerimeter(curX, curY);
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (checkRange(nextX, nextY) && !visited[nextX][nextY] && map[nextX][nextY] == '#') {
				q.push({ nextX, nextY });
				visited[nextX][nextY] = 1;
			}
		}
	}
	if (ansArea < area) {
		ansArea = area;
		ansPerimeter = ansPerimeter;
	}
	else if (ansArea == area) {
		ansPerimeter = min(ansPerimeter, perimeter);
	}

	return;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (map[i][j] == '#' && !visited[i][j]) BFS(i, j);
	
	cout << ansArea << ' ' << ansPerimeter << '\n';
	return 0;
}

문제 : https://www.acmicpc.net/problem/15898

#구현 #시뮬레이션

[ 문제해석 ]

5 x 5 가마에 4 x 4 크기의 재료들을 넣어서 폭탄을 제조한다. 이때, 4 x 4 크기의 재료는 가마의 격자를 벗어날 수 없고, 회전해서 넣을 수 있고 서로 다른 재료를 3가지 가마에 넣는다.

[ 알고리즘핵심 ]

4 x 4 크기의 재료는 최대 10개이고 회전해서 넣을 수 있으므로 최대 40개(회전시킨재료포함)의 재료에서 3가지 재료를 뽑는다고 생각해도 된다. 그 후, 이 재료들을 5 x 5 가마에 넣어야되는데 이때도 가마의 (0, 0) / (0, 1) / (1, 0) / (1, 1) 에 재료를 넣는 경우를 제외하고는 가마를 다 벗어난다.

 따라서, 백트레킹을 이용해 40개에서 3개를 뽑고, 4가지 위치 중에 하나를 고르는 모든 경우의 수를 구해도 복잡도가 40C3 * 4^3 밖에 나오지 않는다. 즉, 1초 안에 가능한 연산이다.

[ 알고리즘풀이 ]

1. 입력을 받으면 시계방향으로 90도, 180도, 270도 회전한 상태도 같이 effect, color 배열에 저장해준다.

2. 백트레킹1 - 백트레킹을 이용해 재료 3개를 뽑는다. 

3. 백트레킹2 - 재료 3개를 다 뽑은 상태에서, 재료 3개의 넣는 위치를 구한다.

4. 플레이게임 - 'W'로 초기화된 가마를 만든 후, 3가지 재료를 정해진 위치에 넣고 red, blue, green, yellow 효능 값을 구해주면 된다.

문제 : https://www.acmicpc.net/problem/15906

BFS DP

문제 해석

 (1,1) 에서 (r,c) 로 최대한 빠르게 이동하고 싶다. 이때, 일반상태에서는 상하좌우로 한 칸 씩만 이동이 가능하고, t 턴을 소모해 변신상태가 되면 상하좌우 중 '#' 이 있는 워프 지역으로 한 번에 이동이 가능하다.

문제 핵심

 일반 상태로도 진행할 수 있고, 변신 상태로도 탐색을 진행할 수 있으므로 현재 지점에서 일반 이동 과 변신을 시킨 후 변신 이동을 모두 진행해야한다.

알고리즘

 Dp[X][Y][S] := ( X, Y ) 지점에 상태 S로 도착하는데 필요한 최소한의 턴 수.

--> 현재 지점에서 nextX, nextY 로 이동할 때 Dp 값과 현재 시간을 비교해서 최소한의 턴 수 가 아니라면 더 탐색을 진행하지 않아도 된다.

 먼저 현재 지점에서 일반 이동을 해보고, 변신 상태가 아니라면 변신을 한 후 변신 이동을 해본다.