BFS DFS 경로탐색 문제 풀기
- DFS는 경로는 알 수 있지만, 최단거리인지는 불분명하고,
- BFS는 최단거리는 알 수 있지만, 경로는 불분명하다.
DFS에서 경로탐색을 하는게 좋을지 BFS에서 하는게 좋을지
1. 나이트의 이동
https://www.acmicpc.net/problem/7562
구현
- 시작점과 도착점이 주어졌을 때, 나이트의 이동으로 도착점에 가는 최단횟수
- map의 크기는 고정이므로 2차원배열도 상관없다.
- map은 bool로 생성했다. 방문했는지 표시만 하기 위함.
- queue에 역시 count를 넣어서 횟수를 파악했다.
문제점
- 각 테스트케이스 시작전에 초기화 잘해줄 것
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int N;
int s_x, s_y;
int e_x, e_y;
bool map[301][301];
int dx[8] = {2,1,-1,-2,-2,-1,1,2};
int dy[8] = {-1,-2,-2,-1,1,2,2,1};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while(T--)
{
//cout << "T : "<< T <<"\n";
cin >> N;
cin >> s_x >> s_y;
cin >> e_x >> e_y;
memset(map, 0, sizeof(map));
queue<pair<pair<int, int>, int>> q;
q.push({{s_x, s_y}, 0});
while(!q.empty())
{
int x = q.front().first.first;
int y = q.front().first.second;
int count = q.front().second;
q.pop();
if(x==e_x && y==e_y)
{
cout << count << "\n";
break;
}
for(int i=0;i<8;i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if(cx < 0 || cx >= N || cy<0 || cy>=N)
{
continue;
}
if(!map[cx][cy])
{
map[cx][cy] = 1;
q.push({{cx, cy}, count+1});
}
}
}
}
return 0;
}2. 숨바꼭질
https://www.acmicpc.net/problem/1697
- 문제를 딱 보면 DP로 풀어야할지 BFS로 풀어야할지
2가지 방식으로 풀 수 있어보인다.
2가지 다 해본다.
2-1. DP
구현
- 한번 DP를 확정해도, 다시 수정하고 수정하고 해야하는데..
문제점
1. DP로 구현할 수 없었다. 풀이를 참고해본다...
#include <iostream>
using namespace std;
int dp[100001];
int S, E;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> S >> E;
// 뒤로는 X-1로만 갈 수 있다 - 같은 경우도 제거
if (E <= S)
{
cout << S - E;
return 0;
}
for(int i=0;i<100001;i++)
{
dp[i] = 987654321;
}
// 1 S는 확정.
dp[S] = 0;
// 2 S 앞의 dp는 확정할 수 있다. (S는 제외)
for (int i = S; i >= 1; i--)
{
dp[i - 1] = dp[i] + 1;
}
// 3 S 뒤는 dp는 계산을 통해서 확정한다. (S는 제외)
for(int i=S+1;i<100001;i++)
{
dp[i] = min(dp[i - 1] + 1, dp[i + 1] + 1);
if (i % 2 == 0)
{
dp[i] = min(dp[i], dp[i / 2] + 1);
}
}
// 문제점 - dp..
for(int i=E+1; i<100001; i++)
{
dp[i-1] = min(dp[i-1], dp[i]+1);
dp[i/2] = min(dp[i/2], dp[i]-1);
}
cout << dp[E];
return 0;
}
/* 틀린 DP
dp[i+1] = min(dp[i+1], dp[i]+1);
dp[i-1] = min(dp[i-1], dp[i]+1);
dp[i*2] = min(dp[i*2], dp[i]+1);
*/해결
- 0~시작점(S) 까지의 dp는 쉽게 구할 수 있는데,
S+1~E까지의 점화식을 구하기 어려웠다.- S+1~ 인덱스는 짝수라면 dp[i]/2+1
홀수라면 dp[i]/2+2을 한다.
그 이유는 2를 곱하고 1을 더하면 해당 dp가 무조건 되기 때문.
아래의 코드를 참고그러니까 점화식을 못찾으면 DP로는 못푼다..
정방향으로 진행하는 점화식을 무조건 찾아야 함.
#include <iostream>
using namespace std;
int dp[100001];
int S, E;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> S >> E;
// 뒤로는 X-1로만 갈 수 있다 - 같은 경우도 제거
if (E <= S)
{
cout << S - E;
return 0;
}
for(int i=0;i<100001;i++)
{
dp[i] = 987654321;
}
// 1 S는 확정.
dp[S] = 0;
// 2 S 앞의 dp는 확정할 수 있다. (S는 제외)
for (int i = S; i >= 1; i--)
{
dp[i - 1] = dp[i] + 1;
}
// 3 S 뒤는 dp는 계산을 통해서 확정한다. (S는 제외)
for(int i=S+1;i<100001;i++)
{
if (i % 2 == 0)
{
dp[i] = min(dp[i/2] + 1, dp[i-1] + 1); //dp[i] = min(dp[i], dp[i / 2] + 1);
}
else
{
dp[i] = min(dp[i-1] + 1, dp[(i+1)/2] + 2);
}
}
cout << dp[E];
return 0;
}2-2. BFS
구현
- BFS는 문제 구문 그대로를 코드로 번역하면 끝이다.
- 2차원 map대신 1차원을 사용하는 것 외엔 바뀐것 X
- visited체크만 잘 하면 된다.
문제점
- 종료조건에 return문을 적지 않았다.
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int S, E;
bool map[100001];
int dx[3] = {1,-1,0};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> S >> E;
memset(map, 0, sizeof(map));
queue<pair<int, int>> q;
q.push({S, 0});
while(!q.empty())
{
int x = q.front().first;
int count = q.front().second;
q.pop();
if(x==E)
{
cout << count;
return 0;
}
for(int i=0;i<3;i++)
{
int cx = x + dx[i];
if(i==2)
{
cx = x * 2;
}
if(cx < 0 || cx > 100000)
{
continue;
}
if(!map[cx])
{
map[cx] = 1;
q.push({cx, count+1});
}
}
}
return 0;
}3. 숨바꼭질 3
https://www.acmicpc.net/problem/13549
이것도 DP, BFS로.
3-1. DP
구현
- S+1~E 까지 DP계산 부분을 수정해주면 된다.
// 3 S 뒤는 dp는 계산을 통해서 확정한다. (S는 제외)
for(int i=S+1;i<100001;i++)
{
if (i % 2 == 0)
{
dp[i] = min(dp[i/2], dp[i-1] + 1); // 2배 부분에 +1 제거
}
else
{
dp[i] = min(dp[i-1] + 1, dp[(i+1)/2] + 1); // 2배 부분에 +1 제거
}
}기존의 것과 비교
3-2. BFS
구현
- 이동에 가중치가 다른 그래프라 이문제는 BFS로 풀기 힘들다고 한다.
문제점
1. 일반적인 BFS로는 풀지 못하는 문제
- 가중치가 다르기 때문.
하지만 가능하게 한 허술한 방법이 있는데,
가중치를 우선적으로 생각할 요소부터 방문하고 queue에 넣는 것이다.- x2 가중치가 0이라 min값이므로
x2를 할 수 있다면 최소값이므로, 그냥 x2를 먼저 한다.- 그 다음은 +1과 -1인데, 둘 다 1의 값을 가진다.
하지만 -1가 우선순위가 더 높아야 한다.
그 이유는, x2 -1을 해서 찾는 경우가 더 빠르기 때문.
+1을 하는 경우는 1칸씩 가는 경우에 보통 해당해서..- 그러니까 결국 허술한 풀이라는 것이다.
풀이법 3가지
https://www.acmicpc.net/board/view/106756
https://www.acmicpc.net/board/view/38887#comment-69010
[정석적으로 푸는 방법]
1. 가중치가 있기 때문에, 다익스트라 등의 방식 사용.
2. BFS를 정말 사용하되, 가중치 0은 queue의 맨 앞에 삽입.
(혹은 deque의 앞에 삽입)
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int S, E;
bool map[100001];
int dx[3] = {0, -1, 1}; / 수정 -
/ 가장 가중치가 적은 것부터 적어야했다.
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> S >> E;
memset(map, 0, sizeof(map));
queue<pair<int, int>> q;
q.push({S, 0});
while(!q.empty())
{
int x = q.front().first;
int count = q.front().second;
q.pop();
if(x==E)
{
cout << count;
return 0;
}
for(int i=0;i<3;i++)
{
int cx = x + dx[i];
if(i==0)
{
cx = x * 2;
}
if(cx < 0 || cx > 100000)
{
continue;
}
if(!map[cx])
{
map[cx] = 1;
/ 수정 - x2를 했다면, 그냥 q에 push
if(i==0)
{
q.push({cx, count});
}
else
{
q.push({cx, count+1});
}
}
}
}
return 0;
}3-3. BFS + priority queue
자료구조도 익힐 겸, 정석대로 풀어본다.
구현
- priority_queue를 사용하여,
가중치가 작은 것부터 빼낸다.- priority_queue는 pair일 경우, first값에 따라 정렬한다.
- 내림차순으로 정렬을 하기에,
count의 값을 -1을 곱해서 넣으면 간단하게 비교함수없이 사용할 수 있다.- 그렇게 가중치가 가장 작은 값을 꺼내서 계산하고 하면 된다.
문제점
1. 아래 블로그를 참고했다.
https://velog.io/@kms9887/13549
2. visited의 체크 위치에 따라 정답이 갈린다.
https://www.acmicpc.net/board/view/126380
왜 그럴까.. 일단 스킵..
안 되면 visited의 위치를 바꾸는 것도 일단 고려해본다
그냥 이런 방법을 사용해 볼 수 도 있다
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int S, E;
bool map[100001];
int dx[3] = {1, -1, 0}; // dx[2]는 x2를 의미하려고 의미없는 0을 넣어둠
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> S >> E;
memset(map, 0, sizeof(map));
priority_queue<pair<int, int>> q; // 시간, 좌표
q.push({0, S});
map[S] = 1;
while(!q.empty())
{
int count = -1 * q.top().first; // priority_queue의 우선순위 때문에
// -1을 곱한 값을 queue에 넣게 됨.
int x = q.top().second;
q.pop();
if(x==E)
{
cout << count;
return 0;
}
map[x] = 1; // 왜 여기서 visited를 체크 해야만 통과가 되는거지??
for(int i=0;i<3;i++)
{
int cx = x + dx[i];
if(i==2) // x2라면,
{
cx = x * 2;
}
if(cx < 0 || cx > 100000)
{
continue;
}
if(!map[cx])
{
//map[cx] = 1; // ==원래의 위치==
if(i==2) // x2라면,
{
q.push({-count, cx});
}
else
{
q.push({-(count+1), cx});
}
}
}
}
return 0;
}4. 숨바꼭질 4
https://www.acmicpc.net/problem/13913
구현
- 기존 숨바꼭질1 문제에서 경로를 출력해야 한다.
- 숨바꼭질1 문제는 가중치가 같기에 DP, BFS 모두 문제되지 않았다.
- 이전노드를 기록하는 int 배열을 하나 만든다.
- dp가 갱신되는 경우에, 현재노드의 이전노드를 저장해둔다.
dp[i] = min(dp[i/2] + 1, dp[i-1] + 1)- 위의 dp식을 풀어서 사용한다.
문제점
1. dp[(i+1)/2]+2 인 경우에, before를 처리하는 방법을 고민했다.
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int dp[100001];
int before[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int S, E;
cin >> S >> E;
// 뒤로는 X-1로만 갈 수 있다 - 같은 경우도 제거
if (E <= S)
{
cout << S - E << "\n";
// 여기서도 경로를 출력, -1밖에 하지 못하므로 내림차순 출력됨
for(int i=S; i>=E; i--)
{
cout << i << " ";
}
return 0;
}
// min 연산을 위한 초기화
for(int i=0;i<100001;i++)
{
dp[i] = 987654321;
}
// 1 S 확정
dp[S] = 0;
before[S] = -1;
// 2 S 이전
for(int i=S; i>=1; i--)
{
dp[i-1] = dp[i] + 1;
before[i-1] = i;
}
// 3 S 이후 - 범위를 E까지만 잡아도 되는 것이, x2를 해봤자 E+1이기 때문
// E+1은 x2-1의 경우에만 사용되며, 마지막 조건에서 다루게 된다.
for(int i=S+1; i<=E; i++)
{
if(i%2==0)
{
if(dp[i-1]+1 <= dp[i/2]+1)
{
dp[i] = dp[i-1] + 1;
before[i] = i-1;
}
else
{
dp[i] = dp[i/2]+1;
before[i] = i/2;
}
}
else
{
if(dp[i-1]+1 <= dp[(i+1)/2] + 2)
{
dp[i] = dp[i-1]+1;
before[i] = i-1;
}
else
{
// before이 핵심
dp[i] = dp[(i+1)/2] + 2;
before[i] = i+1;
before[i+1] = (i+1)/2;
}
}
}
cout << dp[E] << "\n";
// 출력하기 위해 순서대로 넣고, stack으로 뒤집음
queue<int> q;
stack<int> rev;
q.push(E);
while(!q.empty())
{
int n = q.front();
if(n == -1)
{
break;
}
rev.push(n);
q.pop();
q.push(before[n]);
}
while(!rev.empty())
{
cout << rev.top() << " ";
rev.pop();
}
return 0;
}5. 다리 만들기
https://www.acmicpc.net/problem/2146
구현
- 2개 이상의 섬이 존재할 때, 2개의 섬을 잇는 가장 짧은 다리 길이를 구한다.
- 먼저 각자 몇번째 섬인지 표시해두고, 각 섬에서 출발하여 다른 섬에 가면
멈추는 BFS를 구현해본다.
문제점
1. memcpy 오류
왜 coast c가 존재하는데 empty라고 뜨는 걸까?
= memcpy구문이 이상하게 실행되는지 뒤의 코드마저 실행되지 않았다.
따라서 for문으로 그냥 직접 대입했다.
2. Segfault 오류
코드 블럭마다 주석처리를 해가며 어디서 발생하는지 체크했다.
DFS부분에서 발생했고, count의 개수가 섬을 의미하는데,
100이라고 너무 간단히 적어놓았다. 100x100에선 더 많다.// 1 Segfault - 섬의 개수는 매우 많을 수 있다 queue<pair<pair<int, int>, int>> coast[100000];
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int N;
int result = 987654321;
int map[101][101];
int t_map[101][101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
bool visited[101][101];
bool t_visited[100][100];
// 1 Segfault - 섬의 개수는 매우 많을 수 있다
queue<pair<pair<int, int>, int>> coast[100000];
int count = 1; // 섬의 인덱스
void DFS(int x, int y)
{
map[x][y] = count; // 섬의 인덱스를 붙임
for (int i = 0; i < 4; i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if (cx < 0 || cx >= N || cy < 0 || cy >= N)
{
continue;
}
// 상하좌우에 0이 존재하면, coast큐에 원점을 넣는다.
// 중복이 들어갈 수 있지만, 그냥 하는 것보단 시간 단축될 듯..
if (map[cx][cy] == 0)
{
coast[count].push({{x, y}, 0});
}
if (map[cx][cy] == 1 && !visited[cx][cy])
{
visited[cx][cy] = 1;
DFS(cx, cy);
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
// 1 입력 그대로 받기
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> map[i][j];
}
}
// 2 입력을 DFS를 통해 섬의 인덱스를 붙여서 Map을 수정
// 2-1. DFS를 통해 섬 마다 해얀가의 위치를 시작점으로서 큐에 담음.
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (map[i][j] == 1 && !visited[i][j])
{
visited[i][j] = 1;
DFS(i, j);
count++;
}
}
}
// 3 각 섬의 시작점으로부터 다른 섬에 방문시 length를 수정하는 BFS
for (int c = 1; c < count; c++)
{
// visited를 t_visited로 복사 (memcpy를 사용했더니 while문이 동작하지 않음 왜?)
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
t_visited[i][j] = visited[i][j];
}
}
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
t_map[i][j] = map[i][j];
}
}
while (!coast[c].empty())
{
int x = coast[c].front().first.first;
int y = coast[c].front().first.second;
int length = coast[c].front().second;
coast[c].pop();
for (int i = 0; i < 4; i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if (cx < 0 || cx >= N || cy < 0 || cy >= N)
{
continue;
}
if (c != t_map[cx][cy] && t_map[cx][cy] > 0)
{
result = min(result, length);
//cout << "\n"<< c << " -> " << t_map[cx][cy] << "\n" << cx << " : " << cy << " = " << length;
}
if (t_map[cx][cy] == 0 && !t_visited[cx][cy])
{
t_visited[cx][cy] = 1;
t_map[cx][cy] = -1;
coast[c].push({{cx, cy}, length + 1});
}
}
}
}
cout << result;
}
Time Waits for No One