기록을

문제 링크

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

섬의 개수를 파악한다고 자주 기술했었는데, 간단하게 floodfill을 수행해주면 된다.

그림의 수를 파악하고, 그림의 넓이를 담아둘 때는 방문 처리 배열을 사용한다.

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

int map[500][500], dist[500][500];
int row, col;

queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0, };

int cnt = 0;
void bfs(pair<int, int> start) {
	cnt++; //섬개수 확인
	q.push(start);
	dist[start.first][start.second]++; 
	int di = 2; //위에서 시작점 방문하면 거리 1이니까, 다음으로 들어갈 거리는 2

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];

			if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 0 || dist[nr][nc] > 0)continue;

			q.push({ nr, nc });
			dist[nr][nc] = di;
			di++;
			
		}
	}
}

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

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			if (map[i][j] == 1 && dist[i][j] == 0)
				bfs({ i, j });
		}
	//방문처리 배열에 카운트를 해뒀기때문에 그 안에서 최댓값을 구하면 된다.
	int Max = -1;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (dist[i][j] > Max)
				Max = dist[i][j];
		}
	}
	cout << cnt << '\n' << Max << '\n';
	return 0;
}

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

좌표 평면위의 점의 최장 거리를 이루는 두 점은 하나의 볼록 껍질 위에 존재한다는 것을 이용해서 푼다.

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

모든 노드의 연결 관계를 파악해야한다.

n 이 500이므로 플로이드 와샬을 사용할 수 있고, 모든 정점으로부터 다른 모든 정점까지의 비용을 파악할 수 있다.

비용은 1로 두고, 갈 수 있는지 없는지만 파악하면 된다.

주의할 사항은, degree를 계산할 때, 자신에서 자신으로 가는 것은 카운트하지 않아야 한다는 것이다.

자기 자신으로의 경로 비용 초기화를 어떻게 했는지에 따라 잘 처리해주면 되겠다.

priority queue가 터져서 최근에 메모리 초과를 몇번 받았다.

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

투포인터를 활용해주면 된다.

길이를 언제 갱신하고, 무한루프를 어느 위치에서 종료할 것인지만 명확히 해준다면 무리없이 풀리는 문제이다.

현재까지 더한 구간합이, 넘겨야할 합보다 크다면 일단 그 시점의 길이가 최소 길이인지 비교해서 갱신해준다.

이후 왼쪽 인덱스 포인터를 증가시키고 길이를 감소시키고, 변화된 상태가 조건을 만족하는지 확인해주고 이런 흐름이다.

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

상관없는지 모르겠으나 원래는 kij순으로 루프 돌아야한다

문제 이름에서부터 플로이드 와샬 알고리즘을 사용해야 한다는 것을 암시하고 있는 문제이다.

주의할 것은, 이전까지 INF 값으로 limits.h 헤더에 있는 INT_MAX를 사용했는데, 이 값에 어떤 값이 더해지는 연산을 하게되면 오버플로우가 발생한다.

다익스트라, 벨만포드에서는 괜찮았지만 플로이드에서 이런 일이 생기니, 그냥 속편하게 내가 INF를 지정해서 써야겠다.

INF는 항상 (간선 가중치의 최댓값 ) * (정점 개수 - 1 ) 보다 크게 잡아줘야 한다.

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

벨만 포드 알고리즘을 사용하는 문제는 음수 가중치를 가지고 무언가를 하는 문제들인데, 거리 / 비용을 음수로 주기는 표현이 애매하기 때문에 이 문제에서처럼 시간을 가지고 문제를 만드는 것 같다. 웜홀, 시간 여행 등의 주제로 나오는 것 같다.

초기에 간선들의 정보를 받아주고, 다익스트라와 동일하게 모든 정점으로 가는 비용을 무한대로 초기화 한다.

그리고 n-1번에 거쳐서, 모든 정점들의 모든 간선들을 탐색해주고, 마지막 한 번은 음수 사이클 검사용으로 탐색해준다.

마지막 1번의 검색에서, 즉 가장 바깥 루프의 n번째 탐색시에, 경로 / 비용의 갱신이 발생한다면, 이 그래프는 음수 사이클을 포함하고 있다는 의미이다.

그렇지 않으면, 당연히 n개의 정점을 최소비용으로 이동하는 데에 n-1개의 간선이면 충분하기 때문이다.

n-1개 이상 간선을 사용한다는 것은? 어딘가에 음수 사이클이 있기 때문에 계속 그곳을 지나가게끔 갱신이 발생되고 있다는 의미이다.

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

다익스트라 알고리즘을 구현해주면 된다.

방문했던 노드를 다시 방문하지 않도록 해주어야 TLE를 피할 수 있을 것이다.

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

가중치가 있는 그래프의 최소 비용 / 최단 경로를 구하는 문제이다.

가중치들이 모두 양수이기 때문에 다익스트라를 이용한다.

먼저 시작점으로부터 i번 노드까지 가는 총 비용을 의미하는 dist[i]를 무한대로 초기화한다.

알고리즘이 시작되면, 시작점으로부터 시작점까지의 비용은 0인 것이 자명하기 때문에 dist[시작점] = 0으로 바꿔준다.

그리고 시작점으로부터의 거리가 가장 낮은 것부터 뽑을 것이기 때문에 min heap을 사용한다.

이 때, pair에 특정 노드번호와, 그 노드까지 가는 비용을 함께 관리할 것이다. 주의할 점은, pair의 대소 비교는 first부터 일어나기 때문에 반드시 비용을 first에 넣어줄 수 있도록 한다.

이후로는 현재노드까지 오는 비용 + 이동할 수 있는 노드로의 이동 비용 < 다음 노드까지 가는 총비용

위의 경우에 다음 노드까지 가는 총 비용을 갱신해준다.

갱신되는 경우에, heap에 갱신되는 지점을 넣어주도록 하자.

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

최소 공통 조상 (Lowest Common Ancestor)를 찾는 알고리즘이다.

1. dfs로 트리를 만든다. 이때 노드별 깊이 정보와(root 깊이 = 0) 가장 첫번째 부모 정보를 잡아준다.

2. 노드 A의 2^k번째 부모 노드는, A의 2^k-1번째 부모 노드의 2^k-1번째 부모 노드와 같다는 것을 이용해서 바텀업 dp로 부모 배열을 채운다.

3. 공통 조상을 찾을 a, b가 있다면, 우선 깊이가 깊은 곳과 낮은 곳을 확실히 구분해준다. 그리고 둘의 높이를 맞춰준다.

n개의 노드가 있다고 했을 때, 2의 거듭제곱으로 타고 올라갈 수 있는 최대 높이가 MAXK =(int)floor(log2(n)); 이다.

두 노드의 높이 차이가, 위에서부터 보고 내려온 2의k승보다 크거나 같아지는 순간마다 깊은 노드를 해당하는 2의 k번째 부모로 갱신한다.

결국 높이가 같아지게 되고, 이때 두 노드의 값이 같다면 반환해주면 된다.

그렇지 않다면

4. 위와 비슷한 방식으로, 2의최대 거듭제곱부터 아래로 내려오면서 부모의 노드가 같은지 확인한다. 다를때마다 두 노드를 다른 순간의 2의 k승번째 노드로 갱신해준다. 결국 둘이 같아지게 된다