graph 만들때 boolean[][] 으로 만드는 경우랑 int... - 인프런

[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편

알고리즘 수업 - 깊이 우선 탐색 1 (백준 24479)

graph 만들때 boolean[][] 으로 만드는 경우랑 int[][] 나 ArrayList<Integer>[] 로 만드는 기준이 어떻게 되나요?

해결된 질문

작성

강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.
해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!
- 취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(
이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!
이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)
"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 🙂

graph 만들때 boolean[][] 으로 만드는 경우랑 int[][] 나 ArrayList<Integer>[] 로 만드는 기준이 어떻게 되나요?

java 코딩-테스트 알고리즘 dfs

답변 2

개발자로 취직하기

지식공유자

안녕하세요 🙂

답변을 드렸다고 깜빡하고 늦게 댓글 남깁니다 죄송합니다 ㅠ

질문 주신 내용을 두 가지로 나눠보면 자료형을 boolean으로 할지, int로 할지 구분할 기준이 필요하고,

둘째는 이중 배열로 할지, ArrayList를 사용할지 결정할 기준이 필요합니다!

boolean vs int: boolean을 사용하는 것이 일반적입니다. 왜냐하면 우리에게 필요한 정보는 두 node 간 연결이 되어있는지 아닌지 알고 싶은 것이라 True/False로 구분만 하면 충분히 정보를 담을 수 있기 때문에 boolean이면 됩니다. 그런데 특정 문제에서는 이를 조금 더 복잡하게 출제해서 '연결되어 있냐/없냐'가 아니라 특정 숫자 값을 넣어서 '해당 칸에서 이동할 때 몇칸씩 이동할지' 등 일반 정보보다 추가되는 정보가 있습니다. 이런 경우는 단순 True/False로 표현할 수 없기 때문에 int로 구분을 해줄 필요가 있습니다. 정리하자면 True/False로만 표현이 가능하면 boolean을 쓰고, 그 외에 추가 정보가 필요하다면 int로 담아줍니다. 그리고 헷갈리신다면 매번 int를 쓰시고, boolean이 필요한 경우에는 0/1로 사용하셔도 됩니다!
[][] vs ArrayList: 이 경우는 정말 선택인데, [][]는 메모리 낭비가 심한 대신 성능이 빠르고, ArrayList는 성능은 상대적으로 느리지만 메모리가 훨씬 효율적인 장점이 있습니다. 그래서 Node 개수가 1000개 이하일 때는 [][]를 사용해도 메모리가 넉넉하기 때문에 [][]를 써서 빠른 성능을 낼 수 있고, 1000개를 넘어가면 애초에 [][]를 만들기 어렵기 때문에 ArrayList를 사용해야만 합니다. 이 경우에도 굳이 선택하거나 고민하기 싫으시다면 ArrayList를 매번 쓰셔도 동작에 문제가 없을 거에요!

인프런 AI 인턴

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

graph 생성 시 boolean[][]와 int[][], ArrayList[]를 사용하는 기준은 주로 그래프 내의 간선 표현 방식과 각 간선에 할당할 수 있는 값의 유형에 따라 달라집니다.

boolean[][]는 간선의 존재 여부만을 표시할 때 사용합니다. 만약 그래프 내의 특정 노드 사이에 간선이 있으면 true, 없으면 false로 표기합니다. 이 방식은 간선의 존재 여부만 중요할 때 간단하고 직관적입니다.
int[][]는 간선의 가중치가 있는 그래프를 표현할 때 사용합니다. 각각의 셀에는 특정 노드 사이의 간선에 대한 가중치(비용, 거리 등)를 저장할 수 있습니다. 이 방식은 다익스트라 알고리즘 같은 가중치 기반 알고리즘에 사용됩니다.
ArrayList[]는 그래프의 각 노드에 대해 연결된 노드 목록을 동적으로 관리할 때 사용합니다. 이 방식은 그래프의 연결 상태가 자주 변경되거나 간선의 개수가 불규칙할 때 유용합니다. 또한 인접 리스트는 메모리 관리 측면에서 효율적일 수 있습니다.

따라서, 선택 기준은 주로 그래프에서 표현하고자 하는 데이터의 유형(간선의 존재 여부, 가중치, 동적 변화 등)과 사용할 알고리즘에 맞춰 결정하게 됩니다.

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

graph 만들때 boolean[][] 으로 만드는 경우랑 int[][] 나 ArrayList<Integer>[] 로 만드는 기준이 어떻게 되나요?