가중치가 1 이상일 경우~
백준 - 깊이우선탐색 강의에서 "모든 간선의 가중치가 1"이라고 되어 있는데 이게 정확히 무슨 의미 일지요? 가중치가 1 이상이면 이 가중치 정보를 그래프에 담아야 할까요??(구조체 사용)
답변 1
2
안녕하세요 :)
가중치가 1이라는 것은 두 정점 간의 거리가 1이라는 것을 의미합니다. 비유를 들어보자면 노드를 도시라고 생각하면 되고, 가중치는 그 도시들 간의 거리라고 생각하면 됩니다. 그래서 한 도시에서 다른 도시로 갈 때 항상 비용은 1이 된다는 것을 의미하고, 다른 의미로 "노드들 간에 이동하는 거리 혹은 비용은 동일하니 이것까지 고려할 필요는 없다" 정도로 정보를 제공한 것으로 보여요.
말씀하신 대로 가중치가 1이 아닌 경우에는 해당 가중치를 고려해서 계산해야 합니다. 이럴 때는 별도 구조체를 두기 보다는 graph라는 배열을 boolean 배열이 아닌 int 혹은 long 배열로 만드는 방식을 사용해요. 그래서 기존 boolean일 때는 "연결됐다 혹은 안됐다" 정보만 저장했다면, int 배열로 바꿀 경우 "연결됐을 때의 거리"를 배열 요소로 저장해두면 됩니다!
혹시 설명이 부족한 부분이 있으면 알려주세요!
오늘도 DFS 공부 화이팅입니다 :)
dfs 부문을 이렇게 작성해도 되나요?
1
74
1
x랑 y를 거꾸로 쓰는 개념이 너무 헷갈립니다...
1
97
2
dfs 파라미터에 count를 넣는이유
1
65
2
graph 채울때 for문 설계 질문
1
73
2
질문있습니다.
1
75
1
다른 강의 언제나오나용?
1
94
2
노드간 거리 계산
1
146
1
안녕하세요, 혹시 다른문제도 여쭤볼 수 있을까요?
1
131
1
최근에 올린 질문, 코드블럭으로 공유드립니다!
1
143
1
질문이 있습니다. dfs 메서드에 order를 이렇게 구현하면 안되는 이유가 무엇인가요?
0
135
2
깊이우선탐색2 백준 24480 수업노트에...
1
120
1
백준 24479 문제 제출 결과 "틀렸습니다" 라고만 나와서 어떤 부분이 틀렸는지 잘 모르겠어요 피드백 부탁드립니다
1
251
3
graph 만들때 boolean[][] 으로 만드는 경우랑 int[][] 나 ArrayList<Integer>[] 로 만드는 기준이 어떻게 되나요?
1
202
2
graph를 2차원 배열 또는 List로 하는 기준을 어떤식으로 잡으면 좋을까요...?
1
224
1
강사님 안녕하세요! 깊이 우선 탐색 2 (백준 24480)에서 제공하는 풀이 코드에서 궁금한 점이 있어서 질문 드립니다!
1
328
3
촌수 계산
1
355
3
연결 요소의 개수 (백준 11724)
1
268
1
백준 24479 문제 시간 초과 질문 드려요
1
384
1
백준 실행시 틀립니다.
1
373
1
재귀대신 스택으로 구현하면 안될까요?
1
410
1
dfs 매개변수에서 y,x 를 왜 순서를 반대로 쓰셨는지 궁금합니다.
1
373
1
안녕하세요 11724번 질문드려요!
2
316
1
출력할 때 BufferedWriter? StringBuilder?
1
513
1
answer++ 위치 질문
1
257
1