프로그래머스 | Level 2 | 단체사진 찍기

Nov 05, 2024

Published byJynn

999

Programmers | Level 2 | 단체사진 찍기

Problems

📘 Src: Programmers
🗂️ Cat: Backtracking

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

 Constraints

입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.

1 <= n <= 100
data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
- 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
- 두 번째 글자는 항상 ~이다.
- 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.
- 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

󰦕 Examples

n	data	answer
2	`["N~F=0", "R~T>2"]`	3648
2	`["M~C<2", "C~M>1"]`	0

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    private static final String[] friends = {"A", "C", "F", "J", "M", "N", "R", "T"};  // 프렌즈 목록
    public int solution(int n, String[] data) {
        return backtracking(0, new String[8], new boolean[8], data);  // 백트래킹 시작
    }
    
    private int backtracking(int depth, String[] permutations, boolean[] marked, String[] data) {
        if (depth == 8) return 1;  // 모든 친구가 배치된 경우 유효한 배치로 카운트
        
        int count = 0;
        for (int i = 0; i < friends.length; i++) {
            if (marked[i]) continue;  // 이미 배치된 친구라면 넘어감
            
            marked[i] = true;
            permutations[depth] = friends[i];  // 현재 친구를 배치
            
            // 조건 만족시, 다음 배치로 재귀 호출
            if (checkSatisfied(depth, permutations, data)) {
                count += backtracking(depth + 1, permutations, marked, data);  // 다음 친구 배치로 이동
            }
            
            marked[i] = false;  // 배치된 친구 해제
        }
        
        return count;
    }
    
    private boolean checkSatisfied(int depth, String[] permutations, String[] data) {
        Map<String, Integer> positions = new HashMap<>();  // 현재 배치된 프렌즈의 위치 저장
        for (int i = 0; i <= depth; i++) {
            positions.put(permutations[i], i);  // 배치된 친구와 위치 매핑
        }
        
        for (String cond : data) {
            String subject = String.valueOf(cond.charAt(0));  // 조건을 제시한 친구
            String target = String.valueOf(cond.charAt(2));   // 조건의 상대 친구
            
            // 친구가 배치되지 않은 경우 조건 검사를 건너뜀
            if (!positions.containsKey(subject) || !positions.containsKey(target)) return true;
            
            char operator = cond.charAt(3);  // 조건의 연산자 ('=', '<', '>')
            int baseDist = cond.charAt(4) - '0';  // 조건의 거리
            int currDist = Math.abs(positions.get(subject) - positions.get(target)) - 1;  // 실제 거리 계산
            
            boolean isSatisfied = switch (operator) {
                case '>' -> currDist > baseDist;
                case '<' -> currDist < baseDist;
                case '=' -> currDist == baseDist;
                default -> true;
            };
            
            if (!isSatisfied) return false;  // 하나의 조건이라도 만족하지 않으면 false 반환
        }
        
        return true;  // 모든 조건을 만족하면 true 반환
    }
}

 Approaches

이 문제는 8명의 친구를 다양한 순서로 배치하면서 주어진 조건을 모두 만족하는 배치의 수를 찾는 문제입니다. 조건에 따라 친구를 배치하기 위해 백트래킹(Backtracking)을 사용하여 가능한 모든 배치를 시도하고, 각 배치에 대해 조건을 검토합니다.

1. 문제 분석

문제는 8명의 친구들이 정해진 조건에 맞게 서는 경우의 수를 찾는 것입니다. 각 조건은 두 친구 간의 거리를 특정 값으로 설정합니다. 예를 들어 "N~F=0"은 네오와 프록도가 나란히 서야 한다는 의미입니다. 이처럼 서로 다른 조건을 모두 만족할 수 있는 배치의 경우의 수를 계산하는 것이 목표입니다.

입력으로는 특정 거리 조건을 나타내는 조건들이 배열 형태로 주어지며, 이는 친구들이 특정한 배치 조건을 따르도록 요구합니다. 8명의 친구는 고정되어 있어, 가능한 배치는 8! 순열로 한정됩니다. 이를 통해 모든 배치를 생성하고 각 조건을 검사하여 조건을 만족하는 경우의 수를 구할 수 있습니다.

2. 접근 방식

이 문제를 해결하기 위해서는 가능한 모든 배치를 생성하고, 각 배치가 조건을 만족하는지 확인해야 합니다. 이 과정을 다음과 같이 단계적으로 접근합니다.

백트래킹을 통한 모든 배치 생성: 8명의 친구를 순서대로 배치하며 가능한 모든 경우를 생성합니다. 각 배치에서 친구가 이미 배치되었는지를 표시하는 배열과 현재까지의 배치를 저장하는 배열을 사용하여 깊이 우선 탐색으로 모든 경우를 생성합니다.
조건 만족 여부 검사: 각 배치가 완성될 때마다 주어진 조건을 확인하여 모든 조건을 만족하는지 검토합니다. 조건이 모두 충족되면 해당 배치는 유효한 것으로 간주하고, 배치의 개수를 1 증가시킵니다.
조건 평가: 조건은 두 친구 간의 상대 위치를 요구하며, 조건의 관계 연산자와 거리를 기준으로 실제 배치의 거리와 비교합니다. 두 친구가 특정 거리를 충족하는지를 판단하여, 만족하지 않으면 해당 배치를 가지치기합니다.

