백준 9663번 N-Queen

문제

나의 풀이

import java.util.*;;

public class Main {
    static boolean a[][] = new boolean[15][15];
    static int n;
    static boolean check_col[] = new boolean[15];
    static boolean check_dig[] = new boolean[40];
    static boolean check_dig2[] = new boolean[40];
    static boolean check(int row, int col) {
        // |
        if(check_col[col]) {
            return false;
        }
        // 왼쪽 위 대각선
        if(check_dig[row + col]) {
            return false;
        }
        // /
        if(check_dig2[row - col + n]) {
            return false;
        }
        return true;
    }
    static int calc(int row) {
        if(row == n) { // 퀸을 모두 놓은 경우
            return 1;
        }
        int count = 0;
        for(int col = 0; col < n; col++) {
            if(check(row, col)) { // 놓을 수 있는 경우
                check_dig[row + col] = true;
                check_dig2[row - col + n] = true;
                check_col[col] = true;
                a[row][col] = true; // 퀸을 놓음
                count += calc(row + 1); // 재귀 호출
                check_dig[row + col] = false; 
                check_dig2[row - col + n] = false;
                check_col[col] = false; 
                a[row][col] = false; // 백트래킹
            }
        }
        return count; // 방법의 수 리턴
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        System.out.println(calc(0));
    }
}

calc 함수는 row 행에 퀸을 어디에 놓을지 결정하는 함수다.
row가 n일 때 모든 행에 퀸을 놓은 것이므로 정답을 1 추가한다.
check_col[i] = i번 열에 퀸이 놓여져 있으면 true를 나타낸다.
check_dig[i] = / 대각선에 퀸이 있으면 true를 나타낸다.
check_dig2[i] = \ 대각선에 퀸이 있으면 true를 나타낸다.
check 부분을 배열을 이용하면 놓을 수 있는지 검사를 O(1)만에 해결할 수 있기 때문에 3가지 배열을 이용하였다.

결과

백준 1987번 알파벳

문제

나의 풀이

import java.util.*;

public class Main {
    public static final int dx[] = {0, 0, 1, -1};
    public static final int dy[] = {1, -1, 0, 0};
    public static int go(String board[], boolean check[], int x, int y) {
        int answer = 0;
        for(int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length()) {
                if(check[board[nx].charAt(ny) - 'A'] == false) { // 다음 칸의 알파벳을 방문한 적이 없을 때
                    check[board[nx].charAt(ny) - 'A'] = true; // 방문 표시
                    int next = go(board, check, nx, ny);
                    answer = Math.max(answer, next); // 최대값 구하기
                    check[board[nx].charAt(ny) - 'A'] = false; // 백트래킹
                }
            }
        }
        return answer + 1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        String board[] = new String[n];
        for(int i = 0; i < n; i++) {
            board[i] = sc.nextLine();
        }
        boolean check[] = new boolean[26];
        check[board[0].charAt(0) - 'A'] = true; // 방문 표시
        System.out.println(go(board, check, 0, 0)); 
    }
}

go 함수의 매개변수 board는 보드, check는 방문한 알파벳, (x,y)는 현재 위치를 뜻한다. 리턴 값은 방문할 수 있는 칸의 최대 개수이다.
다음칸에 대하여 범위 안에 있으면서 이동하려는 칸의 알파벳을 방문한 적이 없을 때 방문하고 백트래킹을 해준다.

결과

인프런 현관문 출입 순서

문제

나의 풀이

import java.util.*;

public class EntryOrder {
    public static int[] solution(int arrival[], int state[]) {
        Queue<Integer> enter = new LinkedList<>();
        Queue<Integer> exit = new LinkedList<>();
        int n = arrival.length, prev = 1; // 앞초에 사원이 나갔는지 들어왔는지 여부 표시
        int answer[] = new int[n];
        for(int t = 0, i = 0, count = 0; ; t++) { // 시간을 기준으로 시뮬
            if(enter.isEmpty() && exit.isEmpty() && i < n) { // 대기하는 사람이 없으면서 아직 사원이 남았을 때
                if(t < arrival[i]) { // 다음 현관문에 도착할 사원의 시간 보다 현재 시간이 작은 경우
                    t = arrival[i]; // 그 시간으로 건너뛰기
                    prev = 1; // 나가는 사원 우선으로 하게
                }
            }
            while(i < n && arrival[i] <= t) { // 현재 시간에 현관문을 사용한 사원들이 있을 때 까지
                if(state[i] == 0) { // 들어오는 경우
                    enter.offer(i);
                } else { // 나가는 경우
                    exit.offer(i);
                }
                i++; // 인덱스 증가
            }
            if(prev == 1) { // 나가는 사원 우선인 경우
                if(!exit.isEmpty()) { // 나가는 사원 대기열이 비어있지 않은 경우
                    answer[exit.poll()] = t; // 사원 인덱스에 사용 시간 적어주기
                    prev = 1;
                } else { // 비어있는 경우
                    answer[enter.poll()] = t; // 들어오는 사원 인덱스에 사용 시간 적어주기
                    prev = 0;
                }
            } else if(prev == 0) { // 들어오는 사원 우선인 경우
                if(!enter.isEmpty()) { // 비어있지 않은 경우
                    answer[enter.poll()] = t;
                    prev = 0;
                } else { // 비어있는 경우
                    answer[exit.poll()] = t;
                    prev = 1;
                }
            }
            count++; // 현관문 이용한 사원 수 증가
            if(count == n) { // 전 사원이 현관문 사용했을 때
                break;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(EntryOrder.solution(new int[]{0, 1, 1, 1, 2, 3, 8, 8}, new int[]{1, 0, 0, 1, 0, 0, 1, 0})));
        System.out.println(Arrays.toString(EntryOrder.solution(new int[]{3, 3, 4, 5, 5, 5}, new int[]{1, 0, 1, 0, 1, 0})));
        System.out.println(Arrays.toString(EntryOrder.solution(new int[]{2, 2, 2, 3, 4, 8, 8, 9, 10, 10}, new int[]{1, 0, 0, 0, 1, 1, 0, 1, 1, 0})));
    }
}

큐 2개를 이용하여 시뮬레이션을 구현한다.

결과