[ 코드트리 조별과제 ] 프로그래밍 연습 - Chapter6. 완전탐색(1)

 

 자리수 단위로 완전탐색 

각 자리의 조합상황을 가정하고 진행해보는 완전탐색 방법을 이용할 수 있다. ( for문을 이용 )

 

 

[ 개념문제 ] 세 자리를 정하여 완전탐색 : 일렬로 서 있는 소2

https://www.codetree.ai/missions/5/problems/cattle-in-a-rowing-up-2?&utm_source=clipboard&utm_medium=text

N마리의 소가 x = 1부터 x = N까지 순서대로 서 있습니다.
각 소의 키는 Ai​이며, 예를 들어 첫 번째 위치에 놓여있는 소의 키는 A1​입니다.
3마리의 서로 다른 소의 위치를 (i, j, k)라고 했을 때, i < j < k를 만족하며 동시에 Ai​≤Aj​≤Ak​ 를 만족하는 서로 다른 쌍의 수를 구하는 프로그램을 작성해보세요.

첫 번째 줄에 N이 주어집니다.
두 번째 줄에는 N마리의 소의 키 정보 Ai​가 공백을 사이에 두고 순서대로 주어집니다.
1 ≤ N ≤ 100
1 ≤ Ai​ ≤ 100

 

첫번째, 두번째, 세번째까지 순차적으로 소의 위치를 모두 가정하는 완전탐색을 진행한다.

모든 상황에서 조건을 만족하는 경우가 무엇인지 탐색해 볼 수 있다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] cows = new int[n];
        for(int i=0; i<n; i++) cows[i] = sc.nextInt();

        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                for(int k=j+1; k<n; k++){
                    int a = cows[i];
                    int b = cows[j];
                    int c = cows[k];

                    if(a<=b && b<=c) cnt++; 
                }
            }
        } 

        System.out.println(cnt);
    }
}

 

---

 

[ 응용문제 ] 체크판위에서2

https://www.codetree.ai/missions/5/problems/on-the-checkboard-2?&utm_source=clipboard&utm_medium=text

R * C 크기인 직사각형의 각 칸이 W, B로 표현되어 있습니다. W는 하얀색으로, B는 검은색으로 칸이 채워져 있는것을 뜻합니다. 왼쪽 상단에서 출발하여 우측 하단으로 이동할 때, 특정 룰을 만족하면서 이동에 성공할 수 있는 경우의 수를 구하는 프로그램을 작성해보세요. 아래가 특정 룰입니다.

1. 이동은 항상 점프를 통해서만 가능합니다. 또, 점프 진행시 항상 현재 위치에 적혀있는 색과, 점프한 이후의 칸에 적혀있는 색이 달라야만 합니다.
2. 점프 진행시 현재 위치에서 적어도 한칸 이상 오른쪽에 있는 위치이며 동시에 현재 위치에서 적어도 한칸 이상 아래쪽에 있는 위치인 곳으로만 점프가 가능합니다.
3. 정확히 시작, 도착 지점을 제외하고 점프하며 도달한 위치가 정확히 2곳 뿐이어야 합니다.

첫 번째 줄에 R, C가 공백을 사이에 두고 주어집니다. (R은 직사각형의 세로변, C는 가로변을 뜻합니다)
두 번째 줄부터 R * C크기의 직사각형이 W B로 주어집니다.
5 ≤ R, C ≤ 15

첫 번째 줄에 룰을 만족하면서 이동에 성공할 수 있는 경우의 수를 출력합니다.

 

예제

5 5
W W W W W
W W W W W
W B W W W
W W W W W
W W W W B

 

 

(행, 열) 기준으로 다음 2가지 방법이 가능합니다. 두 방법 모두 밟게되는 위치에 적혀있는 색이 'W', 'B', 'W', 'B' 순으로 조건을 만족하게 됩니다.

• (1, 1) → (3, 2) → (4, 3) → (5, 5)
• (1, 1) → (3, 2) → (4, 4) → (5, 5)

 

 

점프조건을 분석해보면 열 크기와 행 크기가 모두 이전위치보다 커야하고 색값을 달라야한다.

그리고 마지막까지 점프를 마치게 된 위치가 격자의 최하단이어야한다.

