[java] 백준 11724 - 무방향 그래프를 양방향으로 저장해야 하는 이유가 궁금합니다

Question

https://www.acmicpc.net/problem/11724(백준 질문게시판에도 동일한 질문이 있는데 달려있는 답변이 이해가 가질 않아서 okky에 도움 청해봅니다!)인접리스트를 이용해서 해결하긴 했습니다. 무방향 그래프이고 한 번만 탐색하면 되니 굳이 양방향으로 연결해줄 필요가 없겠다 싶어 39번 라인 없이 제출하니 틀려서 양방향으로 연결하고 성공했습니다.dfs 한 번 돌 때 방문 처리를 할텐데 양방향으로 저장해야 하는 이유가 궁금합니다 !!

jeus1212 · Accepted Answer

6 5 1 2 2 5 5 1 3 4 6 4 answer &#61; 2 작성자님 예상 답안 &#61; 3 반례 입니다 단방향 그래프라면 연결 요소의 개수는 3이겠지만 무방향(양방향 그래프는) 2로 정답이 나옵니다 단방향이라면 1 -> 2 -> 5 3 -> 4 6 output: 3 양방향이라면 1 -> 2 -> 5 3 -> 4 -> 6 output: 2 그림판에 그려보면서 하기거나 실제 출력을 하면서 반례를 생각하시면 실력 향상에 많은 도움이 됩니다

[java] 백준 11724 - 무방향 그래프를 양방향으로 저장해야 하는 이유가 궁금합니다

1개의 답변

기술 목록