인프런 커뮤니티 질문&답변
작성한 질문수
인접리스트 기반 탐색 코드 질문있습니다
해결된 질문
작성
·
469
0
안녕하십니까 큰돌님
인접행렬 때의 코드와 인접리스트 코드까지만 공부하고 퀴즈를 풀기 전에 작성했던 코드인데 깔끔하지는 않은데 1 2 3 4 출력은 잘 돼서 틀린 로직은 아닌 건가요 ??
답변 4
1
위 문제의 로직과 제가 작성한 코드의 로직이 많이 다른지 물어본 것이였습니다 !!
>> 네 다른 부분이 있습니다. 대표적으로 다음과 같은 코드입니다.
for (int there : a[i]) {
if (a[i][there] && visited[i] == 0) go(i);여기서 there의 의미는 a[i][0], a[i][1] ..의 의미를 갖기 때문에 이렇게 구축을 하시면 안됩니다.
이렇게 하게 되면
a[i][a[i][0]]... 식의 코드가 되어버립니다.
감사합니다.
0
Q. 인접리스트를 기반으로 탐색하기
1번.
정점은 0번 부터 9번까지 10개의 노드가 있다. 1 - 2 / 1 - 3 / 3 - 4 라는 경로가 있다. (1번과 2번, 1번과 3번, 3번과 4번은 연결되어있다.)
이를 인접리스트로 표현한다면?
2번.
0번부터 방문안한 노드를 찾고 해당 노드부터 방문, 연결된 노드를 이어서 방문해서 출력하는 재귀함수를 만들고 싶다면 어떻게 해야할까? 또한, 정점을 방문하고 다시 방문하지 않게 만드려면 어떻게 해야할까?
정답코드
#include<bits/stdc++.h>
using namespace std;
const int V = 10;
vector<int> adj[V];
int visited[V];
void go(int idx) {
cout << idx << '\n';
visited[idx] = 1;
for(int there : adj[idx]) {
if(visited[there]) continue;
go(there);
}
return;
}
int main() {
adj[1].push_back(2); adj[2].push_back(1); adj[1].push_back(3); adj[3].push_back(1);
adj[3].push_back(4); adj[4].push_back(3);
for(int i = 0; i < V; i++) {
if(adj[i].size() && visited[i] == 0) go(i);
}
}
문제를 빠트렸었네요 ㅎㅎ
위 문제의 로직과 제가 작성한 코드의 로직이 많이 다른지 물어본 것이였습니다 !!
0
안녕하세요 대기업님 ㅎㅎ
어떤 질문인지 모르겠어서 일단 코드를 리뷰드리면요.
for (int i = 0; i < V; i++) {정점은 1부터 4까지 있기 때문에 해당부분 고려해주어야 합니다.
for (int there : a[i]) {
if (a[i][there] && visited[i] == 0) go(i);여기서 there의 의미는 a[i][0], a[i][1] ..의 의미를 갖습니다. 해당부분 고려해주세요.
감사합니다.
0
안녕하세요, 인프런 AI 인턴이에요. 주신 링크에는 코드가 포함되어 있지 않아서 정확한 답변을 드리기가 어렵습니다. 그러나 인접리스트 기반의 탐색 코드를 작성하는 방법을 알려드릴게요.
일반적으로 인접리스트를 사용한 그래프 탐색은 DFS(Depth-First Search) 또는 BFS(Breadth-First Search) 알고리즘을 활용합니다. 이 알고리즘들은 스택(Stack)이나 큐(Queue) 자료구조를 사용하여 구현할 수 있습니다.
인접리스트에는 각 노드(정점)의 인접한 노드들을 리스트로 표현합니다. 이때, 리스트의 원소들은 해당 노드와 인접한 노드들의 번호입니다.
출력하려고 하는 1 2 3 4은 탐색한 순서에 대한 결과인 것 같습니다. 따라서 DFS나 BFS 알고리즘을 사용하여 그래프를 탐색한 뒤, 방문한 노드들의 순서를 출력해야 합니다.
만약 코드에 관련된 질문이 있다면, 코드를 공유해주시면 더 자세한 답변을 드릴 수 있을 것 같아요. 감사합니다.