3. 지원자 조건 조합 생성

백트래킹을 활용해 모든 가능한 친구들의 배치 조합을 생성하며, 각 배치가 완료될 때마다 주어진 조건을 만족하는지 확인합니다. 이 과정에서는 각 친구가 이미 배치되었는지 여부를 기록하며, 아직 배치되지 않은 친구들을 현재 위치에 배치하는 방식으로 모든 가능한 배치 조합을 탐색합니다.

백트래킹은 현재 배치에서 조건을 만족하는지 확인하며, 조건을 만족하지 않는 경우 해당 배치는 더 이상 탐색하지 않으므로 효율적입니다. 이러한 방식으로 가능한 모든 배치를 생성하며, 각 배치의 유효성을 조건에 따라 판단하게 됩니다.

Solution.java

private int backtracking(
        int depth,            // 현재 깊이 (배치된 친구 수)
        String[] permutations, // 현재까지 배치된 친구 배열
        boolean[] marked,      // 친구가 이미 배치되었는지 표시
        String[] data          // 배치 조건 배열
) {
    if (depth == 8) return 1; // 모든 친구가 배치된 경우 유효한 배치로 카운트
    
    int count = 0;
    for (int i = 0; i < friends.length; i++) {
        if (marked[i]) continue; // 이미 배치된 친구는 건너뜀
        
        marked[i] = true;
        permutations[depth] = friends[i]; // 현재 친구를 배치에 추가
        
        // 조건을 만족하는지 확인 후, 다음 배치로 재귀 호출
        if (checkSatisfied(depth, permutations, data)) {
            count += backtracking(depth + 1, permutations, marked, data);
        }
        
        marked[i] = false; // 현재 배치에서 친구를 제외하고 다음 경우 탐색
    }
    
    return count;
}

4. 조건에 따른 거리 검사

배치가 완성되면 각 친구의 상대적인 위치가 조건을 만족하는지 검사합니다. 이를 위해 조건마다 두 친구 사이의 거리와, 조건의 연산자(같음, 이상, 이하)를 기준으로 실제 거리가 조건을 충족하는지 확인합니다.

조건 연산자: 두 친구 간의 거리를 특정 값과 비교합니다.
- = : 거리가 지정된 값과 같아야 함
- > : 거리가 지정된 값보다 커야 함
- < : 거리가 지정된 값보다 작아야 함
거리 계산: 두 친구가 배치된 위치를 이용해 실제 거리를 계산한 후, 해당 거리와 조건을 비교하여 조건을 만족하는지 확인합니다.

모든 조건을 만족하는 배치만 유효한 배치로 간주되며, 유효하지 않은 배치는 더 이상 탐색하지 않습니다.

Solution.java

private boolean checkSatisfied(
        int depth,            // 현재 배치된 깊이 (배치된 친구 수)
        String[] permutations, // 현재 배치된 친구 순서
        String[] data          // 배치 조건 배열
) {
    Map<String, Integer> positions = new HashMap<>(); // 각 친구의 현재 위치를 저장
    for (int i = 0; i <= depth; i++) {
        positions.put(permutations[i], i);
    }
    
    for (String cond : data) {
        String subject = String.valueOf(cond.charAt(0)); // 조건의 첫 번째 친구
        String target = String.valueOf(cond.charAt(2));  // 조건의 두 번째 친구
        
        // 친구가 배치되지 않은 경우 조건 검사를 건너뜀
        if (!positions.containsKey(subject) || !positions.containsKey(target)) return true;
        
        char operator = cond.charAt(3);  // 연산자 (같음, 이상, 이하)
        int baseDist = cond.charAt(4) - '0';  // 조건 거리
        int currDist = Math.abs(positions.get(subject) - positions.get(target)) - 1; // 실제 거리 계산
        
        // 조건에 따른 거리 비교
        boolean isSatisfied = switch (operator) {
            case '>' -> currDist > baseDist;
            case '<' -> currDist < baseDist;
            case '=' -> currDist == baseDist;
            default -> true;
        };
        
        if (!isSatisfied) return false; // 조건을 만족하지 않는 경우 유효하지 않음
    }
    
    return true; // 모든 조건을 만족하는 경우 true 반환
}

5. 조건을 만족하는 경우의 수 반환

모든 조건을 만족하는 배치가 확인되면 그 개수를 카운트합니다. 각 배치 조합이 조건을 모두 만족할 때마다 카운트를 증가시키며, 가능한 모든 배치를 탐색한 후 최종적으로 조건을 만족하는 배치 수를 반환합니다.

이 방식으로 모든 배치를 생성하고 조건을 검토하여, 주어진 조건을 만족하는 모든 경우의 수를 효율적으로 구할 수 있습니다.

Solution.java

// 조건을 만족하는 경우의 수 반환
return result;

󰄉 Complexity

⏳ TC: O(N!)
💾 SC: O(N)

8명의 친구를 배치하는 모든 경우를 백트래킹으로 생성하기 때문에 시간 복잡도는 O(N!)에 비례합니다. 각 배치가 생성될 때마다 조건을 검사하는 과정이 있으므로, 실제 복잡도는 조건 개수 N에 비례해 증가합니다.

Algorithm
Backtracking