[프로그래머스] 도넛과 막대그래프

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258711

풀이

각 노드 별로 어느 그래프에 속하는 지 판별해야 하므로 dfs를 사용해야겠다고 생각했다.
시작 노드가 랜덤으로 주어지면 판별이 부정확하고 시간이 늘어날 것으로 예상되어 각 그래프 별로 시작할 노드의 특징을 찾기 시작했다.

• 막대그래프 : 종점 노드가 outdegree는 0이고 indegree는 1 이상이다.
  • 1 이상인 이유는 추가 노드가 가리킬 경우를 고려하여 1이 아닌 1 이상으로 설정
• 8자 그래프 : 중간에 위치한 노드가 outdegree는 2이고, indegree는 2 이상이다.
• 도넛 그래프 : 모든 노드가 outdegree는 1이고, indegree는 1 이상
• 추가 노드 : outdegree는 2 이상이고, indegree는 0이다.

도넛 그래프의 노드들과 8자 그래프의 노드들이 중복될 수 있으므로 별다른 특징이 없는 도넛 그래프는 나머지 그래프들의 탐색이 끝난 후 진행한다.

기본 탐색은 dfs로 진행하는데, 막대그래프의 경우 반대로 탐색을 해야 하므로 인접행렬을 열기준, 행기준 둘 다 만들어주겠다.

1. 노드 압축 (이거 안하면 마지막 테케 통과 못함)

   노드 번호는 연속되지 않고, 1 11 29 38 이런 식으로 주어질 수 있다. 이럴 경우 요구되는 메모리 공간이 매우 커져 문제가 발생할 수 있으므로 압축을 진행해준다.

   • set(중복 허용 x)과 unordered_map을 사용하여 압축 진행

2. 연결 리스트 만들기

   • 기본적인 dfs를 위한 방향 그래프 생성
   • 막대 그래프를 위한 역방향 그래프 생성

3. 각 노드 별 outdegree와 indegree 개수 저장

4. 각 노드 별 outdegree와 indegree에 따른 그래프 분류 및 dfs

   • 미방문 노드일 경우, 앞서 말했던 조건에 맞춰 그래프 분류
     - 8자 그래프의 경우, 해당 노드로부터 dfs를 통해 방문 처리
     - 막대 그래프의 경우, 해당 노드로부터 역방향 그래프 dfs를 통해 조상 노드들 방문 처리
     - 추가 노드의 경우, 방문 처리 후 기록

5. 아직 방문하지 않은 노드들은 모두 도넛 그래프 소속

   • 미방문 노드를 시작으로 하여 dfs

코드

https://github.com/LGY010011/Algorithm/blob/main/Algorithm/P258711.cpp