그래프 암시적 그래프 질문입니다!
427
작성한 질문수 3
너비우선 탐색부분 강의 듣는중입니다!
이전 강의에서 암시적 그래프 최단거리 찾기 등의 그래프를 구현할 때는 [1,1,0,1,1] 이런식으로 구현하라고 하셨는데,
저런 문제도 지금 bfs강의에서 외우라고 하신 템플릿 대로 외워서 조금 응용해서 풀면 되는건가요???
격자판 문제가 조금 어려워서 질문드립니다!
격자판은 템플릿이 따로 있나..해서요!
답변 1
0
안녕하세요, 인프런 AI 인턴이에요.
암시적 그래프라는 것은 인접 리스트나 인접 행렬로 나타내기 어려운 경우를 말합니다. 따라서, 이전 강의에서 소개된 [1,1,0,1,1]과 같은 표현 방법을 사용할 수 있습니다.
그리드 문제 또한 암시적 그래프로 처리할 수 있습니다. 격자판을 그래프로 나타내면 각 격자를 노드로, 인접한 격자를 간선으로 나타낼 수 있습니다. 이때 템플릿은 정해져 있지 않아서 해당 격자판에 맞는 방식으로 구현하면 됩니다.
예를 들어, N x M 크기의 격자판을 그래프로 나타낼 때, 각 격자를 1차원 배열에 인덱스로 매핑하여 구현할 수 있습니다. 또한, 상, 하, 좌, 우로 인접한 격자를 각각 인덱스에 더하거나 빼서 인접한 노드를 찾을 수 있습니다.
하나의 예시로는, 상하좌우 4방향으로 인접한 격자판에서 두 점간의 최단 거리를 구하는 문제가 있을 때, 너비 우선 탐색(BFS) 알고리즘을 사용하여 구현할 수 있습니다.
고맙습니다.
노션 공유 링크
0
87
2
수업 중간에 내주신 문제는 해답을 알 수 없는걸까요?
0
78
2
최신 강의와 비교
0
85
2
Min Cost Climbing stairs 질문
0
77
2
노션 공유 부탁드립니다!
1
88
2
for 문에 sort 함수 를 사용하면
1
90
2
노션 공유 부탁드립니다.
0
104
2
디스코드가 올바르지 않다고 뜹니다..!
0
107
1
그래프
0
98
2
노션 공유
1
123
2
시간복잡도 질문
2
125
3
11강 질문
1
78
2
노션 공유 부탁드립니다
0
84
2
linkedList - BrowserHistory 코드 질문
0
76
1
list1.append(list2)와 list1.append(list2[:])의 차이가 무엇인가요?
1
168
1
라이브러리 사용
1
137
2
문제 교재는 따로 없는 거 맞나요?
1
202
2
LCA 관련해서 질문이 있습니다.
1
118
2
[Unique Paths] 완전탐색 / DP (후반부)
0
108
1
dp 계단오르기최소비용질문입니다.
0
109
1
Dynamic Array 의 size 정보가 저장되는 곳
2
161
2
노션공유가 안된듯 합니다
1
165
2
[코테 적용] 👉 [3번 문제] 완전탐색 (DFS, BFS) (전반부)
1
122
1
강의자료 만들 때 사용하신 프로그램이 뭘까요?
1
204
1