잊어먹지 않기 위해 개념만 기록해둠
- 왼쪽(here) -> 오른쪽(there) 그래프 만듬
- there가 누구와 매칭 되었는지 기록함 here
- 왼쪽 노드를 순서대로 탐색함
- 하는 일은 here와 연결된 there들을 찾으면서 빈 공간을 찾는데, 빈 공간이 없으면 연결/연결/연결들을 다 찾아가면서 빈 공간이 있는지 확인하고 하나씩 밀어내는 개념임
- dfs 탐색 비슷한데, 왼쪽노드의 vt 배열을 일단 초기화함
- 왼쪽 노드와 연결된 오른쪽이 비어있으면 -> 바로 연결
- 비어있지 않으면 -> there의 here와 연결된 정보를 탐색 -> 연결 연결 하다가 언젠가는 새로운 공간이 생길 수도 있고, 아닐 수도 있고
- 왼쪽 노드와 연결된 다른 오른쪽 노드에 대해서도 같은 작업 수행
newbieski