굳건하게

문제 : 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 값과 현재 시간을 비교해서 최소한의 턴 수 가 아니라면 더 탐색을 진행하지 않아도 된다.

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

안녕하세요, 여행벌입니다.

저번 포스팅에 이어서 컬렉션 프레임워크의 기반이 되는 Collection<E> 인터페이스의 메소드에 대해서 정리해보겠습니다.

Collection<E>

 모든 컬렉션클래스들은 Collection<E> 인터페이스를 직/간접적으로 구현하고 있습니다.

 따라서, Collection<E> 인터페이스에는 컬렉션을 다루는데 공통적으로 필요한 메소드들을 지원해주고 있습니다. 그럼 Collection 인터페이스에서 제공해주는 메소드들을 하나하나 정리해보도록 하겠습니다.

 예시는 컬렉션 클래스 중 하나인 LinekdList 컬렉션 클래스를 이용해서 보여드리겠습니다. 다음 포스팅에서 다룰 컬렉션 클래스이니 그냥 Collection 인터페이스에서 지원해주는 메소드 활용 방식만 참고하시면 될 것 같습니다.

boolean add​(E e)

 이름 그대로 해당 컬렉션에 요소를 추가해줍니다. 추가가 성공한다면 true 를 반환하고, 메모리 문제 등으로 요소 추가가 실패한다면 false를 반환합니다.

boolean add(int index, E e)

 원하는 index에 요소를 추가할 수 있습니다.

boolean addAll(Collection<? extends E> c)

 컬렉션 c에 있는 모든 요소들을 추가해줍니다.

 list 에 있는 모든 요소들을 list2에 addAll 해주면 list2 도 요소 5와 7이 생깁니다.

void clear()

 clear 메소드는 말 그대로 해당 컬렉션의 모든 요소들을 제거해줍니다.

boolean contains(Object o)

 contains 메소드는 컬렉션이 해당 요소를 가지고 있다면 true, 아니라면 false를 return 해줍니다.

boolean containsAll(Collecton<?> c)

 해당 컬렉션이 컬렉션 c의 모든 요소를 가지고 있다면 true, 아니라면 false를 return 해줍니다.

int size()

 해당 컬렉션의 size를 return 해줍니다.

boolean isEmpty()

 해당 컬렉션이 비어있다면 true, 아니라면 false를 return 해줍니다.

boolean remove(Object o)

 컬렉션에서 해당 요소를 찾아서 제거합니다. 제거가 성공하면 true, 실패하면 false 를 반환합니다.

boolean removeAll(Collection<?> c)

 해당 컬렉션에서 모든 요소를 제거합니다. 제거가 성공하면 true, 실패하면 false 를 반환합니다.

Collection 인터페이스에서 자주 사용되는 메소드들을 정리해보았습니다.

모든 컬렉션 클래스들에게 공통적으로 지원해되는 메소드로 꼭 익혀두시길 바랍니다.