코딩가딩가딩

Programming/JAVA

[백준] 단계별로 풀어보기 > 백트래킹 (java)

코딩뽀시래기 2022. 1. 26. 14:47
728x90

+) 풀이 코드

https://github.com/jung0115/CodingTestPractice.git

 

GitHub - jung0115/CodingTestPractice: Practice Coding Test with Beakjoon, programmers, etc.

Practice Coding Test with Beakjoon, programmers, etc. - GitHub - jung0115/CodingTestPractice: Practice Coding Test with Beakjoon, programmers, etc.

github.com

 

+) 백준에 Java 코드를 제출할 때는 class명을 Main으로 해주어야 오류가 발생하지 않는다.

 

15649번 - 2022.01.26.수

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        int[] num = new int[M];
        StringBuilder printSet = new StringBuilder();
        printSet = NandM(N, M, 0, num);
        System.out.println(printSet);
    }
    static StringBuilder NandM(int N, int M, int cnt, int[] num) {
        StringBuilder sequence = new StringBuilder();
        
        for(int i = 0; i < cnt-1; i++) //수열 중 겹치는 수가 있을 경우
            if(num[cnt-1] == num[i]) return sequence;
        
        if(cnt == M) { //수열 완성
            for(int i = 0; i < M; i++)
                sequence.append(num[i]).append(" ");
            sequence.append("\n");
            return sequence;
        }

        for(int i = 1; i <= N; i++) {
            int[] next = new int[M];
            for(int j = 0; j < cnt; j++)
                next[j] = num[j];
            next[cnt] = i;
            sequence.append(NandM(N, M, cnt+1, next));
        }
        return sequence;
    }
}

 

15650번 - 2022.01.26.수

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] num = new int[M];
        StringBuilder printSet = new StringBuilder();
        printSet = NandM(N, M, 0, num);
        System.out.println(printSet);
    }
    static StringBuilder NandM(int N, int M, int cnt, int[] num) {
        StringBuilder sequence = new StringBuilder();
        
        for(int i = 0; i < cnt-1; i++) //수열 중 겹치는 수가 있거나 오름차순이 아닌 경우
            if(num[cnt-1] <= num[i]) return sequence;
        
        if(cnt == M) { //수열 완성
            for(int i = 0; i < M; i++)
                sequence.append(num[i]).append(" ");
            sequence.append("\n");
            return sequence;
        }

        for(int i = 1; i <= N; i++) {
            int[] next = new int[M];
            for(int j = 0; j < cnt; j++)
                next[j] = num[j];
            next[cnt] = i;
            sequence.append(NandM(N, M, cnt+1, next));
        }
        return sequence;
    }
}

 

15651번 - 2022.01.26.수

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] num = new int[M];
        StringBuilder printSet = new StringBuilder();
        printSet = NandM(N, M, 0, num);
        System.out.println(printSet);
    }
    static StringBuilder NandM(int N, int M, int cnt, int[] num) {
        StringBuilder sequence = new StringBuilder();
        
        if(cnt == M) { //수열 완성
            for(int i = 0; i < M; i++)
                sequence.append(num[i]).append(" ");
            sequence.append("\n");
            return sequence;
        }

        for(int i = 1; i <= N; i++) {
            int[] next = new int[M];
            for(int j = 0; j < cnt; j++)
                next[j] = num[j];
            next[cnt] = i;
            sequence.append(NandM(N, M, cnt+1, next));
        }
        return sequence;
    }
}

 

15651번 - 2022.01.26.수

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] num = new int[M];
        StringBuilder printSet = new StringBuilder();
        printSet = NandM(N, M, 0, num);
        System.out.println(printSet);
    }
    static StringBuilder NandM(int N, int M, int cnt, int[] num) {
        StringBuilder sequence = new StringBuilder();
        
        for(int i = 0; i < cnt-1; i++) //수열이 비내림차순이 아닌 경우
            if(num[cnt-1] < num[i]) return sequence;
        
        if(cnt == M) { //수열 완성
            for(int i = 0; i < M; i++)
                sequence.append(num[i]).append(" ");
            sequence.append("\n");
            return sequence;
        }

        for(int i = 1; i <= N; i++) {
            int[] next = new int[M];
            for(int j = 0; j < cnt; j++)
                next[j] = num[j];
            next[cnt] = i;
            sequence.append(NandM(N, M, cnt+1, next));
        }
        return sequence;
    }
}

 

