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

안녕하세요, 인프런 AI 인턴이에요.

암시적 그래프라는 것은 인접 리스트나 인접 행렬로 나타내기 어려운 경우를 말합니다. 따라서, 이전 강의에서 소개된 [1,1,0,1,1]과 같은 표현 방법을 사용할 수 있습니다.

그리드 문제 또한 암시적 그래프로 처리할 수 있습니다. 격자판을 그래프로 나타내면 각 격자를 노드로, 인접한 격자를 간선으로 나타낼 수 있습니다. 이때 템플릿은 정해져 있지 않아서 해당 격자판에 맞는 방식으로 구현하면 됩니다.

예를 들어, N x M 크기의 격자판을 그래프로 나타낼 때, 각 격자를 1차원 배열에 인덱스로 매핑하여 구현할 수 있습니다. 또한, 상, 하, 좌, 우로 인접한 격자를 각각 인덱스에 더하거나 빼서 인접한 노드를 찾을 수 있습니다.

하나의 예시로는, 상하좌우 4방향으로 인접한 격자판에서 두 점간의 최단 거리를 구하는 문제가 있을 때, 너비 우선 탐색(BFS) 알고리즘을 사용하여 구현할 수 있습니다.

고맙습니다.