스프링 객체조립기(assembler), 백준 11725번 문제를 풀며 든 인접리스트에 대한 생각. [최범균 스프링 5] 2021-05-26

객체 조립기는 이전 포스트에서 내가 DI가 필요한 이유에 대해서 설명할 때, 객체생성에 사용할 클래스를 변경하기 위해(의존을 하는 클래스는 변경하지 않고) 객체를 주입하는 코드 한 곳 만 변경하는것이 DI의 장점이라고 하였다. 그렇다면 이 '한 곳'에 실제 객체를 생성하는 곳이 필요한데 그것이 바로 객체조립기이다.

 

백준 11725번.

그래프 구현 방법중 인접리스트의 각 배열에 저장된 리스트 요소들의 정렬에 대한 고찰.

->일단 순서를 생각한다는 것 자체가 넌센스이다. 왜냐? 인접리스트와 인접행렬 이라는 방법을 자체가 [루트노드]가 주어진 그래프를 나타내는 방법이 아니라, 단지 [노드]와 [노드]사이의 연결관계를 표현한 것이기 때문이다.

->즉, 리스트배열에 저장된 리스트요소들의 정렬순서는, dfs나 bfs 방법을 쓸때, 방문하는 '순서'의 차이일뿐, 연결된 모든 노드를 방문한다는 사실은 똑같다.

애초에 dfs나 bfs는 그래프'탐색'알고리즘이다. 노드와 노드 간의 '연결'의 유무가 중요한 것이지, 순서(숫자가 큰지 작은지)등은 판단할 이유가 없다.

 

문제 해결법. 우선 주어진 노드와 노드의 관계를 노트에 인접리스트로 나타내니 특이한 규칙을 바로 발견할 수 있었다.

우선 노트에 나타내면,

(앞에 인덱스가 바로 배열의 인덱스이고, : 뒤에 붙은 것이 인덱스(n번노드)에 연결된 리스트의 요소이다.)

1번노드: 6 4

2번노드: 4

3번노드: 6 5

4번노드: 1 2 7

5번노드: 3

6번노드: 1 3

7번노드: 4

 

바로 각 n번 노드의 부모노드는 인접리스트로 표현 했을 때, 각 인덱스(~번노드)의 첫번째 요소라는 것이다. 

왜냐하면, 이건 문제의 입력방식에서 파생된 트릭인데, 애초에 루트노드가 존재하는 그래프 이므로, 입력으로 주어지는 노드의 첫번째 노드가 루트 노드로부터의 연결관계이다. 예) (1 6), (6 3),(3 5)...이렇게 주어진다면, 루트노드가 1번이고 그에 연결된 노드는 6, 6에연결된 노드는 3 이런 식이다..그냥 순서대로 인접 리스트를 만드는 순서만 지키며 리스트배열에 저장해도, 자연스럽게 루트노드가 1을 기준으로 했을때, 모든 노드들의 부모는 리스트배열의 첫번째 요소로 오게끔 문제가 구조화 되어있다. 이해가 안간다면, 직접 하나하나 노트에 인접리스트를 만드는 순서를 지키며 해 보자. 아무래도, 루트노드시작해서 연결관계를 표현할수 "밖에" 없기때문에 이런 현상이 일어난 거 같다.

 

순 공부/프로그래밍 시간 1시간 조금 넘게.

오늘 요양원에서 아스트라제네카 2차 접종을 한다고 오전공부를 못해서 시간이 많이 안나온거 같다.