9663번 - 2022.01.27.목

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        
        int[][] chess = new int[N][2];
        int result = Nqueen(N, chess, 0);
        System.out.println(result);
    }
    static int Nqueen(int N, int[][] chess, int cnt) {
        for(int i = 0; i < cnt-1; i++) {
            if(chess[cnt-1][0] == chess[i][0]) return 0; //위아래(수직)으로 공격할 수 있는 경우
            if(Math.abs(chess[cnt-1][0]-chess[i][0]) == Math.abs(chess[cnt-1][1]-chess[i][1])) return 0; //대각선으로 이동해 공격할 수 있는 경우
        }
        
        if(cnt == N) { //퀸 N개를 서로 공격하지 못하도록 놓은 경우(성공)
            return 1;
        }

        //한 행에 퀸이 하나씩 위치할 수 있다는 점을 이용
        int correct = 0;
        for(int i = 0; i < N ; i++) {
            chess[cnt][0] = i;
            chess[cnt][1] = cnt;
            correct += Nqueen(N, chess, cnt+1);
        }
        
        return correct;
    }
}

배열을 메소드의 매개변수로 보내면 주소값이 전달되는 걸로 알고 있어서 재귀함수 때문에 배열 내용이 얽힐까봐 위의 15649~15652번 문제처럼 일일히 배열을 다시 만들어서(값 복사) 매개변수로 넘겨줬었다. 그랬더니 채점결과가 메모리 초과라고 나왔다... 혹시 복사를 안 하고 그냥 넘겨줘도 답이 제대로 나올까 싶어서 해봤는데 제대로 나온다... 나는 지금까지 왜 열심히 배열을 복사했는가... 아무튼 위의 4문제도 배열 값 복사하는 부분을 삭제해도 제대로 답이 나올 것이다.

 

2580번 - 2022.01.27.목 (틀림)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int[][] sudoku = new int[9][9];
        for(int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for(int j = 0; j < 9; j++)
                sudoku[i][j] = Integer.parseInt(st.nextToken());
        }

        findAnswer(sudoku, 0, 0);
    }
    static boolean findAnswer(int[][] sudoku, int x, int y) {
        if(x != 0 || y != 0) { //첫 시작 때는 건너뛰기
            for(int i = 0; i < 9; i++) {
                if((sudoku[i][y] == sudoku[x][y]) && i != x && sudoku[i][y] != 0) return false; //같은 열(수직)에 있는 수와 같은 수인 경우
                if((sudoku[x][i] == sudoku[x][y]) && i != y && sudoku[x][i] != 0) return false; //같은 행(수평)에 있는 수와 같은 수인 경우
            }
            int checkX = (x/3)*3;
            int checkY = (y/3)*3;
            for(int i = checkX; i < checkX+3; i++) {
                for(int j = checkY; j < checkY+3; j++)
                    if((sudoku[i][j] == sudoku[x][y]) && i != x && j != y && sudoku[i][j] != 0) return false; //같은 3*3 정사각형 박스 안에 있는 수와 같은 수인 경우
            }

            if(x == 8 && y == 8) { //스도쿠 완성
                printSudoku(sudoku);
                return true;
            }
            x += y/8;
            y = (y+1)%8;
            if(y != 0) {
                for(int i = y; i < 9; i++) {
                    if(sudoku[x][i] == 0) {
                        for(int j = 1; j <= 9; j++) {
                            sudoku[x][i] = j;
                            if(findAnswer(sudoku, x, i)) return true;
                        }
                    }
                }
                y = 0;
                x++;
            }
        }
        
        for(int i = x; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(sudoku[i][j] == 0) {
                    for(int k = 1; k <= 9; k++) {
                        sudoku[i][j] = k;
                        if(findAnswer(sudoku, i, j)) return true;
                    }
                }
            }
        }
        return false;
    }
    static void printSudoku(int[][] sudoku) { //출력
        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) 
                printSet.append(sudoku[i][j]).append(" ");
            printSet.append("\n");
        }
        System.out.print(printSet);
    }
}

이렇게 하면 될 것 같았는데... 왜 틀렸다고 나오는지는 잘 모르겠다 검색해서 나오는 답이랑 논리는 비슷한데 뭔가 잘못된 부분이 있는 것 같다. 이걸 고쳐서 해결해보려고 했지만 더 망해버렸... 그냥 해답으로 찾은 방법을 따라가야겠다.

 

2580번 - 2022.01.27.목 (정답)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
    static int[][] sudoku = new int[9][9];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        for(int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for(int j = 0; j < 9; j++)
                sudoku[i][j] = Integer.parseInt(st.nextToken());
        }

        findAnswer(0, 0);
    }
    static void findAnswer(int x, int y) {
        if(y == 9) { //해당 행이 다 채워졌을 경우 다음 행으로
            findAnswer(x+1, 0);
            return;
        }
        if(x == 9) { //모든 칸이 다 채워졌을 경우 출력 후 종료
            printSudoku();
            System.exit(0); //시스템 종료
        }

        if(sudoku[x][y] == 0) { //해당 칸이 비어있는 경우
            for(int i = 1; i <= 9; i++) {
                if(checkCorrect(x, y, i)) {
                    sudoku[x][y] = i;
                    findAnswer(x, y+1);
                }
            }
            sudoku[x][y] = 0; //정답이 아니었던 경우
            return;
        }

        findAnswer(x, y+1);
    }
    static boolean checkCorrect(int x, int y, int value) { //value 값이 (x,y)에 들어가도 되는지 검사
        for(int i = 0; i < 9; i++) {
            if(sudoku[x][i] == value) return false; //같은 행에 이미 해당 숫자가 있는 경우
            if(sudoku[i][y] == value) return false; //같은 열에 이미 해당 숫자가 있는 경우
        }
        int checkX = (x/3)*3;
        int checkY = (y/3)*3;
        for(int i = checkX; i < checkX+3; i++) {
            for(int j = checkY; j < checkY+3; j++)
                if(sudoku[i][j] == value) return false; //같은 3*3 사각형 칸에 해당 숫자가 있는 경우
        }
        return true;
    }
    static void printSudoku() { //출력
        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) 
                printSet.append(sudoku[i][j]).append(" ");
            printSet.append("\n");
        }
        System.out.print(printSet);
    }
}

 

