~~재제출 죄송합니다.~~

연결 요소의 개수

문제 링크

http://icpc.me/11724

풀이

BFS 혹은 DFS를 돌려주면서 방문 여부를 체크를 해줍니다.
BFS나 DFS를 몇 번 실행했는지 카운트하면 됩니다.

섬의 개수

문제 링크

http://icpc.me/4963

풀이

11724번과 같은 문제입니다.
아래와 같은 코드를 이용하면 조금 더 쉽게 구현할 수 있습니다.

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

inline bool bound(int i, int j){
  return 1 <= i && i <= n && 1 <= j && j <= m;
}

바이러스

문제 링크

http://icpc.me/2606

풀이

DFS, BFS, Floyd-Warshall 중 원하는 방법을 골라 적당히 풀어봅시다.

단지번호붙이기

문제 링크

http://icpc.me/2667

풀이

BFS를 돌면서 단지의 번호를 붙여줍시다.
BFS를 호출할 때마다 붙여줄 번호를 바꿔줍시다.

경로 찾기

문제 링크

http://icpc.me/11403

풀이

DFS, BFS, Floyd-Warshall 중 원하는 방법을 골라 적당히 풀어봅시다.

키 순서

문제 링크

http://icpc.me/2458

풀이

자신이 몇 번째 순서인지 알 수 있는 방법은 나보다 큰 사람의 수를 알거나, 나보다 작은 사람의 수를 알면 됩니다.
Floyd-Warshall을 이용해 쉽게 풀 수 있습니다.

케빈 베이컨의 6단계 법칙

문제 링크

http://icpc.me/1389

풀이

가중치가 모두 1인 그래프에서 최단 거리를 구해야 합니다.
가중치가 모두 1이니 BFS를 돌려도 되고, 정점의 개수가 적으니까 Floyd-Warshall을 돌려도 됩니다.

그대, 그머가 되어

문제 링크

http://icpc.me/14496

풀이

모든 간선의 가중치가 1인 그래프로 모델링해봅시다.
BFS를 이용해 최단거리를 구할 수 있습니다.

미로 탐색

문제 링크

http://icpc.me/2178

풀이

BFS!

토마토

문제 링크

http://icpc.me/7576

풀이

BFS를 쭉 돌리면서 각 칸에 있는 토마토가 언제 익게 되는지 구해줍시다.
BFS를 다 돌았는데 안 익은 토마토가 있다면 -1을 출력해주고, 그렇지 않다면 얼마나 걸렸는지 출력하면 됩니다.

토마토

문제 링크

http://icpc.me/7569

풀이

7576 문제를 3차원으로 확장하면 됩니다.

int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};

안전 영역

문제 링크

http://icpc.me/2468

풀이

물이 h만큼 찼을 때 영역이 몇 개인지 구해주는 것을 반복하면 됩니다.

최대 힙

문제 링크

http://icpc.me/11279

풀이

priority_queue<int> pq;

최소 힙

문제 링크

http://icpc.me/1927

풀이

priority_queue<int, vector<int>, greater<int> > pq;

혹은 최대 힙을 사용하되, 각 데이터에 -1을 곱해줘도 됩니다.

절댓값 힙

문제 링크

http://icpc.me/11286

풀이

pair<int, int>에 {절댓값, 음수/양수 여부} 형태로 저장을 한 뒤, priority_queue에 넣어줍시다.

가운데를 말해요

문제 링크

http://icpc.me/1655

풀이

출력할 값은 root에 저장하고, root 왼쪽에는 max heap, 오른쪽에는 min heap을 놓은 형태로 트리를 만들어줍시다.
BST비슷한 느낌으로 max heap에는 root보다 작거나 같은 값을 저장하고, min heap에는 root보다 크거나 같은 값을 저장해줍니다.
홀수번째 원소를 볼 때는 max heap과 min heap의 크기가 같아야 root에 중앙값이 저장됩니다. 짝수번째의 경우에는 둘 중 더 작은 값을 출력해야하므로 min heap의 크기가 더 커야 합니다.
minHeap과 maxHeap의 균형을 맞추는 작업은 아래 코드의 relax 부분을 참고해주세요.

1655코드