모든 점프 조합상황을 가정하고 만족조건을 충족하는 것들의 갯수를 알아낸다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();

        //입력값 처리, 바둑판 만들기
        char[][] arr = new char[r][c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) arr[i][j] = sc.next().charAt(0);
        }  
        
        int ans = 0; //정답갯수
        
        //이동규칙 : 열크기 크게, 행크기 크게, 색값 다르게
        //첫번째 점프
        for(int i=1; i<r; i++){
            for(int j=1; j<c; j++){
                if(arr[i][j] != arr[0][0]){ //첫번째 점프조건 만족
                    //System.out.println("First jump: " + i +" "+ j);
                    
                    //두번째 점프
                    for(int k=i+1; k<r; k++){
                        for(int l=j+1; l<c; l++){
                            if (arr[k][l] != arr[i][j]) { //두번째 점프조건 만족
                                //System.out.println("second jump: " + k +" "+ l);
                                
                                //도착지점 확인
                                for(int m=k+1; m<r; m++){
                                    for(int n=l+1; n<c; n++){
                                        if(arr[m][n] != arr[k][l] && m==r-1 && n==c-1) ans++;
                                    }
                                }
                                
                            }
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

 

어려웠던 점 : 

처음에는 다음과 같이 new column과 new row를 업데이트 하는 방식으로 진행했는데 이렇게 연속점프를 한번에 처리하게 되면 연속 점프에 대한 여러조합이 제대로 찾아지지 않아서 문제가 발생했다.

예를들어, (1, 1) → (3, 2)로 점프이후 다음 점프위치를 (4, 3) 하나만 찾게 되어서 문제가 발생한다.

//이동규칙 : 열크기 크게, 행크기 크게, 색값 다르게
// int ans = 0;
// int cnt = 0;
// int nr = 0; //now row
// int nc = 0; //now col
// char color = arr[nr][nc];
// for(int i=nr+1; i<r; i++){
//     for(int j=nc+1; j<c; j++){
//         if(arr[i][j] != color){ //점프가능조건 만족
//             nr = i;
//             nc = j;
//             System.out.println(cnt+"번째 "+nr+" "+nc);
//             color = arr[nr][nc];
//             cnt++; //점프횟수
//             if(cnt==3 && nr==r-1 && nc==c-1 ) {
//                 ans++;
//             }
//         }
//     }
// }

 

해설답안

import java.util.Scanner;

public class Main {
    public static final int MAX_N = 15;

    public static int n, m;
    public static char[][] grid = new char[MAX_N][MAX_N];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                grid[i][j] = sc.next().charAt(0);
            }

        // 이동 시에 행과 열이 전부 증가하도록
        // 모든 쌍을 다 잡아봅니다.
        int cnt = 0;
        for(int i = 1; i < n; i++)
            for(int j = 1; j < m; j++)
                for(int k = i + 1; k < n - 1; k++)
                    for(int l = j + 1; l < m - 1; l++)
                        // 그 중 색깔이 전부 달라지는 경우에만 개수를 세줍니다.
                        if(grid[0][0] != grid[i][j] && 
                           grid[i][j] != grid[k][l] &&
                           grid[k][l] != grid[n - 1][m - 1])
                            cnt++;
        
        System.out.println(cnt);
    }
}

 

---

 

[ 응용문제 ] 원 모양으로 되어있는 방

https://www.codetree.ai/missions/5/problems/a-room-in-a-circle?&utm_source=clipboard&utm_medium=text

원 모양으로 되어있는 N개의 방이 있고, 방은 1부터 N까지 시계 반대방향으로 번호가 매겨져 있습니다. 각 방에는 이웃한 두 개의 방으로 통하는 문이있습니다. 사람들은 무조건 시계 반대방향으로만 이동해야 합니다.

각자 방에 몇 명이 사람이 들어가야하는지 주어지며, 모든 사람이 같은 방에서 시작한다고 합니다. 어떤 방에서 시작해야 각 방에 정해진 인원이 들어가는 데까지의 거리의 합을 최소화 할 수 있는지를 계산하는 프로그램을 작성해보세요.

첫 번째 줄에 정수 N이 주어집니다.
두 번째 줄부터는 N 개의 줄에 걸쳐 한 줄에 하나씩 순서대로 각 방에 들어가야 하는 사람들의 인원이 주어집니다.
3 ≤ N ≤ 1,0031 ≤ 각 방에 들어가야 하는 사람들의 인원 ≤ 100

첫 번째 줄에 각 방에 정해진 인원이 들어가는 데까지의 최소화된 거리의 합을 출력합니다.

 

예제

5
4
7
8
6
4

 

 

단순히 start인덱스와 돌아가는 인덱스(i)사이의 거리를 구하는 것이 아니라, 반시계방향으로 돌았을때의 거리를 구하는 문제여서 복잡했다.

start가 0~n-1일때의 상황에서 각각 반시계방향으로 이동한거리(i)와 위치해야하는 인원(배열값)을 구하여 비교했다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] nums = new int[n];
        for(int i=0; i<n; i++) nums[i] = sc.nextInt();
        
        int min = Integer.MAX_VALUE;
        for(int start=0; start<n; start++ ){ //시작지점 0~n-1의 인덱스
            int sum = 0;
            for(int i=1; i<n; i++){ // n-1회의 이동, 이동횟수 = 이동거리
                int next = (start+i)%n; //시작지점에서 반시계방향의 다음 인덱스
                sum += i * nums[next]; //이동거리*인덱스에 위치해야하는 인원
            }
            //System.out.println(start+" "+sum);
            min = Math.min(min,sum);
        }
        System.out.println(min);
    }
}

 