14888번 - 2022.02.07.월

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
    static int max = -1000000000; //최대
    static int min = 1000000000; //최소
    static int[] nums; //수열
    static int[] operators = new int[4]; //연산자
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        nums = new int[N];
        StringTokenizer st1 = new StringTokenizer(bf.readLine());
        StringTokenizer st2 = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++) //수열
            nums[i] = Integer.parseInt(st1.nextToken());
        for(int i = 0; i < 4; i++) //연산자
            operators[i] = Integer.parseInt(st2.nextToken());
        
        calculation(N, 1, nums[0]);

        StringBuilder printSet = new StringBuilder();
        printSet.append(max).append("\n").append(min);
        System.out.print(printSet);
    }
    static void calculation(int N, int cnt, int cal) {
        if(cnt == N) { //계산이 끝났을 때
            if(max < cal) max = cal; //최대값보다 큰 수일 경우
            if(min > cal) min = cal; //최소값보다 작은 수일 경우
            return;
        }

        for(int i = 0; i < 4; i++) {
            if(operators[i] == 0) continue; //해당 연산자를 모두 사용했거나 할당되지 않은 경우
            operators[i]--;
            int setCal = calculate(cal, nums[cnt], i);
            calculation(N, cnt+1, setCal);
            operators[i]++;
        }
    }
    static int calculate(int cal, int num, int operator) {
        if(operator == 0) return cal + num;
        if(operator == 1) return cal - num;
        if(operator == 2) return cal * num;
        return cal / num;
    }
}

 

14889번 - 2022.02.08.화

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.lang.Math;
public class Main {
    static int[][] skillScore;
    static int min = 1000000; //능력치 차이 최소값
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        skillScore = new int[N][N];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for(int j = 0; j < N; j++) {
                skillScore[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[] start = new int[N/2];
        startAndLink(N, start, 0);
        System.out.print(min);
    }
    static void startAndLink(int N, int[] start, int cnt) {
        if(cnt == N/2) {
            int scoreSub = calculateScore(N, start);
            if(scoreSub < min){
                min = scoreSub;
            }
            return;
        }

        int startI =0;
        if(cnt != 0) startI = start[cnt-1]+1;
        for(int i = startI; i < N; i++) {
            start[cnt] = i;
            startAndLink(N, start, cnt+1);
        }
    }
    static int calculateScore(int N, int[] start) {
        int[] link = new int[N/2];
        int cntS = 0, cntL = 0;
        for(int i = 0; i < N; i++) {
            if(cntS == N/2 || start[cntS] != i) {
                link[cntL] = i;
                cntL++;
                if(cntL == N/2) break;
            }
            else cntS++;
        }

        //스타트 팀의 능력치 계산
        int startScore = 0;
        for(int i = 0; i < N/2; i++) {
            for(int j = i+1; j < N/2; j++) {
                startScore += skillScore[start[i]][start[j]];
                startScore += skillScore[start[j]][start[i]];
            }
        }

        //링크 팀의 능력치 계산
        int linkScore = 0;
        for(int i = 0; i < N/2; i++) {
            for(int j = i+1; j < N/2; j++) {
                linkScore += skillScore[link[i]][link[j]];
                linkScore += skillScore[link[j]][link[i]];
            }
        }
        
        return Math.abs(startScore - linkScore); //스타트 팀과 링크 팀의 능력치 차 반환
    }
}

 

728x90
저작자표시 비영리 변경금지

'Programming > JAVA' 카테고리의 다른 글

[백준] 단계별로 풀어보기 > 동적 계획법 1 (java)  (0) 2022.02.08
[백준] 단계별로 풀어보기 > 입출력과 사칙연산 (java)  (0) 2022.02.06
[Java] LinkedList  (0) 2022.01.21
[Java] StringBuilder로 출력하기  (0) 2022.01.21
[Java] BufferedReader로 입력 받기  (0) 2022.01.21

'Programming/JAVA'의 다른글

  • 현재글[백준] 단계별로 풀어보기 > 백트래킹 (java)

관련글

댓글

티스토리툴바