[BOJ] 11403 경로찾기 C++ 문제풀이 & 소스코드

INFO

난이도 : SILVER1

유형 : DFS Graph

https://www.acmicpc.net/problem/11403

---

SOLVE

문제에서 주어진 조건을 그대로 그래프 형태로 구현하면 되는 문제이다. 

항상 이러한 그래프 구현 문제는 문제 조건을 잘 읽어야 한다. 

11403 경로찾기 문제는 "가중치가 없는" "방향 그래프" 임에 유의하여 로직을 구현해야한다. 

 

방향 그래프임에 유의하여 입력값이 1인 경우에만 인접 리스트에 노드를 추가한다. 

    int line;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> line;
            if (line == 1) {
                adj_list[i].push_back(j);
            }
        }
    }

 

다음으로 노드의 개수(n)만큼 반복하여 i번째 노드와 연결된 모든 노드와의 dfs 탐색을 수행하여 vistit 배열을 초기화한다. 

1번 노드를 예시로 들어보면 1번노드에서 2번, 3번 노드와 연결된 경로가 존재하기에 visit 배열은 모두 1로 셋팅된다. 

vector<int> adj_list[101]; // 인접리스트
int isVisit[101]; // 방문여부 표시

void dfs(int u) {
    for (int i = 0; i < adj_list[u].size(); i++) {
        if (!isVisit[adj_list[u][i]]) {
            isVisit[adj_list[u][i]] = 1;
            dfs(adj_list[u][i]);
        }
    }
}

    for (int i = 0; i < n; i++) {
        // i번째 노드와 연결된 모드 노드와의 dfs 탐색 수행
        // 차례로 모든 노드를 방문하며 i번째 노드와 연결된 모든 노드의 값을 1로 출력한다.
        memset(isVisit, 0, sizeof(isVisit));
        dfs(i);
        for (int j = 0; j < n; j++) {
            cout << isVisit[j] << " ";
        }
        cout << '\n';
    }

---

CODE

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> adj_list[101]; // 인접리스트
int isVisit[101]; // 방문여부 표시

void dfs(int u) {
    for (int i = 0; i < adj_list[u].size(); i++) {
        if (!isVisit[adj_list[u][i]]) {
            isVisit[adj_list[u][i]] = 1;
            dfs(adj_list[u][i]);
        }
    }
}

int main() {
    
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    int n;
    cin >> n;

    int line;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> line;
            if (line == 1) {
                adj_list[i].push_back(j);
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        // i번째 노드와 연결된 모드 노드와의 dfs 탐색 수행
        // 차례로 모든 노드를 방문하며 i번째 노드와 연결된 모든 노드의 값을 1로 출력한다.
        memset(isVisit, 0, sizeof(isVisit));
        dfs(i);
        for (int j = 0; j < n; j++) {
            cout << isVisit[j] << " ";
        }
        cout << '\n';
    }
    
}