---

 

[ 응용문제 ] 숨은 단어찾기2

https://www.codetree.ai/missions/5/problems/find-hidden-words-2?&utm_source=clipboard&utm_medium=text

N과 M이 주어지고 또 N * M의 문자열이 주어지면 가로, 세로, 대각선 뱡향으로 도중에 방향을 틀지 않고 인접하여 나오는 ‘LEE’ 의 개수를 구하는 프로그램을 작성해보세요.

첫 번째 줄에 정수 N과 M이 공백을 사이에 두고 주어집니다.
두 번째 줄 부터는 N개의 줄에 걸쳐 길이가 M인 문자열이 한 줄에 하나씩 주어집니다. 주어지는 모든 문자는 알파벳 대문자로만 이루어져 있다고 가정해도 좋습니다.
1 ≤ N, M ≤ 50
첫 번째 줄에 모든 'LEE'의 개수를 출력합니다.

 

예제

4 6
TAEHGI
EELVWE
LEELSE
HBLUEL

 

아래 그림과 같이 'LEE'의 개수는 총 6개 입니다.

 

총 8가지의 경우의 수에 따라 단어를 조합할 수 있다.

가로로 좌우, 세로로 상하, 2개 대각선별 각 2개

같은 선상(방향)에 있는 4가지의 경우의 루프를 만들고 그 방향별로 인덱스와 값을 조정하여 모든 경우를 고려해볼 수 있었다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        char[][] arr = new char[n][m];
        for(int i=0; i<n; i++){
            String str = sc.next();
            for(int j=0; j<m; j++) arr[i][j] = str.charAt(j);
        }

        //가로 : 행고정, 열이 1씩 변화하는 3개
        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m-2; j++){
                if( arr[i][j] == 'L' && arr[i][j+1] == 'E' && arr[i][j+2] == 'E' ) cnt++;
                if( arr[i][j] == 'E' && arr[i][j+1] == 'E' && arr[i][j+2] == 'L' ) cnt++;
            }
        }

        //세로 : 열고정, 행이 1씩 변화하는 3개
        for(int i=0; i<n-2; i++){
            for(int j=0; j<m; j++){
                if( arr[i][j] == 'L' && arr[i+1][j] == 'E' && arr[i+2][j] == 'E' ) cnt++;
                if( arr[i][j] == 'E' && arr[i+1][j] == 'E' && arr[i+2][j] == 'L' ) cnt++;
            }
        }  

        //대각선 : 행과 열이 1씩 감소하는 3개, 행과 열이 1씩 증가하는 3개,
        //      행은 1씩감소, 열은 1씩 증가하는 3개, 행은 1씩 증가 열은 1씩감소
        for(int i=0; i<n-2; i++){
            for(int j=0; j<m-2; j++){
                if( arr[i][j] == 'L' && arr[i+1][j+1] == 'E' && arr[i+2][j+2] == 'E' ) cnt++;
                if( arr[i][j] == 'E' && arr[i+1][j+1] == 'E' && arr[i+2][j+2] == 'L' ) cnt++;

                if( arr[i][j+2] == 'L' && arr[i+1][j+1] == 'E' && arr[i+2][j] == 'E' ) cnt++;
                if( arr[i][j+2] == 'E' && arr[i+1][j+1] == 'E' && arr[i+2][j] == 'L' ) cnt++;

            }
        } 

        System.out.println(cnt);
    }
}

 

