ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 11403.경로찾기
    알고리즘/백준 BAEK JOON 2020. 3. 16. 23:19

    이번에 풀어볼 문제는 백준의 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인 경우는 없다는 뜻이다.

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

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    4949.균형잡힌 세상  (0) 2020.04.06
    1874.스택 수열  (0) 2020.04.02
    11403.경로찾기  (0) 2020.03.16
    2178. 미로탐색  (0) 2020.03.15
    1260. DFS와 BFS ( Stack & Queue 사용 )  (0) 2020.03.10
    [백준] 퇴사 14501  (0) 2019.04.18

    댓글 0

Designed by Tistory.