링크 : https://www.acmicpc.net/problem/2606
문제읽기
노드 연결이 하고 싶다!!
포인터를 사용하고 싶다!!
포인터는
- 1을 가리키는 포인터
- 1이 아닌 포인터
- 1이 아닌 원소를 가리키는 포인터. 만약 연결되었다면 이 포인터는 지워진다.
- 1과 연결되어 있지 않은 포인터. 예시의
4-7조합 말고도9-10이런 조합을 받아야 함. 여러 개임.
이렇게 하려고 했는데 2차원 bool 배열을 사용하는 것이 더 나을 것 같다.
제한이 100개가 걸려있으니 100X100 배열이고 받은 쌍의 위치를 체크하고 대각선으로 접어 동일하게 위치를 찍어준다. 다음 1부터 탐색하여 걸려있는 것들을 확인한다. 걸려있는 것들을 행 개념으로 걸러주고 탐색을 완료했다면 false로 찍어준다. 그래서 총 몇개가 걸려있는지 확인해본다!
그래서 벡터로도 접근해보고 배열로도 접근해봤지만 너무 시간만 흘려보내는 것 같아서 포기.
코드
#include <iostream>
using namespace std;
int map[101][101] = { 0 };
int visit[101] = { 0 };
int N, ans = 0;
void dfs(int n) {
ans++;
visit[n] = 1;
for (int i = 1; i <= N; i++) {
if (map[n][i] && !visit[i])
dfs(i);
}
}
int main() {
int n;
int x, y;
cin >> N >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y;
map[x][y] = map[y][x] = 1;
}
dfs(1);
cout << (ans - 1);
return 0;
}분석
다음 블로거의 분석을 참고했다.
링크1 : http://from20180718.blogspot.com/2018/09/c-2606-dfs-bfs.html
링크2 : https://ssu-gongdoli.tistory.com/12
링크2의 글을 분석해보자.
첫번째로 DFS, 2차원 벡터 배열로 접근해보자.
void dfs(int x) {
ans++;
visit[x] = true;
for (int k = 0; k < map[x].size(); k++) {
if (!visit[map[x][k]])
dfs(map[x][k]);
}
return;
}- 재귀로 들어가므로 한번 함수에 들어간 순간부터 count되니까
ans++해준다. - 그 후에는 탐색을 시작하였으므로
visit[x] = true;로 설정해주고map는 2차원 벡터 배열이므로 한 행의 크기만큼map[x].size()만큼 탐색한다. - 만약
map[x][k]를 탐색하지 않았다면 dfs로 다시 탐색에 들어간다.
두번째로는 내가 처음에 접근했던 것처럼 2차원 배열로 접근한다.
void dfs(int n) {
ans++;
visit[n] = 1;
for (int i = 1; i <= computer_num; i++) {
if (map[n][i] && !visit[i])
dfs(i);
}
}- 들어간 순간 count를 해준다.
- 방문한 컴퓨터를 체크해주는 용으로
visit[n] = 1;를 설정한다. - 컴퓨터 개수만큼, 즉 행의 크기만큼 접근한다. 여기서 내가 했던 것처럼 배열은 대칭이므로 왼쪽 부분을 탐색한다. 여기서 이미 탐색한 컴퓨터라면 넘어간다. 그걸
if (map[n][i] && !visit[i])으로 설정한 것이다.
마지막으로 플로이드 와샬을 이용한 풀이이다.
#include<cstdio>
int map[101][101] = { 0 };
int computer_num, ans = 0;
int main() {
int n;
int x, y;
scanf("%d %d", &computer_num, &n);
for (int i = 1; i <= computer_num; i++) {
for (int j = 1; j <= computer_num; j++) {
map[i][j] = 10000;
}
}
for (int i = 0; i < n; i++) {
scanf("%d %d", &x, &y);
map[x][y] = map[y][x] = 1;
}
for (int k = 1; k <= computer_num; k++) {
for (int i = 1; i <= computer_num; i++) {
for (int j = 1; j <= computer_num; j++) {
if (map[i][j] > map[i][k] + map[k][j])
map[i][j] = map[i][k] + map[k][j];
}
}
}
for (int i = 2; i <= computer_num; i++) {
ans += map[1][i] != 10000;
}
printf("%d", ans);
return 0;
}
시작해보자.
for (int i = 1; i <= computer_num; i++) {
for (int j = 1; j <= computer_num; j++) {
map[i][j] = 10000;
}
}컴퓨터 크기만큼 배열을 초기화시켜준다.
for (int i = 0; i < n; i++) {
scanf("%d %d", &x, &y);
map[x][y] = map[y][x] = 1;
}x와 y를 받아와서 초기화해준다. 이로써 연결된 노드는 1이고 연결되지 않은 부분들은 10000으로 설정되어 있다.
여기서 플로이드 와샬 알고리즘이 무엇인지 확인하고 들어가자.
링크 : https://blog.naver.com/ndb796/221234427842
다익스트라(Dijkstra) 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 하지만 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 한다. 다익스트라 알고리즘이 가장 적은 비용을 하나씩 선택하는 알고리즘이라면
플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다.
노드 1을 거쳐가는 경우를 계산해보자. X에서 Y로 가는 최소 비용은 X에서 노드 1로 가는 비용 + 노드 1에서 Y로 가는 비용과 비교되어 진다. 1을 거쳐서 가는 경우가 더 빠르다면 그 비용으로 최소 비용을 계산한다.는 것이다.
그래서 바로 알 수 없는 부분은 10000으로 둬서 계산 시 어떻게 해도 큰 값이 도출되도록 설정한 것이다.
모든 계산은
D[x,y]와D[x, node] + D[node, y]의 값을 비교하여 최솟값을 넣어주는 것이다.
다시 코드로 돌아와보자.
for (int k = 1; k <= computer_num; k++) {
for (int i = 1; i <= computer_num; i++) {
for (int j = 1; j <= computer_num; j++) {
if (map[i][j] > map[i][k] + map[k][j])
map[i][j] = map[i][k] + map[k][j];
}
}
}k는 거쳐가는 노드이다. i는 출발 노드(왼쪽), j는 도착 노드(오른쪽)이다.
if (map[i][j] > map[i][k] + map[k][j])에서 map[i][j]는 D[x,y]인 것이고 map[i][k] + map[k][j]는 D[x, node] + D[node, y]인 것이다.
어차피 모든 값은 초기화시 10000으로 설정되므로 작은 값이 들어갈 수 있도록 부등호를 설정해준 것이다.
for (int i = 2; i <= computer_num; i++) {
ans += map[1][i] != 10000;
}여기서 컴퓨터 1을 거치는 노드의 갯수를 알아야 하므로 map[1][탐색하는 컴퓨터]의 값이 10000이 아니라면, 즉 1을 거쳐 다른 컴퓨터로 가는 길이 있다면 ans의 값을 증가시킨다.
사실 직관적으로 이해가 되지 않는다.
마지막 부분은 1을 거치는 컴퓨터를 찾게 한다. 만약 1과 2가 연결되어 있고 2와 5가 연결되어 있다면 1과 5가 연결되어 있다고 볼 수 있다. 여기서 D[1,5]는 D[1,2]+D[2,5]로 쪼개질 수 있다. 여기서 만약 D[1,2],D[2,5]의 길이 없다면 10000이 넘는 값이 저장되어 있을 테지만 길이 존재하면 10000 이하의 작은 값이 들어간다. 그렇게 된다면 D[2,5]을 계산한 값이 D[1,2]을 계산한 값 속으로 더해져 들어가는 것 같다.