---

 

[ 응용문제 ] 오목

https://www.codetree.ai/missions/5/problems/O-mok?&utm_source=clipboard&utm_medium=text

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓으면서 겨루는 게임입니다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있습니다. 가로줄은 위에서부터 아래로 1번, 2번, ..., 19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙습니다.

위 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 됩니다. 여기서 연속적이란 가로, 세로 또는 대각선 방향을 모두 뜻합니다. 즉, 위의 그림은 흰색 바둑알이 이긴 경우입니다.
입력으로 바둑판의 상태가 숫자로 표현되어 주어지면 검은색 바둑알이 이겼는지, 흰색 바둑알이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성해보세요. 단, 검은색 바둑알과 흰색 바둑알이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 주어지지 않습니다.

입력 형식 : 19 * 19 크기의 숫자가 공백을 사이에 두고 주어집니다. 검은색 바둑알은 1, 흰색 바둑알은 2, 그리고 알이 놓이지 않은 자리는 0으로 주어집니다. 단, 같은 색의 알이 연속으로 6번 이상 주어지는 경우는 없다고 가정해도 좋습니다.

출력 형식 : 첫 번째 줄에 승리여부를 출력합니다. 검은색이 이겼을 경우는 1을, 흰색이 이겼을 경우는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력합니다.
두 번째 줄에는 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가운데 위치하고있는 바둑알의 가로줄 번호와, 세로줄 번호를 순서대로 공백을 사이에 두고 출력합니다.

 

예제

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 2 2 2 2 2 0 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

 

문제 설명에 있는 위의 그림과 같이 흰색 바둑알이 승리하였기에 2를 출력한다. 연속된 5개의 바둑알중 가운데 위치한 바둑알의 가로줄 번호는 4이고, 세로줄 번호는 5이다.

 

import java.util.Scanner;

// [n][n]에 위치 = n+1행, n+1행에 위치

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        
        int n = 19;
        int[][] board = new int[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                board[i][j] = sc.nextInt(); //검정돌1, 흰색돌2
            }
        }

        int x = 0; // 가운데 행번호
        int y = 0; // 가운데 열번호
        int win = 0; // 이긴 돌번호

        // 가로 : 행고정, 열1씩 증가
        for(int i=0; i<n; i++){
            for(int j=0; j<=n-5; j++){
                if( board[i][j] != 0 && board[i][j] == board[i][j+1] && 
                board[i][j+1] == board[i][j+2] && board[i][j+2] == board[i][j+3] && 
                board[i][j+3] == board[i][j+4] ){
                    win = board[i][j];
                    x = i;
                    y = j+2;
                }
            }
        }
        
        // 세로 : 열고정, 행1씩 증가
        for(int i=0; i<=n-5; i++){
            for(int j=0; j<n; j++){
                if( board[i][j] != 0 && board[i][j] == board[i+1][j] &&
                board[i+1][j] == board[i+2][j] && board[i+2][j] == board[i+3][j] &&
                board[i+3][j] == board[i+4][j] ){
                    win = board[i][j];
                    x = i+2;
                    y = j;
                }
            }
        }
        
        // 대각선(/) : 행1씩증가, 열1씩증가 & 행1씩감소, 열1씩감소(V)
        for(int i=4; i<n; i++){
            for(int j=4; j<n; j++){
                if( board[i][j] != 0 && board[i][j] == board[i-1][j-1] &&
                board[i-1][j-1] == board[i-2][j-2] && board[i-2][j-2] == board[i-3][j-3] &&
                board[i-3][j-3] == board[i-4][j-4] ){
                    win = board[i][j];
                    x = i-2;
                    y = j-2;
                }
            }
        }

        // 대각선(\) : 행1씩감소, 열1씩증가(V) & 행1씩증가, 열1씩감소
        for(int i=4; i<n; i++){
            for(int j=0; j<=n-5; j++){
                if( board[i][j] != 0 && board[i][j] == board[i-1][j+1] &&
                board[i-1][j+1] == board[i-2][j+2] && board[i-2][j+2] == board[i-3][j+3] &&
                board[i-3][j+3] == board[i-4][j+4] ){
                    win = board[i][j];
                    x = i-2;
                    y = j+2;
                }
            }
        }

        System.out.println(win);
        x++;
        y++;
        if(win != 0) System.out.println(x+" "+y);
    }
}