경로탐색(DFS)
역시나 오랜만에..진짜 최근 모든 글들 시작이 오랜만에 업로드..인것같다 ㅎㅎ..
최근에 휴가를 나갔었고 아마 마지막 휴가였을것이다.. 이제 약 4개월정도 남았고, 얼른 전역을 해야하는 시점이 왔다..
정말 자대에 온지가 엊그제같고, 불타는 학구열(?)로 열심히 코딩을 해야겠다는 생각이 짙었었는데 역시 쉽지 않았다.. 그나마 남은 4개월만이라도 열심히 해볼 예정이다..
우선 경로탐색이다.
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성해야한다.
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 N가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.
우선 계속해서 비슷한 알고리즘, 메카니즘의 문제이다. 지금까지 해왔던 DFS와 접근이 비슷하고, 내가 찾고자하는 정답을 if문에, 그렇지 않은 것을 else에 짱박고 왼쪽, 그리고 오른쪽 자식을 통해서 얻고자 하는 정답에 점점 가까워지면 된다.
정말 기본중의 기본문제.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int map[21][21]={0,}, ch[10]={0,};
//ch배열을 만들어줌으로써 내가 한번 갔었던 경로를 기억해야 한다.
int M, N, cnt=0;
void DFS(int v){
if(v==N){
cnt++;
return;
}
else{
for(int i=1; i<=N; i++){
if(map[v][i]==1 && ch[i]==0){
//맵에 길이 있고, ch배열도 0일 경우 갈 수 있음
ch[i]=1;
DFS(i);
ch[i]=0;
//ㄴ요놈들이 핵심!
}
}
}
}
int main(){
int a, b;
cin>>N;
cin>>M;
for(int i=1; i<=M; i++){
cin>>a;
cin>>b;
map[a][b]=1;
}
ch[1] = 1;
DFS(1);
cout<<cnt;
}이번에는 위 문제보다 살짝 심화된 문젠데, 진짜 개 바보같은 짓 때문에 어제 분명히 다 풀어놓고도 답이 이상하게 나와서 오늘까지 계속 해맸다..
우선 문제는
이거다.. 이거 또한 map 이중배열과 ch배열을 만들어서, 길이 뚫려있는 곳과 내가 지났던 곳을 체크해주는 ch배열을 만들어주고, 동서남북을 확인해주면서 탐색해주면 된다.
근데 진짜..main 함수쪽에 cin을 두번 받아주는 바람에 자꾸 이상한 몇만이 답으로 떠서.. 하아...
아무튼 어렵진 않은 문제였다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int map[8][8]={0,}, ch[8][8]={0,};
int cnt=0;
void DFS(int a, int b){
if(a==7 && b ==7){
cnt++;
return;
}
else{
if(map[a+1][b]==0 && ch[a+1][b]==0){
ch[a+1][b]=2;
DFS(a+1, b);
ch[a+1][b]=0;
}
if(map[a][b+1]==0 && ch[a][b+1]==0){
ch[a][b+1]=2;
DFS(a, b+1);
ch[a][b+1]=0;
}
if(map[a-1][b]==0 && ch[a-1][b]==0){
ch[a-1][b]=2;
DFS(a-1, b);
ch[a-1][b]=0;
}
if(map[a][b-1]==0 && ch[a][b-1]==0){
ch[a][b-1]=2;
DFS(a, b-1);
ch[a][b-1]=0;
}
}
}
int main(){
for(int i=1; i<=7; i++){
for(int j=1; j<=7; j++){
cin>>map[i][j];
//cin>>ch[i][j];
//하아.. 이부분 때문에 진짜 개고생.. 진짜 난 바보새끼..
}
}
for(int i=1; i<=7; i++){
map[0][i] = 1;
map[i][0] = 1;
ch[0][i] = 1;
ch[i][0] = 1;
}
ch[1][1] = 2;//한번 지나간 길은 2
DFS(1, 1);
cout<<cnt;
}그리고 밑의 코드는 위 코드를 조금 더 깔끔하게 정리한 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int map[8][8]={0,}, ch[8][8]={0,};
int cnt=0;
int dir_a[5] = {0, 1, 0, -1}, dir_b[5] = {1, 0, -1, 0};
void DFS(int a, int b){
int xx, yy;
if(a==7 && b ==7){
cnt++;
return;
}
else{
for(int i=0; i<4; i++){
xx = a + dir_a[i];
yy = b + dir_b[i];
if(xx<1 || xx>7 || yy<1 || yy>7) continue;
if(map[xx][yy]==0 && ch[xx][yy]==0){
ch[xx][yy]=1;
DFS(xx, yy);
ch[xx][yy]=0;
}
}
}
}
int main(){
for(int i=1; i<=7; i++){
for(int j=1; j<=7; j++){
cin>>map[i][j];
cin>>ch[i][j];
}
}
ch[1][1] = 1;//한번 지나간 길은 2
DFS(1, 1);
cout<<cnt;
}