인프런 커뮤니티 질문&답변

안녕하세요, 김옥윤님.

1번 문제와 2번 문제는 비슷한 문제인 것처럼 보이지만 확실한 차이점이 있습니다.

1번 문제는 땅덩어리가 총 몇개인지를 반환하는 문제이고, 2번 문제는 시작점(0,0)에서 도착점까지의 최단거리를 반환해야하는 문제입니다.

1번 문제에서는 땅덩어리가 몇개인지를 알아내기 위해서 2중 반복문으로 암시적 그래프를 순회하면서 땅(1)을 만나면 bfs(혹은 dfs)로 순회하면서 방문표시를 합니다. 방문표시를 하지 않는다면 2중 반복문에서 아직 방문하지 않은 새로운 땅으로 파악될 수 있습니다.

만약, 2중 반복문을 쓰지 않는다면? 어디에 땅이 있는지 어떻게 파악할 수 있을까요? 필연적으로 2중 반복문을 사용할 수밖에 없습니다.

2번 문제의 경우에는 시작점(0,0)이 주어집니다. 따라서 그 지점에서 단순히 bfs를 통해서 도착점까지의 최단거리를 구하면 되는 문제입니다.

만약, 이 문제에서 시작점이 어디인지 알려주지 않았다면(다만 시작점에는 표시를 해두었다면) 2중 반복문을 사용하여 시작점을 알아내야 했을 것입니다.

이 점에 유의하여 강의를 다시 시청해보시는 것을 권장 드립니다.

감사합니다.

안녕하세요, 인프런 AI 인턴입니다.

김옥윤님께서 질문하신 그래프 관련 강의에서 “그래프 1번 문제와 그래프 2번 문제에서 왜 for문 사용 방식이 다른가요?“라는 주제에 대해 설명드리겠습니다.

일반적으로 그래프 문제는 탐색 방식과 문제 해결 방법에 따라 for문 사용이 다를 수 있습니다.

1. 그래프 1번 문제에서는 보통의 경우 모든 정점을 확인하며, 각 정점에 연결된 간선들을 탐색하기 위해 두 번의 완전 탐색이 필요할 때가 많습니다. 이는 보통의 BFS(너비 우선 탐색)나 DFS(깊이 우선 탐색)에서 모든 정점과 간선을 탐색하는 과정에서 나타날 수 있습니다.

2. 그래프 2번 문제는 특정한 패턴이나 조건을 만족하는 정점/간선을 찾는 경우라면, 최적화된 경로나 옵션이 있을 수 있어, for문을 덜 사용하여도 원하는 결과를 도출할 수 있는 경우도 있습니다. 이는 문제의 특성에 따라 다르며, 가령 목표로 하는 정점에만 접근하면 되는 경우, 불필요한 탐색을 줄이고 성능을 개선할 수 있습니다.

추천 관련 답변 링크

아래는 그래프 문제에서 for문 사용과 관련된 유사한 질문 및 답변이 있는 링크입니다:

그래프 탐색 방법 및 시간 복잡도 관련 답변

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.