Q1. 2468 안전영역 > 문제 링크
문제에서 준 상황을 분석해보면,
물에 잠긴 지점을 회색으로 표시했을 때 안전구역을 그림으로 표시하면 아래와 같은 형태가 되어 안전 구역이 5개다.
그래서 우선 그래프 정보를 입력 받고 > 물에 잠긴 구역을 표시한 뒤 > 물에 잠기지 않은 점에서 그래프 탐색을 시행하여 탐색이 한 번 끝날 때마다 cnt 변수의 값을 증가 시키면 안전 구역의 개수를 구할 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int graph[101][101] = { 0 };
int water[101][101] = { 0 };
int check[101][101] = { 0 };
int depth[101];
int n, m, f1, f2;
int cnt = 0, res = 0;
vector<int> result;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
void dfs(int y, int x) {
check[y][x] = true;
for (int i = 0; i < 4; i++) { // 인접한 모든 부분 고려해야 하므로
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue; // 모서리의 경우 continue를 통해 예외처리
if (water[ny][nx] && !check[ny][nx]) { // 물에 젖지 않고 방문하지 않았을 경우 계속 탐색
check[ny][nx] = true;
dfs(ny, nx);
}
}
}
int findSafe(int h) {
for (int i = 0; i < n; i++) { // 물에 잠기는 영역 표시
for (int j = 0; j < n; j++) {
if (graph[i][j] < h) water[i][j] = 0;
else water[i][j] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (check[i][j] == 0 && water[i][j] == 1) {
dfs(i, j);
cnt++; // 한 번의 dfs가 끝나면 안전 구역의 수를 증가
}
}
}
return cnt;
}
int main() {
cin >> n;
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
// 모든 높이에 대해 안전구역의 수를 구해야 하므로, max 높이까지 for문을 돌리기 위해 max값 구함
if (graph[i][j] > max) max = graph[i][j];
}
}
for (int i = 0; i <= max; i++) {
// 안전구역의 수를 벡터에 저장
result.push_back(findSafe(i));
// 한 높이에 대해 안전 구역을 구했으면, 변수들을 새로 초기화
cnt = 0;
for (int k = 0; k < n; k++) {
for (int t = 0; t < n; t++) {
check[k][t] = 0;
}
}
}
cout << *max_element(result.begin(), result.end()) << endl; // 벡터 내에서 최댓값 출력
}먼저 그래프의 정보를 입력받고, 문제에서 모든 높이에 대해 안전 구역의 수를 구한 뒤 안전 구역의 수가 가장 많은 경우를 출력하라고 했으므로 for문을 구역의 최대 높이까지 돌리기 위해서 max 높이까지 함께 구한다.
이 작업이 끝나면 for문을 통해 안전 구역의 수를 구하게 된다. findSafe함수에 매개변수로 물에 잠기는 지점의 높이를 넘겨서 안전 구역을 구하게 된다.
반복문을 통해서 물에 잠기는 영역을 water 배열에 저장하고, 모든 점 중에서 방문한 적이 없고 물에 잠기지 않은 지역을 대상으로 dfs를 돌린다.
dfs는 기본 dfs 코드에 네 방향 인접함을 모두 따지게 수정하고, 물에 젖지않은 점을 탐색하도록 수정했다.
한 번 dfs가 끝나면 하나의 그래프를 찾은 것이므로, cnt 값을 추가하여 그래프 갯수를 세 주고, findSafe가 최종적으로 반환 할 때 리턴시킨다.
이 리턴된 값들을 result 벡터에 저장하고, 벡터의 최댓값을 찾아서 출력시킨다.
Q2. 2644 촌수 계산 > 문제 링크
예제의 상황을 그림으로 그려보면,
그래프에서 경로를 찾아보면 최단경로 그대로 n촌 관계가 형성 되어 있음을 확인할 수 있었다.
그리고 두 번째 예제에서 경로를 찾을 수 없는 경우 -1 출력이 됨도 확인할 수 있었다.
따라서 bfs를 이용해 최단경로를 구하는 로직을 적용해서 문제를 풀었다.
#include <iostream>
#include <queue>
using namespace std;
int graph[101][101] = { 0 };
int checked[101] = { 0 };
int depth[101];
int n, m, f1, f2;
int cnt = 0, res = 0;
void bfs(int x) {
queue<int> q;
q.push(x);
checked[x] = 1;
while (!q.empty()) {
x = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (graph[x][i] == 1 && checked[i] == 0) {
q.push(i);
checked[i] = 1;
depth[i] = depth[x] + 1;
}
}
}
}
int main() {
cin >> n >> f1 >> f2 >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a][b] = 1;
graph[b][a] = 1;
}
bfs(f1);
if (depth[f2] == 0) cout << -1 << endl;
else cout << depth[f2] << endl;
}먼저 그래프를 입력받아 노드를 입력받고, 문제에 입력된 부모 노드부터 bfs 탐색을 진행한다.
bfs를 진행하면서 가족 관계에 해당하는 노드를 찾으면 그 노드의 depth를 1 증가시켜서 저장 해준다.
그리고 최종적으로 문제에 입력된 자식 노드의 depth를 출력한다. (depth가 0인 경우 가족관계가 아닌 경우이므로 -1을 출력한다.)
