[백준/BOJ] 1014 컨닝 - JAVA

백준 BOJ 1014 컨닝 - JAVA - 플래4

문제

https://www.acmicpc.net/problem/1014

문제 분석

조건

• N행, M열로 배치된 좌석에서 컨닝을 못하도록 배치할 수 있는 최대 학생 수 구하기
• 앞줄의 대각선, 좌우에 학생이 있을 경우 컨닝을 할 수 있음
• 부서진 자리에는 앉을 수 없다.

컨닝 가능한 위치

풀이방법

• 불 끄기 문제와 비슷하게 접근하였다.(앞 행이 결정되면 뒷 행이 영향을 받음)
  • 앞행이 결정되더라도 뒷줄이 여러가지 경우의 수가 나올 수 있다는 점이 다름

[백준/BOJ] 14939 불 끄기 - JAVA

[백준/BOJ] 14939 불 끄기 - JAVA

• 비트마스킹을 활용하여 M을 입력받으면 한 줄에 배치할 수 있는 방법은 `(1 << M)`개이다.
  • 이때 연속하게 앉게 될 경우 양 옆자리는 컨닝을 할 수 있으므로 배치가 불가능하다.
  • 교실의 가로 길이가 일정하다. 따라서 한 줄에 앉을 수 있는 방법은 동일하므로 미리 앉을 수 있는 방법을 저장해두고 각 행마다 해당 방법으로 앉혔을 경우 부서진 자리에 앉는지, 컨닝이 가능한지 확인한다.
• DP를 사용하여 배치할 수 있는 최대값을 찾는다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class SeatCase {
    private int seats;
    private int count;

    public SeatCase(int seats, int count) {
        this.seats = seats;
        this.count = count;
    }

    public int getSeats() {
        return seats;
    }

    public int getCount() {
        return count;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            st = new StringTokenizer(br.readLine());
            int R = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            int max = 1 << C;
            int[][] dp = new int[R + 1][max];
            char[][] map = new char[R + 1][C];
            for (int r = 1; r <= R; r++) {
                String line = br.readLine();
                for (int c = 0; c < C; c++) {
                    map[r][c] = line.charAt(c);
                }
            }

            //한 행에 가능한 자리 배치 구하기
            List<SeatCase> seatCaseList = new ArrayList<>();
            for (int seatCase = 0; seatCase < max; seatCase++) {
                if (sideCheck(seatCase)) {//인접한 자리에 앉는지 확인
                    int count = 0;
                    for (int i = 0; i < C; i++) {//앉은사람 수 카운트
                        if ((seatCase & (1 << i)) != 0) {
                            count++;
                        }
                    }
                    seatCaseList.add(new SeatCase(seatCase, count));
                }
            }

            int answer = 0;

            //앞 줄부터 앉히기
            for (int r = 1; r <= R; r++) {
                for (SeatCase seatCase : seatCaseList) {
                    //앉아야 하는 자리에 의자가 부서지지 않았는지 확인
                    if (chairCheck(seatCase.getSeats(), map[r])) {
                        //앞 자리랑 대각선인지 확인
                        for (SeatCase frontCase : seatCaseList) {
                            if (sideCheck(frontCase.getSeats() | seatCase.getSeats())) {
                                dp[r][seatCase.getSeats()] = Math.max(dp[r][seatCase.getSeats()], dp[r - 1][frontCase.getSeats()] + seatCase.getCount());
                                answer = Math.max(answer, dp[r][seatCase.getSeats()]);
                            }
                        }
                    }
                }
            }
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }


    /**
     * 의자 앉을수있는지 확인
     */
    private static boolean chairCheck(int seats, char[] seat) {
        for (int i = seat.length - 1, chairNum = 0; i >= 0; i--, chairNum++) {
            if (((1 << i) & seats) != 0) {
                if (seat[chairNum] == 'x') {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 연속된 자리에 앉는지 확인
     */
    private static boolean sideCheck(int seatCase) {
        int test = 0;
        for (int i = 0; test <= seatCase; i++) {
            test = 3 << i;
            if ((seatCase & test) == test) {
                return false;
            }
        }
        return true;
    }
}

결과