[프로그래머스] 산 모양 타일링 (실패)

문제

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

프로그래머스

 

문제 분석

[제한사항]

• 1 ≤ n ≤ 100,000
• tops의 길이 = n
  • tops[i]는 사다리꼴의 윗변과 변을 공유하는 i+1번째 정삼각형의 위쪽에 정삼각형을 붙이는 경우 1, 붙이지 않는 경우 0입니다.

 

우선 하나하나 맞춰보는 거 말고는 다른 방법이 생각나지 않았다.

n 의 크기가 10^5 까지기 때문에 완전 탐색으로는 해결이 힘들어 보였지만 다른 방법이 떠오르지 않아 우선 시도해 보았다.

문제 접근

[실패]

해당 도형에 마름모를 하나하나 맞춰가면서 가능한 모든 가능성을 체크하였다.

도형 형태로는 코드로 계산할 수 없기 때문에 아래와 같이 그래프 형태로 만든 후 마름모가 들어갈 수 있는 모든 경우의 수를 체크하여 문제를 풀었다.

 

그래프의 간선은 두 삼각형을 이용해 마름모를 만들 수 있다는 것을 나타낸다.

 

주어진 정보를 통해 간선들을 모아 둔 리스트를 만들고

간선들을 조합하여 문제를 풀었다.

이때 사용한 간선에 붙은 노드는 방문 처리하여 다시 사용하지 않도록 막아 두었다.

 

하지만 역시 시간 초과로 11번 테스트 부터는 통과하지 못했다.

코드 (실패)

import java.util.*;

class Solution {
    static int result = 0;
    public int solution(int n, int[] tops) {
        int e = 0;
        int cnt=0;

        // edge 구성
        List<int[]> edges = new ArrayList<>();
        for (int i = n + 1; i < 2 * n + 1; i++) {
            edges.add(new int[]{i, e});
            e++;
            edges.add(new int[]{i, e});
            if (tops[cnt] == 1) {
                edges.add(new int[]{2 * n + 1 + cnt, i});
            }
            cnt++;
        }

        boolean[] visited = new boolean[3 * n + 1];

        int maxDepth = visited.length / 2;

        for (int i = 0; i <= 10; i++) {
            dfs(0, visited, edges, 0, i);
        }

        return result % 10007;
    }
    public static void dfs(int start, boolean[] visited, List<int[]> edges, int depth, int maxDepth){
        if (depth == maxDepth) {
            result++;
            return;
        }

        for (int i = start; i < edges.size(); i++) {
            int[] edge = edges.get(i);
            if (!visited[edge[0]] && !visited[edge[1]]) {
                visited[edge[0]] = true;
                visited[edge[1]] = true;
                dfs(i + 1, visited, edges, depth + 1, maxDepth);
                visited[edge[0]] = false;
                visited[edge[1]] = false;
            }
        }
    }
}