[코드트리 조별과제] 3 days - TIL

Topics

• 완전탐색 I

완전탐색 I

이번 조별과제는 완전탐색에 대해서 공부하였다. 그 중에서도 자리 수, 구간 단위로 완전탐색을 하고 자리마다 숫자를 정하는 완전탐색에 대해서 공부하였다. 그 중에서 어려웠던 내용이나 중요한 내용 몇 가지를 추려서 말하고자 한다.

 

1. 오목

import java.util.Scanner;

public class Main {
    private static final int SIZE = 19;
    private static final int[][] DIRECTIONS = {
        {0, 1}, // 오른쪽
        {1, 0}, // 아래쪽
        {1, 1}, // 오른쪽 아래 대각선
        {1, -1} // 왼쪽 아래 대각선
    };

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[][] board = new int[SIZE][SIZE];
        
        // 바둑판 상태 입력
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                board[i][j] = scanner.nextInt();
            }
        }
        
        // 승리 여부 확인
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (board[i][j] != 0) {
                    int winner = board[i][j];
                    if (checkWin(board, i, j, winner)) {
                        System.out.println(winner);
                        int[] winningPosition = findWinningPosition(board, i, j, winner);
                        System.out.println((winningPosition[0] + 1) + " " + (winningPosition[1] + 1));
                        return;
                    }
                }
            }
        }
        
        // 승부가 결정되지 않음
        System.out.println(0);
    }

    // 주어진 위치에서 승리 조건을 만족하는지 확인하는 함수
    private static boolean checkWin(int[][] board, int x, int y, int player) {
        for (int[] direction : DIRECTIONS) {
            int count = 1;
            int dx = direction[0];
            int dy = direction[1];
            
            // 한 방향으로 연속된 바둑알 개수 세기
            for (int step = 1; step < 5; step++) {
                int nx = x + dx * step;
                int ny = y + dy * step;
                if (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && board[nx][ny] == player) {
                    count++;
                } else {
                    break;
                }
            }
            
            // 반대 방향으로 연속된 바둑알 개수 세기
            for (int step = 1; step < 5; step++) {
                int nx = x - dx * step;
                int ny = y - dy * step;
                if (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && board[nx][ny] == player) {
                    count++;
                } else {
                    break;
                }
            }
            
            // 연속된 바둑알이 5개인 경우 승리
            if (count == 5) {
                return true;
            }
        }
        return false;
    }

    // 승리한 바둑알의 위치를 찾는 함수
    private static int[] findWinningPosition(int[][] board, int x, int y, int player) {
        for (int[] direction : DIRECTIONS) {
            int count = 1;
            int dx = direction[0];
            int dy = direction[1];
            int startX = x;
            int startY = y;
            
            // 한 방향으로 연속된 바둑알 개수 세기
            for (int step = 1; step < 5; step++) {
                int nx = x + dx * step;
                int ny = y + dy * step;
                if (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && board[nx][ny] == player) {
                    count++;
                    startX = nx;
                    startY = ny;
                } else {
                    break;
                }
            }
            
            // 반대 방향으로 연속된 바둑알 개수 세기
            for (int step = 1; step < 5; step++) {
                int nx = x - dx * step;
                int ny = y - dy * step;
            
                if (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && board[nx][ny] == player) {
                    count++;
                } else {
                    break;
                }
            }
            
            // 연속된 바둑알이 5개인 경우, 시작점과 끝점 중간의 위치 반환
            if (count == 5) {
                int midX = (x + startX) / 2;
                int midY = (y + startY) / 2;
                return new int[]{midX, midY};
            }
        }
        return new int[]{x, y};  // 기본값으로 현재 위치 반환
    }
}

 

문제에서 주어진 조건에 맞추어, 오목이 변환하는 규칙을 따라 위치를 변환하고, 위치를 찾는 알고리즘을 작성하였다.

2. G or H

import java.util.Scanner;

public class Main {
    public static final int MAX_NUM = 100;
    
    public static int n, k;
    public static int[] arr = new int[MAX_NUM + 1];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 입력
        n = sc.nextInt();
        for(int i = 0; i < n; i++) {
            int x = sc.nextInt();
            char c = sc.next().charAt(0);
            
            if(c == 'G')
                arr[x] = 1;
            else
                arr[x] = 2;
        }
        
        // 모든 구간의 시작점을 잡아봅니다.
        int maxLen = 0;
        for(int i = 0; i <= MAX_NUM; i++) {
            for(int j = i + 1; j <= MAX_NUM; j++) {
                // i와 j 위치에 사람이 있는지 확인합니다.
                if(arr[i] == 0 || arr[j] == 0)
                    continue;
                
                // 해당 구간 내 g와 h의 개수를 구합니다.
                int cntG = 0;
                int cntH = 0;
                
                for(int k = i; k <= j; k++) {
                    if(arr[k] == 1)
                        cntG++;
                    if(arr[k] == 2)
                        cntH++;
                }
                
                // 조건을 만족할 때 구간의 길이를 구해 최댓값과 비교합니다.
                if(cntG == 0 || cntH == 0 || cntG == cntH) {
                    int len = j - i;
                    maxLen = Math.max(maxLen, len);
                }
            }
        }
                            
        System.out.print(maxLen);
    }
}

 

최대 사진의 크기를 구하는 알고리즘으로, 시작점과 사람이 있는지 없는지를 판단하는 변수를 통하여 구간의 길이를 구해서 

최댓값과 비교하여 더 큰 값을 찾았다.

3. 개발자의 능력

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 6명의 능력을 입력받습니다.
        int[] abilities = new int[6];
        for (int i = 0; i < 6; i++) {
            abilities[i] = scanner.nextInt();
        }
        
        // 가능한 모든 팀 조합을 생성합니다.
        List<int[][]> teams = generateTeams(abilities);
        
        // 팀 간의 능력 차이를 최소화합니다.
        int minDifference = Integer.MAX_VALUE;
        for (int[][] team : teams) {
            int sum1 = abilities[team[0][0]] + abilities[team[0][1]];
            int sum2 = abilities[team[1][0]] + abilities[team[1][1]];
            int sum3 = abilities[team[2][0]] + abilities[team[2][1]];
            int maxSum = Math.max(sum1, Math.max(sum2, sum3));
            int minSum = Math.min(sum1, Math.min(sum2, sum3));
            int difference = maxSum - minSum;
            minDifference = Math.min(minDifference, difference);
        }
        
        // 최소 차이를 출력합니다.
        System.out.println(minDifference);
    }
    
    // 가능한 모든 팀 조합을 생성하는 함수
    private static List<int[][]> generateTeams(int[] abilities) {
        List<int[][]> teams = new ArrayList<>();
        int[] indices = {0, 1, 2, 3, 4, 5};
        generateCombinations(indices, 0, teams);
        return teams;
    }
    
    // 조합을 생성하는 함수
    private static void generateCombinations(int[] indices, int start, List<int[][]> teams) {
        if (start == indices.length) {
            int[][] team = new int[3][2];
            team[0][0] = indices[0];
            team[0][1] = indices[1];
            team[1][0] = indices[2];
            team[1][1] = indices[3];
            team[2][0] = indices[4];
            team[2][1] = indices[5];
            teams.add(team);
            return;
        }
        for (int i = start; i < indices.length; i++) {
            swap(indices, start, i);
            generateCombinations(indices, start + 1, teams);
            swap(indices, start, i);
        }
    }
    
    // 배열의 두 요소를 교환하는 함수
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

 

팀원들의 능력 총합이 큰 차이와 작은 차이의 갭을 최소화하여 균형있게 구성하였다.