백준(BOJ) [백준] 11403번 경로 찾기 C++ - 반응형 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 분류 그래프 탐색(깊이 우선 탐색: DFS) 해설 #include <iostream> #include <queue> using namespace std; int main() { int N; cin >> N; int** G = new int* [N]; // 연결 그래프 배열 int** result = new int* [N]; // 출력 그래프 배열 for (int i = 0; i < N; i++) { G[i] = new int[N]; result[i] = new int[N]; for (int j = 0; j < N; j++) { cin >> G[i][j]; result[i][j] = 0; } } // DFS 알고리즘 for (int i = 0; i < N; i++) { queue<int> q; // q에는 다음 탐색할 배열의 인덱스를 저장 bool* visit = new bool[N]; // visit은 무한 반복을 제어하기 위해 방문한 곳을 저장 for (int j = 0; j < N; j++) { visit[j] = 0; if (G[i][j] == 1) q.push(j); } // 위 for문에서 visit 배열을 초기화하며 i번째 배열에서 방문할 곳이 있 while (!q.empty()) { int iter = q.front(); q.pop(); // iter: 방문할 인덱스 if (visit[iter] == 0) { visit[iter] = 1; for (int j = 0; j < N; j++) { if (visit[j] == 0 && G[iter][j] == 1) q.push(j); } // 방문하지 않은 곳에 다음 방문할 곳을 찾으면 q에 넣어준다 } } for (int j = 0; j < N; j++) { result[i][j] = visit[j]; // visit 1차원 배열을 result 2차원 배열의 각 행에 저장 } delete visit; // 정답코드 관계x } // 출력 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cout << result[i][j] << " "; cout << "\n"; } // 정답 관계 x delete[] result; delete[] G; } DFS를 이용한 그래프 탐색 문제입니다 DFS의 특성을 생각하여 필요한 조건들만 작성해주면쉽게 풀리는 문제였습니다저는 출력 그래프를 따로 만들지 않고 작성하다 헤맸는데출력 그래프를 따로 추가하여 코드를 작성하니해결되었습니다 반응형 공유하기 게시글 관리 구독하기CuriHuS Blog 저작자표시 비영리 동일조건 '백준(BOJ)' 카테고리의 다른 글 [백준] 30022번 행사 준비 C++ (0) 2023.09.30 [백준] 30024번 옥수수밭 C++ (0) 2023.09.29 [백준] 21736번 헌내기는 친구가 필요해 C++ (0) 2023.06.30 [백준] 1932번 정수 삼각형 C++ (0) 2023.06.29 [백준] 14940번 쉬운 최단거리 C++ (0) 2023.06.27 Contents 당신이 좋아할만한 콘텐츠 [백준] 30022번 행사 준비 C++ 2023.09.30 [백준] 30024번 옥수수밭 C++ 2023.09.29 [백준] 21736번 헌내기는 친구가 필요해 C++ 2023.06.30 [백준] 1932번 정수 삼각형 C++ 2023.06.29 댓글 0 + 이전 댓글 더보기