그래프 문제 풀 때마다 그래프를 어떻게 저장할지에서 한 번씩 멈칫하게 돼요. 인접 행렬이랑 인접 리스트 두 가지가 있다는 건 아는데, 막상 새 문제 만나면 어느 걸 골라야 할지 매번 헷갈리네요.
제가 이해한 차이는 이 정도예요.
인접 행렬 : 2차원 배열, 공간 O(V^2), 두 정점 연결 확인 O(1)
인접 리스트 : 정점마다 연결된 목록, 공간 O(V+E), 이웃 순회 편함
여기까지는 외웠는데, 실제로 문제 풀 때 "이 문제는 행렬" "이 문제는 리스트" 이렇게 판단하는 기준이 잘 안 서요. 그냥 대부분 인접 리스트 쓰면 되는 거 아닌가 싶다가도, 어떤 풀이는 굳이 행렬로 짜여 있어서 왜 그런가 싶고요.
정점 수가 많고 간선이 적은 희소 그래프면 리스트가 유리하다는 건 어렴풋이 알겠는데, 반대로 행렬이 확실히 나은 경우는 어떤 때인가요? 정점 수가 몇 백 개 이하로 적을 땐 그냥 행렬이 편하다는 말도 봤는데 이게 맞는 기준인가요? 그리고 두 정점이 연결됐는지 자주 확인해야 하는 문제면 행렬이 낫다고 보면 될까요? 실전에서 어떻게 판단하시는지 궁금해서 여쭤봐요.