[PGS] 산 모양 타일링, 도넛과 막대 그래프

1. 도넛과 막대 그래프

1. 📑 사용한 알고리즘
   BFS

2. 📑 구현 방식에 대한 간략한 설명
   새롭게 생성된 정점은 쉽게 구할 수 있습니다. 해당 정점으로부터 나가는 간선이 2개 이상이면서(도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다. 라는 조건이 있음), 들어오는 간선이 0개인 정점을 찾으면 됩니다.

그렇게 시작 정점을 구한 후, 해당 정점으로부터 BFS 방식으로 분기하며 각 그래프의 종류를 찾았습니다.

먼저 8자 그래프인 경우, 임의의 한 정점에서 시작할 경우 탐색하다 보면 간선이 2개 연결된 정점이 무조건 존재합니다. 그래서 연결리스트 탐색 중 연결된 정점 개수가 2개 이상이면 8자 그래프로 판단했습니다.

도넛 그래프인 경우, 탐색하다보면 무조건 이미 방문한 정점을 탐색하게 됩니다.(시작 점으로 돌아오기 때문입니다.)

여기서 8자 그래프이지만, 8자 그래프로 판단되기전에 도넛으로 분류될 위험이 있다고 생각될 수 있습니다. 왜냐하면, "8자 그래프에서 간선이 2개 이상 연결된 정점을 탐색하기 전에 이미 방문한 정점을 방문하려하면 어떻게 하나?" 라는 의문이 생길 수 있습니다.

하지만 8자 그래프에서 간선이 2개 이상 연결된 정점은 도넛 그래프를 연결하는 중심에 위치합니다. 따라서 중복 방문할 정점은 항상 중심 정점이 되는데, 이 중심 정점을 중복 방문하기 전에 이미 간선 개수로 8자로 분류를 하게 되므로 도넛으로 오인될 확률은 없습니다.

2. 산 모양 타일링

1. 📑 사용한 알고리즘
   DP
2. 📑 구현 방식에 대한 간략한 설명
   재귀, 반복문 두 방식으로 모두 구현해 보았습니다.
   먼저 재귀로 구현하게 되면, dp[2 * n + 1][3]과 같이 삼각형을 기준으로 인덱싱을 적용했습니다.
   각 삼각형에서 정삼각형을 놓을지, 오른쪽으로 퍼지는 평행사변형을 쓸지, 위로 퍼지는 마름모를 쓸지와 같이 3분기로 나누어 탐색했습니다.

하지만 재귀의 경우, depth가 1씩 증가하게 되는데 이 때 재귀 깊이가 10만이 넘어가므로 StackOverFlow runtimeError가 발생할 위험이 있습니다. 그래서 반복문으로 추가 풀이했습니다.

반복문은 먼저 위에 정삼각형을 올릴 수 있는, 즉 거꾸로 뒤집어진 정삼각형을 기준으로 인덱싱을 적용했습니다. 왜냐하면, 분기가 이루어지는 곳은 항상 거꾸로 뒤집어진 정삼각형인 부분이고 정상적인 정삼각형 부분은 항상 정상 정삼각형으로 채운다고 생각하면 같은 경우의 수로 판단될 수 있습니다.

그 후 거꾸로 뒤집어진 정삼각형을 기준으로하면 총 4가지 경우의 수가 존재합니다.

1. 위로 퍼져나가는 마름모를 놓는다.
2. 이전 정삼각형과 함께 평행사변형을 이룬다.
   
3. 이후 정삼각형과 함께 평행사변형을 이룬다.
   
4. 정삼각형을 배치한다.

여기서 신경써야 할 부분은, 2번 방법입니다. 2번 방법을 적용하기 위해서는, 이전 거꾸로 뒤집어진 삼각형에서 3번 방법을 적용하지 않은 상태이어야 합니다. (이렇게 해야 겹치지 않습니다.)
그래서 2차원 dp를 활용해 3번 방법을 적용한 경우와, 3번 이외의 방법을 적용한 경우 두 가지로 나누어 구현했습니다.

거꾸로 뒤집어진 삼각형 기준
dp[i][0] -> i번째 거꾸로 뒤집어진 삼각형에서, 3번 방법을 적용합니다.
dp[i][1] -> i번째 거꾸로 뒤집어진 삼각형에서, 1,2,4번 방법을 적용합니다.

다만 여기서 위로 퍼져나가는 마름모는 tops[i]가 1일 때만 가능하므로, 해당 부분만 분기로 나누었습니다.
3번 방법은 위에 추가 삼각형이 있든, 이전에 어떤 방법을 썼든 항상 적용할 수 있으므로 dp[i][0]은 항상 dp[i - 1][0] + dp[i - 1][1]로 구했고,
1, 2, 4번 방법은 두 분기로 나누었습니다.

1. 위에 추가 삼각형이 있음
   아까 서술했듯이, dp[i][0]은 항상 같습니다.
   dp[i][1]은, 위에 삼각형이 있으므로 1번 방법을 사용할 수 있습니다. 다만 아까 말했듯이 2번 방법은 최근 놓은 거꾸로 뒤집어진 삼각형쪽에서 3번 방법을 쓰지 않았을 때 사용할 수 있기 때문에, 1,4번 방법만 사용 가능해 최근 3번 방법을 쓴 dp[i - 1][0]에 2를 곱해줍니다. 반대로 dp[i - 1][1]은 1,2,4 모두 가능하므로 3을 곱해줍니다.

2. 위에 추가 삼각형이 없음
   dp[i][0]은 같습니다.
   dp[i][1]은, 위에 삼각형이 없으므로 1번 방법 사용이 불가능합니다. 가능한건 2, 4인데, 이 또한 dp[i - 1][0]에서는 3번을 사용했으므로 4번 방법만 가능합니다. 그래서 곱하는것 없이 더해주고, dp[i - 1][1]은 2, 4번 가능하니 2를 곱해서 더해줍니다.

이상

코드는 https://github.com/kjy0349/algorithm/tree/main/%EC%A0%9C%EC%98%81/0407
에서 확인하실 수 있습니다.