gistfile1.txt

package jvm.ds;

import java.util.*;

/**
 * Collections를 활용한 N-Queen 문제 해결
 * - ArrayList: 각 행의 퀸 위치(열) 저장
 * - HashSet: 빠른 충돌 검사
 */
public class NQueenProblem {
    private static final int N = 8;
    private int solutionCount = 0;
    private List<List<Integer>> allSolutions = new ArrayList<>();
    
    // 현재 배치: queens.get(i) = j 는 i행 j열에 퀸이 있다는 의미
    private List<Integer> queens = new ArrayList<>();
    
    // 충돌 체크를 위한 Set들 (O(1) 검사)
    private Set<Integer> usedCols = new HashSet<>();           // 사용 중인 열
    private Set<Integer> usedDiag1 = new HashSet<>();          // 대각선 \ (row - col)
    private Set<Integer> usedDiag2 = new HashSet<>();          // 대각선 / (row + col)

    /**
     * 백트래킹으로 모든 해 찾기
     */
    public void solve() {
        backtrack(0);
        System.out.println("총 " + solutionCount + "개의 해를 찾았습니다.");
    }

    /**
     * row 행에 퀸을 배치하는 백트래킹
     */
    private void backtrack(int row) {
        // 모든 행에 퀸을 배치했으면 해를 찾음
        if (row == N) {
            solutionCount++;
            saveSolution();
            printSolution();
            return;
        }

        // 현재 행의 각 열을 시도
        for (int col = 0; col < N; col++) {
            if (isSafe(row, col)) {
                // 퀸 배치
                placeQueen(row, col);
                
                // 다음 행으로 진행
                backtrack(row + 1);
                
                // 백트래킹: 퀸 제거
                removeQueen(row, col);
            }
        }
    }

    /**
     * (row, col)에 퀸을 배치할 수 있는지 확인
     * Set을 사용하여 O(1) 시간에 체크
     */
    private boolean isSafe(int row, int col) {
        return !usedCols.contains(col) 
            && !usedDiag1.contains(row - col) 
            && !usedDiag2.contains(row + col);
    }

    /**
     * (row, col)에 퀸 배치
     */
    private void placeQueen(int row, int col) {
        queens.add(col);
        usedCols.add(col);
        usedDiag1.add(row - col);
        usedDiag2.add(row + col);
    }

    /**
     * (row, col)의 퀸 제거
     */
    private void removeQueen(int row, int col) {
        queens.remove(queens.size() - 1);
        usedCols.remove(col);
        usedDiag1.remove(row - col);
        usedDiag2.remove(row + col);
    }

    /**
     * 현재 해를 저장
     */
    private void saveSolution() {
        allSolutions.add(new ArrayList<>(queens));
    }

    /**
     * 현재 해 출력
     */
    private void printSolution() {
        System.out.println("해 " + solutionCount + ":");
        
        // 체스판 형태로 출력
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                if (queens.get(row) == col) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        
        // 퀸의 위치를 리스트로 출력
        System.out.println("퀸 위치 (행별 열 번호): " + queens);
        System.out.println();
    }

    /**
     * 특정 해를 출력
     */
    public void printSolutionByIndex(int index) {
        if (index < 0 || index >= allSolutions.size()) {
            System.out.println("유효하지 않은 인덱스입니다.");
            return;
        }

        List<Integer> solution = allSolutions.get(index);
        System.out.println("해 " + (index + 1) + ":");
        
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                if (solution.get(row) == col) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println("퀸 위치: " + solution);
    }

    /**
     * 모든 해를 가져오기
     */
    public List<List<Integer>> getAllSolutions() {
        return new ArrayList<>(allSolutions);
    }

    /**
     * 해의 개수 반환
     */
    public int getSolutionCount() {
        return solutionCount;
    }

    public static void main(String[] args) {
        System.out.println("=== 8-Queen 문제: Collections 활용 ===\n");
        
        NQueenProblem solver = new NQueenProblem();
        
        long startTime = System.currentTimeMillis();
        solver.solve();
        long endTime = System.currentTimeMillis();
        
        System.out.println("실행 시간: " + (endTime - startTime) + "ms");
        
        // 결과 검증
        if (solver.getSolutionCount() == 92) {
            System.out.println("✓ 정답! 모든 해를 찾았습니다.");
        } else {
            System.out.println("✗ 오류: " + solver.getSolutionCount() + "개의 해를 찾았습니다.");
        }
        
        // 몇 가지 해를 다시 출력
        System.out.println("\n=== 첫 번째와 마지막 해 ===");
        solver.printSolutionByIndex(0);
        System.out.println();
        solver.printSolutionByIndex(91);
        
        // 통계 정보
        System.out.println("\n=== 통계 ===");
        List<List<Integer>> solutions = solver.getAllSolutions();
        System.out.println("총 해의 개수: " + solutions.size());
        
        // 첫 번째 열에 퀸이 배치된 해의 개수
        long firstColCount = solutions.stream()
            .filter(sol -> sol.get(0) == 0)
            .count();
        System.out.println("첫 번째 행의 첫 번째 열에 퀸이 있는 해: " + firstColCount + "개");
    }
}