인프런 커뮤니티 질문&답변
작성한 질문수
2주차 개념 #4-2. 인접행렬 질문있습니다.
작성
·
40
·
수정됨
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
#include <bits/stdc++.h>
using namespace std;
const int V = 10;
bool adj[V][V];
bool visited[V];
void go(int from) {
visited[from]=1;
cout << from << " ";
for(int i=0;i<V; i++) {
if(visited[i]) continue; //이미 방문된건지 확인
if(adj[from][i]) { //방문x라면 현재 from과 연결된 노드인지 확인
go(i);
}
}
return;
}
int main() {
adj[1][2]++; adj[1][3]++; adj[3][4]++;
adj[1][2]++; adj[1][2]++; adj[1][2]++;
for(int i=0;i<V;i++){
for(int j=0;j<V;j++)
if(adj[i][j]) {
go(i);
exit(0);
}
}
return 0;
}
main()내부 이중 for문의 역할이 재귀와 중복된다고 생각이들어 if문 성립하면 바로 exit(0) 시키고( go()한 번 호출하면 연결된 모든 노드를 재귀적으로 다 순회하기때문에 이중 for문으로 go()를 또 호출할 필요가 없다고 생각하였습니다) , main()내부의 visited()==0도 재귀 내부에서 검사하고 있기에 없어도 될 것 같다고 생각하여 지워보았습니다.
방금 말씀드린대로 코드를 수정한것이 제가 올려둔 코드인데, 이렇게 해도 출력이 1,2,3,4가 나오는거보면 정상적으로 순회가 되는듯한데 , 혹시 연결된 컴포넌트 하나만 순회하는게아니라 모든 연결된 컴포넌트를 방문해야하는건가요??
Q1. main() 내부의 visited[j]==0 이 꼭 필요한 이유,
Q2. 그리고 main()에서 go()한 번 호출후에 exit(0) 시키지않고 계속해서 go()를 더 호출하도록 코드를 짜는 이유가 궁금합니다.
답변 2
0
안녕하세요 재윤님 ㅎㅎ
지금 코드를 보면
1 -> 2
1 -> 3 -> 4
이렇게 연결되어있는 그래프로 보입니다.
네 코드를 봤을 때 모든 정점을 탐색하는 코드가 맞습니다.
#include <bits/stdc++.h>
using namespace std;
const int V = 10;
bool adj[V][V];
bool visited[V];
void go(int from) {
visited[from] = 1;
cout << from << " ";
for (int i = 0; i < V; i++) {
if (visited[i]) continue; // 이미 방문된건지 확인
if (adj[from][i]) { // 방문x라면 현재 from과 연결된 노드인지 확인
go(i);
}
}
return;
}
int main() {
adj[1][2]++;
adj[1][3]++;
adj[3][4]++;
adj[1][2]++;
adj[1][2]++;
adj[1][2]++;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (adj[i][j]) {
go(i);
exit(0);
}
}
}
return 0;
}
Q1. main() 내부의 visited[j]==0 이 꼭 필요한 이유,
-> main함수내에는 visited가 없습니다.
그리고 main()에서 go()한 번 호출후에 exit(0) 시키지않고 계속해서 go()를 더 호출하도록
-> main - go(i)의 의미는 만약 i로부터 연결된 간선이 있다면 해당 i로부터 탐색을 이어나가는 코드입니다.
만약 정점들의 집합이 그저 1 -> 2 -> 3 이렇게 단순하다면 저거 한번 호출하고 종료시켜도 되지만
1 -> 2
3 -> 4 -> 5
이렇게 된 경우에는 main함수내에서 go를 여러번 호출시켜야 모든 정점들을 탐색가능합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 재윤님.
질문해 주신 내용을 토대로 답변을 드리겠습니다.
Q1. main() 내부의 visited[j]==0 이 꼭 필요한 이유
visited[j]==0 부분은 그래프 탐색에서 중복 방문을 피하기 위한 장치입니다. 재귀적으로 탐색하는 과정에서 이미 방문한 노드를 다시 방문하게 되면, 불필요한 계산이 반복될 수 있고 최악의 경우 무한 루프에 빠질 수 있습니다. 사실, visited[] 체크는 일반적으로 go() 함수 내에서 처리하는데, 만약 main 함수의 이중 루프에서 모든 노드를 초기화하고자 하면 이러한 점검이 필요할 수 있습니다. 그러나 go() 함수가 이미 성공적으로 방문 상태를 관리하고 있다면, main 함수에서의 중복 체크는 필요하지 않을 수도 있습니다.
Q2. main()에서 go() 한 번 호출 후 exit(0) 시키지 않고 계속해서 go()를 더 호출하도록 코드를 짜는 이유
모든 노드를 한 번에 탐색하고 싶다면 adj 행렬을 통해 각 노드의 연결 상태를 확인하고 go(i)로 시도하는 것이 유의미합니다. 하지만, 주어진 코드는 인접해 있는 첫 번째 노드에서만 탐색이 이뤄지므로 exit(0);를 호출하면 처음 탐색한 노드만 탐색하게 됩니다. 즉, 그래프의 모든 성분을 탐색하지 않을 수 있습니다. 특정 조건이나 시작점을 기반으로 전체 그래프를 대상으로 한 번에 정확한 전위 순회를 수행하려면 main의 반복을 통해 모든 노드를 체크하는 것이 필요할 수 있습니다.
관련 토론과 코드 수정에 관하여 다음 링크를 참고하실 수 있습니다:
- 4-2 인접행렬 - 이 게시물에서는 이중 for문과 재귀함수의 역할에 대해 토론한 바 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.