11403.경로찾기
이번에 풀어볼 문제는 백준의 11403 경로찾기이다.
문제를 이해하는게 어려웠던거 같다. 크흠... 이해력을 기르자!!
해당 문제는 정점이 갈 수 있는 경로를 물어보는 문제였다.
정점과 연결된 간선에는 방향이 존재했다는 것이 바로 이 문제의 포인트다!
< Code 설명 >
#include <iostream>
#include <stack>
#include <string.h>
#define MAX 101 // 주의 -> 나는 배열을 0이 아닌 1부터 적용했다. 그러므로 101
using namespace std;
int n; // 정점의 수
int arr[MAX][MAX]; // Map
bool check[MAX]; // 방문확인
void dfs(int a){
stack <int>s;
s.push(a); // n번째 줄 내용
int v = s.top(); // 해당 스택의 상단값을 이용하기 위한 변수
while(!s.empty()){
for(int i=1; i<=n; i++){
if(check[i]==false && arr[v][i]==1){ // 미방문 && 경로가 있다면!
check[i]=true; // 방문 체크
s.push(i); // 방문한 것은 스택에 넣고
v = s.top(); // 해당 스택 내용을 기준으로 탐색하기 위해 v에 저장
// 이 때 시작정점 방문으로 check하면 안된다.
// 이유는? -> 아래 글 참조
i=0; // 위의 스택에 넣은 정점과 연결된 선이 있는지 검색해야하며
// 다시 for문이 돌면 1이 되므로 0을 넣어준다.
// 우리가 만든 배열은 0이 아닌 1번째부터 값이 있다는 걸 고려함
}
}
if(check[v]==true){ // 방문한적이 있으면서
if(!s.empty()){ // 스택이 비어있지 않다면 해당 정점 관련 탐색을 마쳤다는 의미
s.pop(); // 이전 정점에서 또다른 경로가 있나 확인하기 위해 pop 진행
if(!s.empty()) // pop해도 스택이 비어있지 않다면
// (스택이 비었는데 pop하면 에러발생)
v=s.top(); // 스택 최상위 값을 이용하기 위해 v에 저장
}
}
else if(check[v]==false){ // 방문한적이 없지만
if(!s.empty()){ // 스택은 더이상 비어있지 않고
if(v==a) // 최상위 스택값이 시작정점이라면
s.pop(); // pop을 진행한다.
// 이 부분이 없으면 시작 정점이 최상위일때 무한루프 발생
}
}
}
}
void init(){ // 한 줄씩 탐색 후 출력하므로 check값 초기화!
memset(check,false,MAX);
}
void showme(){
for(int i=1; i<=n; i++){
if(check[i]==true) // 방문한적이 있는 경우만 "1"을 출력
cout << "1 ";
else
cout << "0 "; // 미방문일 경우 "0"
}
cout << endl;
}
int main() {
cin >> n;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
scanf("%1d",&arr[i][j]);
}
}
for(int i=1; i<=n; i++){ // 초기화 -> 탐색 -> 출력 진행
init();
dfs(i);
showme();
}
return 0;
}
# 시작 정점을 방문으로 Check하면 안되는 이유!!
이 부분을 아무생각 없이 구현했다가 시간을 소비했다.
첫 정점을 Stack에 push할 때 해당 정점을 방문으로 check하면 안된다.
그 이유는 문제를 이해했다면 당연한 것이다. 해당 문제는 정점을 옮겨가는데 방향이 존재한다.
문제를 그림으로 나타내면 더 쉽게 이해할 수 있는데 출력결과는 정점을 방문한 것에 대한 문제가
아니라 정점으로 가는 길이 존재하느냐가 문제가 요구하는 정답이기 때문이다.
< 예제 입력 2번 >
해당 문제 예제2번을 그림으로 아래와 같이 그려보았다.
< 예제 입력 2번 그림>
예를 들어 2번째 라인을 dfs한다고 가정해보자. 2 -> 7 -> 3 순으로 진행될 것이다.
하지만 만약 아무생각없이 그저 기준이된 정점을 방문했다고 check하게되면
실제로는 2번이 갈 수 있는 경로는 7과3뿐인데 자기자신인 2번 또한 방문으로 check될 것이다.
자기자신으로 돌아가는 경로가 존재하는 경우도 있다.(첫 번째 라인의 경우 1이 자기자신으로 돌아올 수 있는 경로가 존재)
떄문에 기준 정점으로 되돌아오는 길이 없는데 무작정 시작 정점을 방문으로 check하게되면 전혀 다른 결과가 나온다.
-> 결론! 아무생각 없이 dfs라고 해서 무작정 똑같이 구현하지말고 예외를 생각하자!
반드시 알아야할 TIP!!
-> 역시나 예외처리를 하는 능력이 가장 중요하다.
-> 문제 구현 난이도는 어렵지 않았으나 문제 이해를 못했다
# i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다.
-> 이러한 내용일 경우 방향이 있다는 것을 생각해보아야 한다.