112224   4년 전

문제 조건만 맞춰야지 하는 마인드로 풀었더니 너무 하드코딩이 되어있더라구요.

1) =이 나오면 유니온 파인드로 그룹지어 주었습니다.

2) > 가 나오면 위상정렬을 위해 인접 리스트에 저장한 후, 모든 입력이 끝나면 각 그룹의 부모끼리의 연결관계로 바꾸어주었습니다.

3) 위에서 만든 부모끼리의 연결 관계 중 그룹 안에서 상하관계가 발생되거나, 사이클이 존재하는 경우 inconsistent 처리 해주었습니다.

2)와 3)의 위상정렬 단계에서 불필요한 연산이 너무 많이 반복됩니다. 이를 해소하기 위해 visit 배열도 생각해 보았지만, 메모리상 말이 안되네요.

어떻게 하면 좋을까요..?

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