inflearn logo
강의

講義

知識共有

10週間完成 C++ コーディングテスト | アルゴリズムコーディングテスト

2週目の概念 #5. 隣接リスト(adjacency list)

인접리스트 기반 탐색 코드 질문있습니다

解決済みの質問

625

kyjun2470418

投稿した質問数 38

0

안녕하십니까 큰돌님

인접행렬 때의 코드와 인접리스트 코드까지만 공부하고 퀴즈를 풀기 전에 작성했던 코드인데 깔끔하지는 않은데 1 2 3 4 출력은 잘 돼서 틀린 로직은 아닌 건가요 ??

http://boj.kr/72b4a1f671414e30a599594cfaf2bb84

c++ 코딩-테스트

回答 4

1

kundol

위 문제의 로직과 제가 작성한 코드의 로직이 많이 다른지 물어본 것이였습니다 !!

>> 네 다른 부분이 있습니다. 대표적으로 다음과 같은 코드입니다.


		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

kyjun2470418

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

kundol

안녕하세요 대기업님 ㅎㅎ

어떤 질문인지 모르겠어서 일단 코드를 리뷰드리면요.

 

	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

communityai8509

안녕하세요, 인프런 AI 인턴이에요. 주신 링크에는 코드가 포함되어 있지 않아서 정확한 답변을 드리기가 어렵습니다. 그러나 인접리스트 기반의 탐색 코드를 작성하는 방법을 알려드릴게요.

일반적으로 인접리스트를 사용한 그래프 탐색은 DFS(Depth-First Search) 또는 BFS(Breadth-First Search) 알고리즘을 활용합니다. 이 알고리즘들은 스택(Stack)이나 큐(Queue) 자료구조를 사용하여 구현할 수 있습니다.

인접리스트에는 각 노드(정점)의 인접한 노드들을 리스트로 표현합니다. 이때, 리스트의 원소들은 해당 노드와 인접한 노드들의 번호입니다.

출력하려고 하는 1 2 3 4은 탐색한 순서에 대한 결과인 것 같습니다. 따라서 DFS나 BFS 알고리즘을 사용하여 그래프를 탐색한 뒤, 방문한 노드들의 순서를 출력해야 합니다.

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

코딩테스트 참고문헌 질문

0

45

2

4-P 질문 있습니다.

0

46

3

4-N 문제 수정 요청

0

34

1

2-T 질문

0

41

1

코딩 살구클럽 가입 문의

0

76

2

코딩살구클럽 가입문의

0

81

2

3-K private case 질문

0

77

2

안녕하세요. 코딩살구클럽 문의드립니다!

0

91

2

7:41 듣다가 질문합니다

0

95

2

코드 리뷰 요청드립니다!

0

91

2

코딩살구클럽 계정 문의

0

87

2

SK하이닉스 대비 강의수강

0

227

3

코딩살구클럽 등록부탁드립니다.

0

85

2

7-F 재귀로 풀시 런타임애러

0

85

1

1-N 문제 질문입니다. (+ 채점오류)

0

89

2

코딩살구클럽 가입 확인 부탁드립니다.

0

90

2

직장인 코테 합격 공부방법 문의

0

136

2

코딩살구클럽 가입 방법

0

106

2

6-H 체점 관련 질문

0

84

1

채점서버 연결 관련 질문입니다

0

112

2

삼성 s직군

0

96

1

삼성 코테 없어짐

0

247

1

코딩살구클럽 가입부탁드립니다

0

95

2

코딩살구클럽 가입 요청 확인부탁드립니다

0

78

2