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인 경우는 없다는 뜻이다.

-> 이러한 내용일 경우 방향이 있다는 것을 생각해보아야 한다.