hoon8810   2년 전

주 사용언어가 자바 라서 자바로 많은 문제들을 풀고 있는데요..

플로우 문제를 풀때 각 간선별 최대유량과 현재 흐르고 있는 유량을 표현할때

2차원 배열을 쓰면 코드도 간결하고 속도도 빠른데..

문제는 간선 갯수가 많아질때 배열을 쓰면 메모리 초과때문에

최대유량과 흐르는 유량을 표현할때 해쉬맵을 쓰고 있는데요

이렇게 풀면 시간초과가 나는 문제들이 많아서 다른방법을 생각해보고 있습니다.(원인이 이것때문인지는 모르지만)

간선을 클래스 객체로 만들어서 간선별로 최대유량, 현재유량을 두고 처리하는 방식을 생각중인데

자바로 플로우 문제 푸시는분들은 어떤 스타일을 사용하시는지... 궁금하네요.

startlink   2년 전

간선을 인접 리스트 형식으로 저장합니다. 

hoon8810   2년 전

감사합니다. 간선을 클래스로 만들어서 인접리스트로 구현하니까

유량을 흘릴때 객체에 접근해서 값만 바꿔주면 되니 연산횟수가 확 줄어들었네요.

전에는 유량을 표현하는 해쉬맵을 별도로 써서 유량을 흘릴때마다 넣고 빼고하는 작업이 많아서 시간이 오래걸렸네요.

댓글을 작성하려면 로그인해야 합니다.