알고리즘 - BF(단체사진찍기)

• 문제 출처 : 프로그래머스
• 문제명 : 단체사진 찍기
• 분류 : DFS, BruteForce
• 언어 : Java
• 체감 난이도 : ⭐⭐⭐
• 풀이 시간 : 50min
• Fail Cnt : 0

---

---

알고리즘 설계

1. 자료

1) int[] g_location : 각 프렌즈들이 서있을 위치를 저장한다. 인덱스마다 프렌즈가 정해져 있고, 배열의 값은 프렌즈의 위치를 나타낸다.

만일 FCJAMNTR 순으로 서있다면 배열의 값은 다음과 같다.

Index:Frineds	0 : A(어피치)	1 : C(콘)	2 : F(프로도)	3 : J (제이지)	4 : M (무지)	5 : N(네오)	6 : R(라이언)	7 : T(튜브)
위치	4	2	1	3	5	6	8	7

2) int[] g_visited : DFS 방문 여부를 저장한다. 프렌즈 당 인덱스 번호는 g_location과 동일하다.

3) g_cnt : 조건을 만족하는 경우의 수를 카운팅한다.

---

2. 프로세스

1) public int solution(int n, String[] data) 메소드

각 인덱스를 시작점으로 해서 dfs탐색할 메소드(dfs_search)를 호출한다

2) public void dfs_search(int idx, int nth, int cnt, int n, String[] data) 메소드

1. g_visited[idx] <- 1 : idx 위치에 있는 프렌즈는 방문했다고 표시한다.
2. g_location[idx] <- nth : idx 위치에 있는 프렌즈가 몇번째에 서있는지 저장한다.
3. for(i=0 ~ i<8) { if(!visited[i]) { dfs_search(i, nth+1, cnt+1, n, data) } } : 방문 안한 프렌즈에 대해 nth+1번째 세우도록 재귀함수를 호출한다.
4. g_visited[idx] <- 0 : idx 위치에 있는 프렌즈를 방문안함으로 수정해 다른 경우의 수를 탐색 할 수 있도록 한다.
5. if(cnt == 8) {...} : 모든 프렌즈를 줄 세운 경우이다. 따라서 조건을 만족하는지 확인한다.

---

3. 구현 코드

    //전역변수
    int[] g_location = new int[10]; //순서대로 A, C, F, J, M, N, R, T 가 서 있는 위치를 저장한다
    int[] g_visited = new int[10];  //A, C, F, J, M, N, R, T 순서대로 방문 여부를 저장한다 (1:방문, 0:방문안함)
    int g_cnt = 0;  //조건을 만족하는 수를 카운팅

    /**
     * DFS를 사용해 완전탐색
     * @param idx 현재 탐색 인덱스
     * @param nth 몇번째에 세울건지
     * @param cnt 줄 세운 카카오프렌즈의 수
     */
    public void dfs_search(int idx, int nth, int cnt, int n, String[] data) {
        int i, index;
        int tempDist;
        char tempChar;  int charNum = 0;
        int from, to, dist;
        int flag = 0;
        from = to = dist = 0;

        g_visited[idx] = 1;
        g_location[idx] = nth;

        for(i=0; i<8; i++) {
            if(g_visited[i] == 0) { //방문 안한 사람은
                dfs_search(i, nth+1, cnt+1, n, data);
            }
        }

        g_visited[idx] = 0;

        if(cnt == 8) {  //모두 줄 세운 경우 조건을 만족하는지 확인한다

            for(i=0; i<n; i++) {

                index = 0;
                //조건을 제시한 프렌즈와 상대방 프렌즈의 인덱스를 구한다
                while(true) {
                    tempChar = data[i].charAt(index);

                    switch(tempChar) {
                        case 'A' : charNum = 0; break;
                        case 'C' : charNum = 1; break;
                        case 'F' : charNum = 2; break;
                        case 'J' : charNum = 3; break;
                        case 'M' : charNum = 4; break;
                        case 'N' : charNum = 5; break;
                        case 'R' : charNum = 6; break;
                        case 'T' : charNum = 7; break;
                        default: break;
                    }

                    if(index == 2) { to = charNum; break; } //상대방
                    else { from = charNum; index = 2; } //조건 제시 프렌즈
                }

                dist = data[i].charAt(4) - '0';

                //둘 사이의 거리를 구한다
                tempDist = g_location[from] - g_location[to];
                if(tempDist < 0) { tempDist *= -1; }
                tempDist -= 1;

                //조건을 만족하지 않으면 다음 조건을 확인하지 않고 루프를 나간다
                if(data[i].charAt(3) == '=') {
                    if(!(tempDist == dist)) { flag = 1; break; }
                } else if(data[i].charAt(3) == '>') {
                    if(!(tempDist > dist)) { flag = 1; break; }
                } else {
                    if(!(tempDist < dist)) { flag = 1; break; }
                }

            }   //end for(i)

            if(flag == 0) { //조건 만족
                g_cnt++;
            }
        }
    }

    public int solution(int n, String[] data) {
        int answer = 0;

        for(int i=0; i<8; i++) {
            dfs_search(i, 1, 1, n, data);
        }

        answer = g_cnt;

        return answer;
    }