BOJ 32085 Count BFS Graph

문제 링크:

문제 내용

길이 $N$ 의 순열 $A$ 가 주어집니다. 정점의 개수가 $N$ 이고 문제의 BFS 알고리즘의 출력이 $A$ 인 단순 무방향 그래프의 개수를 구하세요.

단순 그래프는 self loop (양 끝점이 같은 정점인 간선)과 multiple edge (동일한 두 정점을 연결하는 둘 이상의 간선)가 없는 그래프입니다. 인접 행렬이 서로 다르면 다른 그래프입니다.

첫 줄에 $N$ 이 주어집니다. ( $2 \le N \le 5000$ )

둘째 줄에 순열 $A$ 가 주어집니다. $A$ 의 첫 번째 원소는 1입니다.

문제의 정답을 $998\;244\;353$ 으로 나눈 나머지를 출력합니다.

스포일러

다음과 같은 DP를 세워볼 수 있습니다.

DP[x][y]: 알고리즘 동작 중에 $x$ 번째 원소가 u이고 큐에 $y$ 번째 원소까지 들어있을 때, 그 뒤의 순열을 완성하는 방법의 수

그러면 다음과 같은 식을 세워볼 수 있습니다.

DP[x][y] = DP[x+1][y] + DP[x][y+1] * 2^(y-x) * [v[y] < v[y+1]]
- 현재 상태에서 다음으로 가능한 동작으로는 $A_x$ 의 모든 이웃이 고갈되어 큐의 다음 정점으로 넘어가거나, $A_x$ 의 다음 이웃이 큐에 추가되는 두 가지 경우가 있습니다.
- 큐가 비어있지 않다면 큐의 다음 정점으로 넘어갈 수 있고, 이때 발생하는 간선의 선택권은 없습니다.
- 다음 이웃이 추가된다면 이전 이웃보다 정점 번호가 커야 하고, 그럴 경우 새로운 이웃과 직전에 큐에 들어있는 정점들 간의 간선들은 넣든 빼든 아무 상관이 없으므로 $2^{y-x}$ 가 곱해집니다.

그러나, “이전 이웃보다 정점 번호가 커야 함"은 직전 원소 또한 $A_x$ 의 이웃일 때에만 적용되며, $A_x$ 가 큐에서 뽑힌 직후에는 적용되지 않습니다. 따라서 이 두 가지 상태를 구분하기 위해 flag를 하나 추가해 줍니다.

이를 다차원 배열로 만들어 $x$ 와 $y$ 의 감소 순으로 채워주면 DP[0][0][0]이 최종 답이 됩니다.

Last updated on 2026년 1월 6일 12:26:11