프로그래머스 문제를 풀고 이문제를 푸니 너무 쉽게 느껴졌다 알고리즘 수련이 아주 부족하다고 느껴졌다 더 열심히 해서 제발 취업을 애햐하는데 이문제의 경우는 문제의 답으로 최소경로수를 원하는 것이기 때문에 최소 경우의 수를 확정적으로 반환해주는 BFS를 사용해주어야 한다 이문제 자체는 실버 1이지만 문제도 짧고 해서 이해하기가 매우 편했다. 이 문제의 경우 bfs를 총 3가지 경우로 짜주면 그냥 해결되는 문제열다 X-1 ,X+1 ,2*X 자기 자신에대해서 자식이 이렇게
만들어지기 떄문에 bfs의 범위를 이렇게 3개씩 넓혀주면 빠르게 끝난다.
BFS의 특징으로는 큐를 사용하면 매우 편해진다는 장점이 있다 이문제의 경우도 마찬가지다 큐를 사용해서 자기를 없애면서 자기자식은 큐에 넣게되면 BFS가 된다 이전 문제에서도 큐를 이용해서 풀었기 때문에 이번문제도 큐를 이요했지만 이번에는 visited 배열에 자기가 몇대손인지를 넣을 수 있게 코드를 짜보았다
#include <iostream>
#include <queue>
using namespace std;
int visited[200002];
int N, K;
int main() {
cin >> N >> K;
queue<int> hs;
hs.push(N);
visited[N] = 0;
while (true) {
if (hs.front() == K) {
break;
}
if (hs.front() > 0) {
if (!visited[hs.front() - 1]) {
hs.push(hs.front() - 1);
visited[hs.front() - 1] = visited[hs.front()] + 1;
}
}
if (hs.front() < 100000) {
if (!visited[hs.front() + 1]) {
hs.push(hs.front() + 1);
visited[hs.front() + 1] = visited[hs.front()] + 1;
}
}
if (hs.front() <= 50000) {
if (!visited[hs.front() * 2]) {
hs.push(hs.front() * 2);
visited[hs.front() * 2] = visited[hs.front()] + 1;
}
}
hs.pop();
}
cout << visited[K];
}
이문제의 경우도 DFS의 개념을 알기에는 좋은 문제였다 DFS의 경우 자신과 연결된 자식들중 하나에게로 간다음 계속 쭉 갔다가 자신의 부모로 돌아오는 게 핵심이다 DFS의 자식들이 오름차순으로 정렬 되어 있을수도 있고 내림차순으로 정렬 되어있을 수도 있다. 이전 문제는 오름차순으로 정렬해놓고 시작했다면 이번 문제에서는 내림차순으로 정렬하여 큰수 부터 방문하도록 하였다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> vertex[100001];
int visited[100001];
int visitedRank[100001];
int countnum=0;
void dfs(int start) {
if (visited[start] == false) {
visited[start] = true;
countnum += 1;
visitedRank[start] = countnum;
int sizeofvertex = vertex[start].size();
for (int i = 0; i < sizeofvertex; i++) {
if (visited[vertex[start][i]] == false) {
dfs(vertex[start][i]);
}
}
}
}
int main() {
int vertexnum, edgenum, startvertex;
cin >> vertexnum >> edgenum >> startvertex;
for (int i = 1; i <= edgenum; i++) {
int temp1,temp2;
cin >> temp1>>temp2;
vertex[temp2].push_back(temp1);
vertex[temp1].push_back(temp2);
}
for (int i = 1; i <= vertexnum; i++) {
sort(vertex[i].rbegin(), vertex[i].rend());
}
dfs(startvertex);
for (int i = 1; i <= vertexnum; i++) {
cout << visitedRank[i] << '\n';
}
}
자 코드를 한번 보자
내가 dfs에서 가장 좋아하는 방법은 vector로 선언하여 입력 받은 값들을 차례로 서로의 정점 번호를 index로 하는 vector에 서로서로를 넣는 방식이다
for (int i = 1; i <= edgenum; i++) {
int temp1,temp2;
cin >> temp1>>temp2;
vertex[temp2].push_back(temp1);
vertex[temp1].push_back(temp2);
}
그래서 이부분의 코드가 이렇게 되는 것이다 입력을 받았으면 지금 두정점이 연결된것이기 때문에 자기로 부터 연결되는 vector를 모두 넣어야하기 때문에 1-2 이렇게 연결되어있다면 2번 vertex 에는 1을 1번 vertex에는 2를 넣어 준다 그후 코드는 vector를 내림차순으로 정렬해준것이다 원래 벡터를 오름 차순으로 정렬할때는 vertex.begin과 vertex.end를 쓰지만 내림차순으로 정렬할 때는 rbegin과 rend를 써주면 내림 차순으로 정렬 한다
void dfs(int start) {
if (visited[start] == false) {
visited[start] = true;
countnum += 1;
visitedRank[start] = countnum;
int sizeofvertex = vertex[start].size();
for (int i = 0; i < sizeofvertex; i++) {
if (visited[vertex[start][i]] == false) {
dfs(vertex[start][i]);
}
}
}
}
그후 dfs코드는 이전에 첨부한 다른 문제와 비슷하다 일단 내가 방분하려고 하는 점이 방문된적이 없다면 그점을 방문했다고 true로 마크하고 방문한 번째수를 1증가시키고 해당정점의 등수를visitedRank에 표시해준다 그다음 그정점의 자식들 즉 vector에 있는 값들을 순회하면서 방문하지 않았던 좌표에 방문 한다.
이 문제의 경우 쉽다 dfs 는 자기 자식으로 쭉내려가기 때문에 일단 자기 자식들중 방문하지 않은 자식있으면 재귀로 쭉쭉내려간다 갈 수 없는곳을 만나면 자기 부모로 돌아가 갈 수 있는 곳을 다시 탐색하는걸 반복한다 그렇기 때문에 일단 재귀로 콜한다음 자기자식이 방문했는지 아닌지 검사하고 방문했으면 conitnue 문을 통해 방문을 건너뛴다 재귀기 때문에 갈곳이 없어 리턴되면 자기자신의 부모가 갈곳을 탐색한다
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> vertex[200001];
int visitednum[100001];
bool visited[100001] = { false, };
int countnum = 0;
void dfs(int start) {
countnum += 1;
visitednum[start] = countnum;
visited[start] = 1;
for (int i = 0; i < vertex[start].size(); i++) {
if (visited[vertex[start][i]] == true) {
continue;
}
dfs(vertex[start][i]);
}
}
int main() {
int vertexnum, edgenum, startvertex;
cin >> vertexnum >> edgenum >> startvertex;
for (int i = 1; i <= edgenum; i++) {
int temp1 = 0;
int temp2 = 0;
cin >> temp1 >> temp2;
vertex[temp1].push_back(temp2);
vertex[temp2].push_back(temp1);
}
for (int i = 1; i <= vertexnum; i++) {
sort(vertex[i].begin(), vertex[i].end());
}
dfs(startvertex);
for (int i = 1; i <= vertexnum; i++) {
cout << visitednum[i]<<'\n';
}
}
일단 위에 코드를 보게되면 visitednum이라는 것이 존재 한다 visitednum은 i번째가 루트로부터 몇번째에 갈 수 있는지를 visitednum[i] 에 저장 해준다 이것을 이용해 후에 답을 출력할 것이다. 개인적으로 배열을 써야하는 알고리즘 문제들은 visualstudio에서 stack 사이즈 문제로 오류를 엄청 띄우기 때문에 거의 전역으로 설정 해주는게 좋다. 뭐 다음 코드는 이전글에 있는 DFS BFS 알고리즘 문제에 있는 방식과 똑같다 나랑연결되 있는애들을 나의 vertex에 넣어 준다.
예시로 백준에 input값을 보자
5 5 1
1 4
1 2
2 3
2 4
3 4
이런식으로 입력을 받아오면
vertex[1]에는 4,2
vertex[2]에는 1,3,4
vertex[3]에는 2,4
vertex[4]에는 1,2,3
이 들어가게 된다 DFS에서의 간선은 양방향으로 갈수 있기때문에 양쪽에 값을 넣어 준 것 이다. 그 이후에 이 vector를 오름차 순으로 정렬해주고 나와 연결된애에게로 간다 지금 상황에선 2부터 쭉가서 끝까지 간다 쭉가다가 더 이상 갈 수 없으면 재귀함수는 return으로 자기 caller에게 돌아가기 때문에 자기 부모로 돌아가게된다 그후 부모도 다른 곳으로 갈 수 있는 지 없는지 판단하고 자기자신의 부모로 간다 이렇게 반복되어 DFS가 완성된다
이 코드가 자기자신과 인접한 4방향중 아직 방문하지 않은 곳으로 가서 자기 자식임을 표시한다 표시방법은 나의 단계에서 1을 더해주는 방식으로 작성 하였다 또한 나의 자식들도 큐의 삽입함으로서 계속해서 자손들을 확인한다.
즉 극단적인 위의 표로 봤을때 큐의 값은 (0,0)->(0,1)(1,1)(1,0)->(0,2)(2,1)(2,2)(1,2)(0,0)->..... 이런식으로 큐의 값이 변화하게 된다. 그후 맨마지막에 도착지점이 몇번째인지 마크되어있을테니 이것을 그대로 출력해주면 된다.
DFS
DFS방식으로는 이문제를 풀 수 없다 백트래킹을 사용하지 않고서는 DFS는 도착지점에 도착하는 순간 끝나기 때문에 백트래킹을 사용하여 이전지점으로가 다른 루트를 찾아가는 방법을 사용하지만 이문제에서는 시간초과를 발생시킨다. 이에
DFS방식으로 푸는것을 추천하지 않는다
#include <iostream>
#include <utility>
#include <stack>
using namespace std;
char maze[101][101] = { '0',};
bool visited[100][100] = { false, };
int N = 0, M = 0;
int minnum = 10001;
stack<pair<int, int>> visitedvertex;
void dfs(int startx, int starty) {
visited[startx][starty] = true;
visitedvertex.push({ startx,starty });
if (startx == N-1 && starty == M - 1) {
if (visitedvertex.size() < minnum) {
minnum = visitedvertex.size();
}
}
else{
if (maze[startx][starty + 1] == '1' && visited[startx][starty + 1] == false) {
starty += 1;
dfs(startx, starty);
starty -= 1;
}
if (maze[startx + 1][starty] == '1' && visited[startx + 1][starty] == false) {
startx += 1;
dfs(startx, starty);
startx -= 1;
}
if (maze[startx - 1][starty] == '1' && visited[startx - 1][starty] == false) {
startx -= 1;
dfs(startx, starty);
startx += 1;
}
if (maze[startx][starty - 1] == '1' && visited[startx][starty - 1] == false) {
starty -= 1;
dfs(startx, starty);
starty += 1;
}
}
visited[startx][starty] = false;
visitedvertex.pop();
}
int main() {
int startx = 0, starty = 0;
cin >> N >> M;
for (int i = 0; i < N; i ++) {
cin >> maze[i];
}
dfs(0, 0);
cout << minnum;
DFS방식은 재귀를 사용하여야 한다 이에 재귀를 사용하면서 스택을 섞어서 사용하였다 자신이 방문할때 스택에다가 값을 쌓아올린다. 이후 도착점에 도착했을 때 도착한 최솟값과 비교하여 작은값을 저장하여 DFS로 갈 수 있는 방법중 최솟값을 출력하는게 내가 한방법이다 DFS는 일단 불러지는 순간 자기자신을 스택에 쌓는다 그후 자신의 4방향을 탐색하여 방문한적이 없으면 쌓는다 하지만 방문할곳이 없으면 다시 스택에서 나온다 이것을 반복하여 방문한곳을 방문하지 않고 끝점 까지 도달하는 경우의 수들중 최소의 점만을 거쳐서 도착하는 값을 출력한다
이문제의 경우 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS)의 차이를 알기에는 딱인 문제 였다.
일단 BFS의 경우 재귀함수를 사용하지 않고 풀어 보았다
현재 이렇게 입력값을 주었을 경우 BFS는 기준점을 기준으로 선 1개를 통해 연결 된 애들 선 2개를 통해 연결된 애들
이런식으로 단계를 나눠준다
이렇게 생각을 하거나 아니면
DFS의 경우에는 또 다르게 생각해주어야한다 비슷하게 생각해보자면 최대한 길게 선을 그어서 모든 정점을 방문하는 방법이라고 생각한다 단 다시 되돌아가기는 내가 왔던 점으로만 돌아 갈수 있다 또한 만약에 이때 다른 경로가 아직 방문되지 않았고 내가 간적 없는 정점이라면 그곳으로 간다. 즉 최대한 길게 갈려고 한다고 생각하면 된다.
다르게 생각하면 부모를 기준으로 내 첫째 자식의 후손들 까지 갔다가 2째 자식의 후손들 까지 쭉보고 나머지 자식들 순으로 그 자식들의 후손들까지 쭉 보는거라고 생각하면된다
이런식으로 기준점을 1로 두고 1과 선 한개로 연결된 애들과 선을 2개로 해서 갈수 있는 애들을 나눠서 생각해줄수 있다
단 밑에 그림처럼 생각할시에는 2번째 단계에서 이미 4를 방문했으므로 3단계에 있는 4에는 방문을 할 필요가 없다고 생각해주면 된다.
일단 전체 코드를 첨부후 부분 부분 설명하도록 하겠다.
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<memory.h>
using namespace std;
vector <int> vertex[10002];
vector <int> resultofDfs;
vector <int> resultofBfs;
int vertexnum;
bool visited[1001] = { false, };
//dfs 함수
void dfs(int start) {
resultofDfs.push_back(start);
visited[start] = 1;
for (int i = 0; i < vertex[start].size(); i++) {
if (visited[vertex[start][i]] == true){
continue;
}
dfs(vertex[start][i]);
}
}
int main() {
queue<int> Bfsqueue;
int edgenum;
int startvertex;
int startvertexforDfs;
int inputvertex;
int inputedge;
cin >> vertexnum;
cin >> edgenum;
cin >> startvertex;
startvertexforDfs = startvertex;
resultofBfs.push_back(startvertex);
for (int i = 0; i < edgenum; i++) {
cin >> inputvertex >> inputedge;
vertex[inputvertex].push_back(inputedge);
vertex[inputedge].push_back(inputvertex);
}
//작은것부터 나와야하니까 정렬해준다
for (int i = 1; i <= edgenum; i++) {
sort(vertex[i].begin(), vertex[i].end());
}
//DFS
dfs(startvertexforDfs);
for (int i = 0; i < resultofDfs.size(); i++) {
cout << resultofDfs[i] << ' ';
}
cout << endl;
// 배열 재사용 위해 초기화
memset(visited, 0, sizeof(visited));
//BFS
visited[startvertex] = true;
for (int i = 0; i < vertexnum; i++) {
int sizeofvertex = vertex[startvertex].size();
for (int j = 0; j < sizeofvertex; j++) {
if (visited[vertex[startvertex][j]] == false) {
visited[vertex[startvertex][j]] = true;
Bfsqueue.push(vertex[startvertex][j]);
resultofBfs.push_back(vertex[startvertex][j]);
}
}
if (Bfsqueue.empty()) {
break;
}
startvertex = Bfsqueue.front();
Bfsqueue.pop();
}
for (int i = 0; i < resultofBfs.size(); i++) {
cout << resultofBfs[i] << ' ';
}
}
맨처음 각각의 정점들이 누구랑 연결되어 있는지를 vector형태로 넣어 줄 수 있도록 만들어 주었다
만약
이런 식으로 입력받아지면
vector[1] 에 2,3,4
vecotr[2] 에 1,4
vector[3] 에 1,4
가 들어가게 된다 즉 내가 다른 누군가와 연결되었는지를 입력해주게 된다
그다음 각 정점이 방문되었는지를 확인해주는 visited 배열을 만들어 주었다
void dfs(int start) {
resultofDfs.push_back(start);
visited[start] = 1;
for (int i = 0; i < vertex[start].size(); i++) {
if (visited[vertex[start][i]] == true){
continue;
}
dfs(vertex[start][i]);
}
}
이 부분의 경우
일단 내가 들어온 곳을 방문 했다고 마크 한다
그후 for문 첫번째 조건에서 내가 아무하고 도 연결안되어있으면 for문을 돌지 않는다 그래서 더이상 가지않고 함수를
return하고 재귀적으로 call하기 이전의 함수가 다시 경로를 찾는다.
혹은 내가 만약에 방문할 수 있는 경로가 있더라도 그곳이 방문됬었다면 방문하지 않고 다른 경로를 찾는다.
BFS의 코드는 재귀가 아니라 반복문으로 작성하였다.
visited[startvertex] = true;
for (int i = 0; i < vertexnum; i++) {
int sizeofvertex = vertex[startvertex].size();
for (int j = 0; j < sizeofvertex; j++) {
if (visited[vertex[startvertex][j]] == false) {
visited[vertex[startvertex][j]] = true;
Bfsqueue.push(vertex[startvertex][j]);
resultofBfs.push_back(vertex[startvertex][j]);
}
}
if (Bfsqueue.empty()) {
break;
}
startvertex = Bfsqueue.front();
Bfsqueue.pop();
}
이 부분의 경우 일단 시작점은 무조건 방문한거니 true로 마크해준다
그 이후에 나랑 연결된 애들중에 방문되지 않은애들을 큐에다가 넣어 준다 resultofBFS 는 큐는 pop을 이용해서 정보를 빼고 더하기 때문에 vector에다가 방문하는 지점을 저장해주기 위해 만들어 놓은것이다 큐에 있는 것들을 pop해주면서 pop되는 애들의 자식들도 queue에다가 넣어준다 이것을 반복해서 같은대의 자식들이 계속 큐에 넣어져서 접근한다 이후에 큐가 비게되면 모두 방문한거가 된다 순서를 보자면
5 5 3
5 4
5 2
1 2
3 4
3 1
처음 큐 3-> 1,4->2-5이런식으로 root로 부터 몇개의 선으로 갈수 있는지에 따라 level이 나누어 진다
