인프런 커뮤니티 질문&답변
작성한 질문수
선생님! 바이러스 문제 코드 질문있어요오
해결된 질문
작성
·
220
1
선생님 안녕하세요 유튜브에서 보고 오늘 처음 수강했는데 너무 귀에 잘 들어와서 재미있어요 bfs 강의도 올려주세용!
다름이 아니고 바이러스 코드 중 이해가 안 되는 부분이 있어 질문 남깁니다!
def dfs(idx):
global visited, graph, answer
visited[idx]= True
answer += 1
for i in range(1, n+1):
if not visited[i] and graph[idx][i]:
dfs(i)바이러스 코드에서 idx가 3이 되고 answer가 3이 되는 부분 까지는 이해를 했는데 idx가 3일 때 for문을 돌면 2는 이미 방문했기 때문에 if문은 7까지 true가 되지 못하고 종료되는 것 아닌가요? 다시 idx=2로 돌아가서 5를 방문하게 되고 1에서 6을 방문하게 되는 부분은 코드 어느 부분에서 이루어지는 건지 잘 모르겠어요ㅜㅜ
답변 2
2
도리님 안녕하세요! :) 답변을 잘 드려야지 고민하다가 조금 늦어진 점 죄송합니다 ㅠㅠ.
우선 질문이 두 가지인 것 같아서 나눠서 정리해볼게요.
바이러스 코드에서 idx가 3이 되고 answer가 3이 되는 부분 까지는 이해를 했는데 idx가 3일 때 for문을 돌면 2는 이미 방문했기 때문에 if문은 7까지 true가 되지 못하고 종료되는 것 아닌가요?
idx가 3일 때 for문은 1부터 7까지 쭉 돌게 됩니다! 중간에 2는 이미 방문을 했기 때문에 if문 내부를 수행하지 않고 바로 i라는 변수가 3이 되고, 3도 현재 방문 중이니 그냥 넘어가고 4번을 확인할 겁니다.
이걸 이어서 하다보면 마지막 7번까지 다 확인을 하게 됩니다.
다시 idx=2로 돌아가서 5를 방문하게 되고 1에서 6을 방문하게 되는 부분은 코드 어느 부분에서 이루어지는 건지 잘 모르겠어요ㅜㅜ
답답하실 수 있겠지만, 위 코드에서 모두 이루어지는 겁니다! 다만 재귀라는 걸 쉽게 이해하시려면, 이 코드가 여러 벌 존재한다고 생각해도 좋을 것 같아요
예를 들어 아래 코드는 idx=1일 때 사용되는 dfs함수라고 해볼게요
def dfs(idx):
global visited, graph, answer
visited[idx]= True
answer += 1
for i in range(1, n+1):
if not visited[i] and graph[idx][i]:
dfs(i)그럼 이 dfs 함수는 i == 2일 때 호출 될텐데, 그 때 별도의 코드가 있다고 생각하는 겁니다.
def dfs(idx):
global visited, graph, answer
visited[idx]= True
answer += 1
for i in range(1, n+1):
if not visited[i] and graph[idx][i]:
dfs(i)그럼 아랫쪽 코드에서는 idx==2인거고, 이 코드를 다 수행하면 본인을 처음 호출 했던 위치로 돌아갈겁니다 (기본적인 함수 호출과 복귀의 원리로). 그리고 그 위치가 바로 윗쪽 코드의 dfs(i) 입니다. 결국 여기서 i == 2로 시작해서 아랫쪽 코드로 왔으니, 아랫쪽 코드 동작을 마무리하면 원래 자리로 돌아간다 라는 것이 전부입니다.
다만 이게 한 코드에서 들어갔다 나왔다를 반복하다보니 정신이 없는 건데, 이걸 개념적으로 설명해보려고 마치 여러 벌이 있는 것처럼 생각해보시라고 추천을 드려봤습니다.
이게 여전히 헷갈리시면 제가 첫 문제에서 설명 드렸던 것처럼 단계별로 누가 누구를 호출했는지를 꼭 정리해보세요! 그걸 잘 해보셔야지 헷갈리지 않고 재귀함수를 구현할 수 있을 거에요:)
나름대로 자세하게 쓴다고 썼지만 부족한 부분이나 추가 질문 있으면 알려주세요! 얼른 답변 드리겠습니다 :)
1
안녕하세요 도리님, 인프런 AI 인턴이에요. 코드 질문에 답변해드리겠습니다.
바이러스 코드에서 dfs(idx) 함수는 깊이 우선 탐색(Depth First Search, DFS) 알고리즘을 구현한 것으로 보입니다. 코드를 살펴보면 다음과 같은 과정을 거치게 됩니다.
- 시작 노드(
idx)를 방문 처리하고, 방문한 노드 수(answer)를 1 증가시킵니다.
- 그 다음, 인접한 노드들을 순회하며 방문하지 않은 노드(
not visited[i])이고, 현재 노드와 연결된 간선이 있는 경우(graph[idx][i])에 재귀적으로dfs(i)함수를 호출합니다.
- 이때, 호출된
dfs(i)함수에서도 마찬가지로 해당 과정을 반복하게 됩니다.
따라서, idx가 3인 경우 다음과 같은 순서로 진행됩니다.
- dfs(3) 호출: visited[3]을 True로 설정하고, answer를 1 증가시킴.
- for i in range(1, n+1) 순회:
- i=1일 때: visited[1]이 False이고, graph[3][1]이 True이므로 dfs(1) 호출
- i=2일 때: visited[2]이 True이므로 종료
- i=3일 때: visited[3]이 True이므로 종료
- i=4일 때: …
- i=5일 때: …
- i=6일 때: …
- i=7일 때: …
위 예시에서 idx 값이 3일 때 for 문이 종료되는 것은 visited[2]가 True인 경우에 해당합니다. 따라서 idx 값이 2인 경우에 해당 순회가 이루어지게 됩니다.
정확한 해석을 위해서는 코드에 대한 전체적인 이해가 필요하지만, 간략히 설명드리면 이 코드는 idx 값이 3인 경우에서도 다른 노드들을 순회하며 방문 여부를 확인하는 과정을 거치게 됩니다. 이는 방향 그래프의 연결 여부에 따라서 탐색 범위를 결정하는 것이기 때문입니다.
만약 여전히 이해가 어렵다면, 해당 코드 부분의 전체적인 흐름을 다시 살펴보시면 도움이 될 것입니다. 감사합니다!
선생님!! 달아주신 답글도 보고 바이러스 이후 강의도 더 들으면서 가르쳐주신 대로 문제에 대한 호출표 그리는 걸 여러 번 반복해 보니 이제 이해했어요 ㅠㅠ 자세한 답변 정말 감사합니다 남은 강의에서도 모르는 부분이 있으면 여쭤보겠습니당!!