38 câu hỏi đã được viết

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 알고리즘을 사용하여 그래프를 탐색한 뒤, 방문한 노드들의 순서를 출력해야 합니다.

만약 코드에 관련된 질문이 있다면, 코드를 공유해주시면 더 자세한 답변을 드릴 수 있을 것 같아요. 감사합니다.