이번 주 내로 DFS / BFS문제를 최대한 풀어보려고 한다.
BFS의 구현은 이제 어느정도 적응했고,
특히 BFS로 최단경로를 찾는다던가, 역추적한다던가
응용도 할 수 있는 상태이다.
DFS는 그렇지 않다.
DFS의 구현은 재귀함수, Stack이 존재하는데,
재귀함수는 어느정도 가능하지만,
Stack의 경우, 어떻게 구현해야하고 경로를 어떻게 출력해야하는지
구조가 아직은 이해되지 않았다.
https://www.youtube.com/watch?v=mIf-ZqfK4EA&t=112s
모든 DFS문제를 BFS로 풀 수 있는게 다행이긴하지만,
DFS문제를 DFS로 푸는 연습을 해야만 할 것 같다.
https://www.acmicpc.net/workbook/view/1833
여러 문제들이 존재한다.
1. 4963 - DFS
DFS로 풀 수 있다면 BFS로도 풀 수 있다.
DFS로 못푸는 문제는 보통 범위가 큰 경우이다.
BFS문제라고 앞으로 굳이 써넣지 않으려고 한다
https://www.acmicpc.net/problem/4963
시도
#include <iostream>
#include <cstring>
using namespace std;
int dirX[8]{-1, -1, -1, 0, 1, 1, 1, 0};
int dirY[8]{1, 0, -1, -1, -1, 0, 1, 1};
void DFS(int, int);
bool map[51][51]; //int는 너무 커서 bool로 생성
int w, h;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int count;
while (true)
{
count = 0;
cin >> w >> h;
if(!w && !h)
{
break;
}
// 맵 초기화
memset(map, 0, sizeof(map));
// 맵 저장
for (int i = 0; i < h; i++)
{
for (int k = 0; k < w; k++)
{
cin >> map[i][k];
}
}
// 계산
for (int i = 0; i < h; i++)
{
for (int k = 0; k < w; k++)
{
if (map[i][k] == 1)
{
count++;
DFS(i, k);
}
}
}
cout << count << "\n";
}
return 0;
}
void DFS(int x, int y)
{
// 현재 x,y좌표값을 0으로 만듦
map[x][y] = 0;
for(int i=0; i<8;i++)
{
if(0 <= x+dirX[i] && x+dirX[i] <w && 0 <= y+dirY[i] && y+dirY[i] < h)
{
if(map[x+dirX[i]][y+dirY[i]] == 1)
{
DFS(x+dirX[i], y+dirY[i]);
}
}
}
}0
1
3
4
5
9결과가 위처럼 나왔다.
0
1
1
3
1
9답은 위와 같다.
현재 구현한 알고리즘에선
해당 문제에서 섬이 3개라고 판단하는 오류가 난다.
왜?
디버그를 위해서 51이던 배열을 3, 2로 줄여보았는데
이 경우는 1이 정상적으로 나온다..
왜??
테스트해보니, h에 해당하는 크기 값이 여유가 남으면,
이상한 계산을 하는 것이었다.
왜??
초기화가 제대로 되지 않았나?
맵 초기화는 false로 잘 되었고,
맵을 저장하는데 2,1인덱스가 true가 되지 않았다..
왜??
세로가로 인덱스가 2 3 으로 해야만 한다
그러니까 인덱스랑 별개로 코드가 쓰레기라는 것이다.
0 0 인덱스가 가장 먼저 DFS에 들어가게 되면,
본인을 우선 0값으로 두고,
본인 주변의 1들을 DFS에 넣는다.
따라서 0 0이 들어갔다면, 본인이 0이되고,
주변의 1,0 / 0,1이 DFS에 들어가게 될 것이다.
그러면 1,0 본인도 0이되고,
주변의 0,1 / 1,1을 DFS에 넣게 될 것이다.
중복해서 0,1이 들어갔는데 예상했던 일이고,
이를 방지하기 위해서 0인 경우는 앞서서 DFS에 들어갔던 경우일 것이므로
return하고 끝낸다.
주변의 1,1 / 0,1을 DFS에 넣게 될 것이다.로 돌아와서,
(dir xy의 순서에 의해 반시계 방향으로 들어가게 됨)
1,1이 들어갔으니 당연히 1,1도 0으로,
그리곤 1,2 / 0,2 / 0,1이 DFS에 넣어지게 될 것이다.
근데 그런일은 일어나지 않았다.
왜일까?
왜 저기만?
시도 2
#include <iostream>
#include <cstring>
using namespace std;
int dirX[8]{-1, -1, -1, 0, 1, 1, 1, 0};
int dirY[8]{1, 0, -1, -1, -1, 0, 1, 1};
void DFS(int, int);
bool map[51][51]; // int는 너무 커서 bool로 생성
int w, h;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int count;
while (true)
{
count = 0;
cin >> w >> h;
if (!w && !h)
{
break;
}
// 맵 초기화
memset(map, 0, sizeof(map));
// 맵 저장
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
cin >> map[i][j];
}
}
// 계산
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (map[i][j] == 1)
{
count++;
DFS(i, j);
}
}
}
cout << count << "\n";
}
return 0;
}
void DFS(int x, int y)
{
if (map[y][x] == 0)
{
return;
}
// 현재 x,y좌표값을 0으로 만듦
map[y][x] = 0;
for (int i = 0; i < 8; i++)
{
if ((0 <= x + dirX[i]) && (x + dirX[i] < w) && (0 <= y + dirY[i]) && (y + dirY[i] < h))
{
if (map[y + dirY[i]][x + dirX[i]] == 1)
{
DFS(x + dirX[i], y + dirY[i]);
}
}
}
}y와 x를 바꿔 썼던 문제를 해결
하지만 해당 예제에서 섬은 9개가 나와야하는데
6개가 나와버렸다.
왜지?
어디가 인식되지 않는지 확인해본다.
ㅋㅋㅋㅋㅋ
위의 3개의 1이 인식되지 않았다.
왜?
이건 DFS와 상관없이, 입력에 따른 결과만 나오면 되는데..
아... 수정 완료..
해결
DFS를 구현하는 것은 쉬웠다.
Visited없이 단순히 본인을 0으로 표시하며(false)
방문함을 인식했고,
헷갈렸던 부분은 2차원 배열에서
가장 처음의 값이 세로,높이 값인데 혼용하다보니 헷갈렸다..
visited없이 dfs를 구현했다는 점에서 뿌듯했는데,
터무니없는 실수를 해서 아쉽다
2. 11725 - BFS / Segfault
https://www.acmicpc.net/problem/11725
문제는 우선 연결을 표현하고,
연결에서 본인보다 더 위에 있는 노드가 부모가 되는 것이다.
2번노드부터 N번노드까지 부모를 출력하면 되는 문제다.
트리 구조이기 때문에, 사이클이 없고, 모든 정점이 연결되어있다.
먼저 연결을 분석해 계층을 저장해두고,
다시 연결을 분석해 더 낮은계층(root는 1번계층)이라면
해당 노드가 부모가 되는 알고리즘을 구현해본다.
라고 하려고 했는데,
int형으로 해당 배열을 표현하기 위해선 많은 메모리가 들고,
connection까지도 입력을 받아야해서 보류..
시도
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// 입력값들 받기
int N;
cin >> N;
bool connection[N+1][N+1]; //1~N인덱스 담을 수 있음
int visited[N+1] = {
0,
};
memset(connection, false, sizeof(connection));
int from, to;
for (int i = 0; i < N-1; i++) //Tree라서 N-1개의 연결이 존재
{
cin >> from >> to;
connection[from][to] = 1;
connection[to][from] = 1;
}
// BFS
queue<int> childNode;
childNode.push(1);
while (!childNode.empty())
{
int parent = childNode.front();
childNode.pop();
for (int i = 1; i < N + 1; i++) //1~N 인덱스
{
if (connection[parent][i] && visited[i] == 0)
{
childNode.push(i);
visited[i] = parent;
}
}
}
for (int i = 2; i < N + 1; i++) //2~N 인덱스
{
cout << visited[i] << "\n";
}
return 0;
}
처음보는 에러가..
for문의 범위도 정확하다고 생각하고, 예제들도 맞는데 왜뜰까?
재귀함수, 동적메모리, 포인터 를 사용하지 않았으므로
배열 인덱스 초과라는 것인데..
인덱스를 다시 살펴봐도 문제될 만한 곳이 보이지 않는다..
음..
해결
#include <iostream>
#include<vector>
#include <queue>
#include <cstring>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// 입력값들 받기
int N;
cin >> N;
//bool connection[N+1][N+1]; //1~N인덱스 담을 수 있음
//memset(connection, false, sizeof(connection));
vector<int> connection[N+1];
int visited[N+1] = {0, };
int from, to;
for (int i = 0; i < N-1; i++) //Tree라서 N-1`개`의 연결이 존재
{
cin >> from;
cin >> to;
connection[from].push_back(to);
connection[to].push_back(from);
}
// BFS
queue<int> childNode;
childNode.push(1);
while (!childNode.empty())
{
int parent = childNode.front();
childNode.pop();
for(int i=0;i<connection[parent].size();i++)
{
int child = connection[parent][i];
if(!visited[child])
{
visited[child] = parent;
childNode.push(child);
}
}
}
for (int i = 2; i < N + 1; i++) //2~N 인덱스
{
cout << visited[i] << "\n";
}
return 0;
}풀이
https://www.acmicpc.net/board/view/123303
Connection을 bool인 2차원배열로 선언했었는데
100,000바이트의 제곱만큼의 크기가 사용되고,
1024로 3번 나누니 KB-MB에서 GB까지, 9GB가 나오게 된다.
vector<int> connection[N+1];바꾼 자료형은 위와 같고, int배열에 벡터가 들어가있는 형태이다.
Connection[0]에 벡터로 담고,
Connection[1]에 벡터로 담고,
...
를 반복하는 것이다.
https://luv-n-interest.tistory.com/975
벡터는 간단히 스택,가변배열을 합친 느낌이다.
벡터 자체도 배열처럼 인덱스로 접근할 수 있어서,
2차원 배열과 같은 효과를 낸다.
vector<int> arr[N+1]이라는 것은,
해당 인덱스 각각에 가변길이의 벡터가 선언되므로
의미없는 메모리를 줄일 수 있다는 것이다.
for(int i=0;i<connection[parent].size();i++)
{
int child = connection[parent][i];
if(!visited[child])
{
visited[child] = parent;
childNode.push(child);
}
}BFS에 넣는 구문도 달라졌다.
- Connection[]배열 내부의 Vector길이만큼 for문을 반복
- Vector를 인덱스로 접근하여, 순서대로 꺼내옴
값을 단순히 저장하고 수정하지 않고 참고하는 용도로 사용한다면,
무조건 벡터로 사용하는 것이 효율적으로 보인다.
특히 Connection처럼 정점의 연결정보를 저장해두는 것
(수정하더라도 중간의 값이 아닌 뒤만 수정한다면 괜찮을듯)
그렇지 않다면, 배열을 사용해야한다.
유익한 글이었습니다.