-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
dfs, bfs 인접리스트
24.03.04 21:50 작성 24.03.05 10:29 수정 조회수 141
1
안녕하세요 강사님, 다름이 아니오라
그래프 탐색에서 그래프를 표현하는 방법으로 소개해주신 것 중에 인접리스트를 보면
딕셔너리로 key(노드) : values(간선)으로 표현하셨는데
강의 말고 다른 교재나 설명들을 보면 인접리스트를 표현할 때 딕셔너리로 나와있는 것은 본 적이 없고 강의 중에 풀어주셨던 rooms 예제에 나오는 것처럼
인덱스를 노드로 생각해서 [['b', 'c'], ['a', 'c', 'd'] , ['a', 'b'], ['b']] 이렇게 2차원 리스트로 표현하는 것만 나와있는데 어떻게 공부를 하면 되는 것일까요?
제가 한 방식을 정해서 체화시키는 것을 좋아해서요ㅠㅠ 자세히 설명해주시면 감사드리겠습니다.
또한 visited = []에 방문한 노드를 append로 추가하는 방식과
visited = [0] * (노드 번호 + 1, 0번째는 안쓰므로) 이거에서 방문한 노드의 원소 0을 1로 바꾸는 방식의 차이점이 무엇인지 궁금합니다.
1로 방문처리 해주는거랑, 방문한 노드를 추가해서 처리해주는 것의 차이가 궁금합니다.
유명한 코테 교재들 모두 가지고 있어서 봤는데
visited = [0] *(n+1)
dfs 함수 내에
visited[v] = True 이런식으로 1로 바꿔주면서 방문처리를 하더라고요 append는 안보이는거 같아서 여쭤봅니다!
아래는 제가 위에서 여쭤본 강의와 다른 교재들에서 본 내용인데 교재 모두가 이렇게 구현하고 있어서 여쭤봅니다ㅎㅎ 보편적인걸 원해서요 질문이 길어져서 죄송합니다
# DFS 메서드 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 인접 리스트 방식으로 그래프 표현
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
# 기본적으로 모든 값들을 False로 초기화하고, index 0은 사용하지 않는다.
visited = [False]*9
답변을 작성해보세요.
1
oldcar27
질문자2024.03.05
그러면 노드의 라벨이 0~n이 아닌 경우에는 강사님께서 소개해주신 append로 방문한 노드 추가하는 방법이 더 편하며 시간복잡도 상으로도 좋다는 말씀이시죠? 강사님 강의에 나온 dfs, bfs코드로 외워서 학습하면 되는 것인가요?
개발남노씨
지식공유자2024.03.05
제가 visited를 리스트로해서 append로 추가했던 이유는 어떤 노드를 방문하는지 그 순서를 print로 보여드리기 위해서였습니다. 만약에 그냥 단순하게 문제를 풀기 위함이면, 제가 답변에서 말씀드렸듯이 dictionary로 visited를 구현하는게 가장 좋습니다.
네넵 교재에도 있고, 강의에도 있는 dfs, bfs 코드를 기본적으로 외우고, 여기서 조금씩 조금씩 확장해나가시면 됩니다 ~~
oldcar27
질문자2024.03.05
visited에 append 하는 절차가 방문처리하는 과정 아닌가요? 방문처리를 해야 나중에 현재 노드가 visited 리스트에 있어서 방문처리된건지 아닌지를 알 수 있는 것으로 이해했어서요ㅠㅠ
그리고 유명한 코딩테스트 교재들 보면 노드가 a,b,c 문자여도 visited = [0] * n+1로 해놓고 1로 방문처리하는 것을 사용하고 있는데 따로 이유가 없나요?
또한 구글에다가 그래프 인접리스트라고 치면 모든 블로그에서 그래프를 딕셔너리로 구현을 안하고 전부 [[1,2], [3], [1]] 이런식으로 2차원 리스트로만 구현하고 있는데 강사님이 말씀해주신 내용이 효율적이라 생각되는데 왜 교재나 모든 블로그에서 딕셔너리로 그래프나 visited를 구현하지 않고 있는 것일까요? 혹시 강사님이 따로 개발하신 방법이신가요? 진짜 인접리스트라고 치면 전부 2차원 리스트로만 설명하고 있어서요ㅠㅠ
설명해주셨는데 비슷한 내용을 또 여쭤봐서 죄송합니다.
진짜 설명해주신 부분이 편하긴 한데 모든 글에서 비슷한 내용이 보이지 않으니깐 걱정되서 여쭤봅니다!
개발남노씨
지식공유자2024.03.05
append하는 절차가 방문처리 하는 과정 맞아요.
다만방문처리하는 방법이 답변에서 말씀드렸듯이
visited.append()
visited = [0] * n+1
dictionary
set
여러가지가 있어요.
각각의 장점과 단점은 아래에 적어드렸으니 참고하시면되고, 여기서 제가 추천하는 visited 구현방식은 3,4번이에요. 다만 암시적 그래프에서는 2차원 리스트로 구현이 되어있는데, 이건 2번 방법을 써서 구현한겁니다.
그런데 제가 1번 방식으로 강의에서 설명드렸던 건, print를 해서 여러분께 어디부터 방문하는건지를 명시적으로 보여주기 위함이였어요.
그리고 2차원 리스트로 그래프를 구현한건 보통의 강의나 교재가 C/ C++ 베이스로 만들어져서 그럴거에요. C/C++로 가면 괜히 unordered_map 으로 해시맵 만들어야되는데 귀찮아서 그냥 'a' 는 0번 인덱스에 넣자~ 이렇게 생각하고 구현하거나, mapping table을 따로 둬야되는데, 굳이 파이썬에서는 그럴필요 없죠.
python에서는 dictionary가 굉장히 편하게 구현되어있어서 활용도가 높습니다.
궁금한게 더 있으면 남겨주세요
oldcar27
질문자2024.03.05
이해했습니다. 빠르게 답변해주셔서 감사드립니다!
혹시 지금 연습문제나 풀어주신 내용들은 dfs, bfs 기본문제자나요.
골드 문제(코테에 나오는 수준)의 dfs, bfs 문제에서는 3, 4번 방식보다 2번 방식이 많이 쓰이나요? dfs, bfs 기출 문제 보면 암시적 그래프 탐색하는 문제가 많아 보여서 여쭤봅니다. 암시적 그래프는 2번을 주로 사용하신다고 하셔서요!
감사합니다.
개발남노씨
지식공유자2024.03.05
골드 문제(코테에 나오는 수준)의 dfs, bfs 문제에서는 3, 4번 방식보다 2번 방식이 많이 쓰이나요? => 난이도에 따라서 달라지는게 아닙니다. 암시적그래프는 dictionary로 구현하려면 복잡해져요. key에다가 좌표값을 넣어야되거든요. 암시적 그래프는 태생이 2차원 리스트로 구현이 되어있는 그래프다 보니까 visited도 그대로 2차원 리스트 쓰는게 편하게 되어있습니다.
제생각에, 조금 불안하시면 모든 문제에 대해서 2,3,4번으로 다 구현해보시길 추천드려요.
그러면 왜 이걸 써야되는지 알 수 있어요.
그냥 쓰라고 하고 싶지만, 저도 납득이 완전히 되지 않으면 못쓰는 타입이라, 그냥 다 해보거든요. 저처럼 한 문제를 풀 때 visited를 4가지 방법으로 다 적용해보면 완전히 이해가 될거에요!
한번 꼭 시도해보세요..!
0
개발남노씨
지식공유자2024.03.05
안녕하세요 oldcar27님.
좋은 질문 감사합니다.
답변 드릴게요~
딕셔너리로 key(노드) : values(간선)으로 표현하셨는데
강의 말고 다른 교재나 설명들을 보면 인접리스트를 표현할 때 딕셔너리로 나와있는 것은 본 적이 없고 강의 중에 풀어주셨던 rooms 예제에 나오는 것처럼
인덱스를 노드로 생각해서 [['b', 'c'], ['a', 'c', 'd'] , ['a', 'b'], ['b']] 이렇게 2차원 리스트로 표현하는 것만 나와있는데 어떻게 공부를 하면 되는 것일까요?
A. 우연히 노드의 번호가 0번부터~ n번까지 라벨링이 되어 있다면 2차원 리스트로 구현해도 됩니다. 하지만 일반적인, 모든 경우에 대해서 인접리스트를 구현할 수 있는 방법은 딕셔너리로 하는 방법 입니다.
그래서 제가 소개해드린 key(노드이름): values(연결된 다음 노드 이름) 이렇게 적어주시면 좋습니다.
상세한 설명은 교재해 추가해드렸어요.
교재에서 두 개의 페이지를 상세히 읽어보시면 도움될거에요~
visited
A. visited도 구현하는 방식이 상황에 따라서 다양할 수 있습니다.
제가 초반에 소개해드렸던,
visited = []
visited.append('A')이런 경우에는 위에서 말했듯이 노드의 라벨들이 0부터 n까지 정갈하게 되어있지 않은경우에 이렇게 구현을 하곤 하죠. 하지만 단점은, 나중에 'A'라는 노드가 visited에 포함되어있는지 확인해야 할 때, 시간복잡도가 O(n)이 걸린다는 것입니다.
if 'A' in visited: # O(n)
그래서 보통 dictionary 또는 hash set으로 visited를 구현하는게 더 편리할 뿐더러 시간복잡도 상으로도 더 좋습니다.
visited = {}
visited['A'] = True
if 'A' in visited: # O(1)
visited = set()
visited.add('A')
if 'A' in visited: # O(1)
물론 리스트를 써도 visited에 포함되어있는지 O(1)으로 알 수 있는 방법이 있습니다.
말씀해주신 예시처럼 노드의 라벨이 0~n으로 되어있는경우
visited = [False]*9
visited[3] = True
if visited[3] == True: O(1)이렇게 리스트로도 방문 체크도 O(1)으로 할 수 있습니다.
따라서 상황에 맞게 다양한 방식으로 사용할 수 있는 거죠!
답변 2