Java/백준
[Java][15683] 감시
tmd1
2022. 10. 5. 22:26
문제:
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
코드:
import java.util.*;
public class Main {
public static int n,m;
public static int [][] arr = new int[8][8];
public static int [][] check = new int[8][8];
public static boolean isIn(int x, int y){
// 범위 외일 경우 true, 아니면 false;
return (x < 0 || x >= n) || (y < 0 || y >= m);
}
public static void Up(int x,int y){
for(int j=1;j<=8;j++){
int nx = x-j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(check[nx][y] != 0) continue; // 이미 true 라면 넘김
check[nx][y] = 7;
}
}
public static void Down(int x, int y){
for(int j=1;j<=8;j++){
int nx = x+j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(check[nx][y] != 0) continue; // 이미 true 라면 넘김
check[nx][y] = 7;
}
}
public static void Left(int x,int y){
for(int j=1;j<=8;j++){
int ny = y-j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(check[x][ny] != 0) continue; // 이미 true 라면 넘김
check[x][ny] = 7;
}
}
public static void Right(int x,int y){
for(int j=1;j<=8;j++){
int ny = y+j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(check[x][ny] != 0) continue; // 이미 true 라면 넘김
check[x][ny] = 7;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
ArrayList<Pos> q = new ArrayList<>();
// 큐에 cctv 있는 부분의 좌표를 하나씩 저장
// cctv,벽 있는 부분을 true
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int k = sc.nextInt();
if (k != 0 && k != 6) {
q.add(new Pos(i,j)); // cctv 좌표 저장
check[i][j] = 7;
}
arr[i][j] = k;
}
}
int pow = (int)Math.pow(4,q.size());
int ans = Integer.MAX_VALUE;
for(int tmp = 0; tmp<pow;tmp++){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
check[i][j] = arr[i][j];
}
}
int brute = tmp;
for(int i=0;i<q.size();i++){
int dir = brute%4;
brute /= 4;
if(arr[q.get(i).x][q.get(i).y] == 1){ // 4방향
if(dir == 0){ // 위 방향
Up(q.get(i).x,q.get(i).y);
}else if(dir == 1){ // 오른
Right(q.get(i).x,q.get(i).y);
}else if(dir == 2){ // 아래
Down(q.get(i).x,q.get(i).y);
}else{ // 왼
Left(q.get(i).x,q.get(i).y);
}
}else if(arr[q.get(i).x][q.get(i).y] == 2){ // 2방향
if(dir == 1 || dir == 3){ // 양 옆
Left(q.get(i).x,q.get(i).y);
Right(q.get(i).x,q.get(i).y);
}else{
Up(q.get(i).x,q.get(i).y);
Down(q.get(i).x,q.get(i).y);
}
}else if(arr[q.get(i).x][q.get(i).y] == 3){ // 4방향
if(dir == 0){ // 위,오른
Up(q.get(i).x,q.get(i).y);
Right(q.get(i).x,q.get(i).y);
}else if(dir == 1){ // 오른, 아래
Right(q.get(i).x,q.get(i).y);
Down(q.get(i).x,q.get(i).y);
}else if(dir == 2){ // 아래,왼
Down(q.get(i).x,q.get(i).y);
Left(q.get(i).x,q.get(i).y);
}else{ // 왼 , 위
Left(q.get(i).x,q.get(i).y);
Up(q.get(i).x,q.get(i).y);
}
}else if(arr[q.get(i).x][q.get(i).y] == 4){ // 4방향
if(dir == 0){ // 위, 양옆
Up(q.get(i).x,q.get(i).y);
Left(q.get(i).x,q.get(i).y);
Right(q.get(i).x,q.get(i).y);
}else if(dir == 1){ // 오른, 위아래
Right(q.get(i).x,q.get(i).y);
Up(q.get(i).x,q.get(i).y);
Down(q.get(i).x,q.get(i).y);
}else if(dir == 2){ // 아래 양옆
Down(q.get(i).x,q.get(i).y);
Left(q.get(i).x,q.get(i).y);
Right(q.get(i).x,q.get(i).y);
}else{ // 왼 , 위아래
Left(q.get(i).x,q.get(i).y);
Up(q.get(i).x,q.get(i).y);
Down(q.get(i).x,q.get(i).y);
}
}else{
Up(q.get(i).x,q.get(i).y);
Down(q.get(i).x,q.get(i).y);
Left(q.get(i).x,q.get(i).y);
Right(q.get(i).x,q.get(i).y);
}
}
int cnt = 0;
for(int i=0;i<n;i++) {
for(int j =0;j<m;j++) {
if (check[i][j] == 0) {
cnt++;
}
}
}
ans = Math.min(ans,cnt);
}
/*
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
System.out.print(check[i][j]+" ");
}
System.out.println();
}
*/
System.out.println(ans);
}
}
class Pos{
int x;
int y;
Pos(int x, int y){
this.x =x;
this.y =y;
}
}
모든 방향에 대한 경우의 수를 다 따져보고 사각지대 개수를 세는 방식으로 푼다
------------------------------------------------------------------------------------------------------------------------
아래는 쉽게 풀려다가 산으로 가버린 풀이...
import java.util.*;
public class Main {
public static int n,m;
public static int [][] arr = new int[8][8];
public static boolean [][] check = new boolean[8][8];
public static boolean isIn(int x, int y){
// 범위 외일 경우 true, 아니면 false;
return (x < 0 || x >= n) || (y < 0 || y >= m);
}
public static void Up(int x,int y){
for(int j=1;j<=8;j++){
int nx = x-j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(check[nx][y]) continue; // 이미 true 라면 넘김
check[nx][y] = true;
}
}
public static void Down(int x, int y){
for(int j=1;j<=8;j++){
int nx = x+j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(check[nx][y]) continue; // 이미 true 라면 넘김
check[nx][y] = true;
}
}
public static void Left(int x,int y){
for(int j=1;j<=8;j++){
int ny = y-j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(check[x][ny]) continue; // 이미 true 라면 넘김
check[x][ny] = true;
}
}
public static void Right(int x,int y){
for(int j=1;j<=8;j++){
int ny = y+j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(check[x][ny]) continue; // 이미 true 라면 넘김
check[x][ny] = true;
}
}
public static int direction_1(int x, int y){
int cnt = 0; // 볼 수 있는 부분 개수
int maxCnt = -1;
int maxIdx = -1; // 최종 방향
for(int i=0;i<4;i++){
for(int j=1;j<=8;j++){
if(i == 0){ // 위
int nx = x-j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}else if(i == 1){ // 오른
int ny = y+j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}else if(i == 2){ // 아래
int nx = x+j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}else{ // 왼
int ny = y-j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
}
if(cnt > maxCnt){
maxCnt = cnt;
maxIdx = i;
}
cnt = 0;
}
return maxIdx;
}
public static int direction_2(int x, int y){
int cnt = 0; // 볼 수 있는 부분 개수
int maxCnt = -1;
int maxIdx = -1; // 최종 방향
for(int i=0;i<2;i++){
if(i == 0){ // 옆
for(int j=1;j<=8;j++){ // 왼
int ny = y-j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 오
int ny = y+j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
}else if(i == 1){ // 위
for(int j=1;j<=8;j++){ // 위
int nx = x-j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 아래
int nx = x+j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
}
if(cnt > maxCnt){
maxCnt = cnt;
maxIdx = i;
}
cnt = 0;
}
return maxIdx;
}
public static int direction_3(int x, int y){
int cnt = 0; // 볼 수 있는 부분 개수
int maxCnt = -1;
int maxIdx = -1; // 최종 방향
for(int i=0;i<4;i++){
if(i == 0){ // 위,오른
for(int j=1;j<=8;j++){
int nx = x-j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
for(int j=1;j<=8;j++){
int ny = y+j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
}else if(i == 1){ // 오른,아래
for(int j=1;j<=8;j++){
int nx = x+j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
for(int j=1;j<=8;j++){
int ny = y+j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
}else if(i == 2){ // 왼,아래
for(int j=1;j<=8;j++){
int nx = x+j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
for(int j=1;j<=8;j++){
int ny = y-j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
}else{ // 왼, 위
for(int j=1;j<=8;j++){
int nx = x-j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
for(int j=1;j<=8;j++){
int ny = y-j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
}
if(cnt > maxCnt){
maxCnt = cnt;
maxIdx = i;
}
cnt = 0;
}
return maxIdx;
}
public static int direction_4(int x, int y){
int cnt = 0; // 볼 수 있는 부분 개수
int maxCnt = -1;
int maxIdx = -1; // 최종 방향
for(int i=0;i<4;i++){
if(i == 0){ // 위
for(int j=1;j<=8;j++){
int nx = x-j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 왼
int ny = y-j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 오
int ny = y+j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
}else if(i == 1){ // 오른
for(int j=1;j<=8;j++){
int ny = y+j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 위
int nx = x+j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 아래
int nx = x-j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
}else if(i == 2){ // 아래
for(int j=1;j<=8;j++){
int nx = x+j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 왼
int ny = y-j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 오
int ny = y+j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
}else{ // 왼
for(int j=1;j<=8;j++){
int ny = y-j;
if(isIn(x,ny)) continue; // 범위 외라면
if(arr[x][ny] == 6) break; // 6이면 빠져나감
if(arr[x][ny] != 0) continue; // 0이 아닐경우
if(check[x][ny]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 위
int nx = x+j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
for(int j=1;j<=8;j++){ // 아래
int nx = x-j;
if(isIn(nx,y)) continue; // 범위 외라면
if(arr[nx][y] == 6) break; // 6이면 빠져나감
if(arr[nx][y] != 0) continue; // 0이 아닐경우
if(check[nx][y]) continue;
cnt++;
}
}
if(cnt > maxCnt){
maxCnt = cnt;
maxIdx = i;
}
cnt = 0;
}
return maxIdx;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Queue<Pos> q = new LinkedList<>();
Queue<Pos> q1 = new LinkedList<>();
// 큐에 cctv 있는 부분의 좌표를 하나씩 저장
// cctv,벽 있는 부분을 true
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int k = sc.nextInt();
if (k != 0 && k != 6 && k != 5) {
q.add(new Pos(i,j));
check[i][j] = true;
}
if(k == 5){
q1.add(new Pos(i,j));
check[i][j] = true;
}
if(k == 6) check[i][j] = true;
arr[i][j] = k;
}
}
while(!q1.isEmpty()){
Pos cur = q1.poll();
Up(cur.x,cur.y);
Down(cur.x,cur.y);
Left(cur.x,cur.y);
Right(cur.x,cur.y);
}
while(!q.isEmpty()){
Pos cur = q.poll();
if(arr[cur.x][cur.y] == 1){ // 4방향
if(direction_1(cur.x,cur.y) == 0){ // 위 방향
Up(cur.x,cur.y);
}else if(direction_1(cur.x,cur.y) == 1){ // 오른
Right(cur.x,cur.y);
}else if(direction_1(cur.x,cur.y) == 2){ // 아래
Down(cur.x,cur.y);
}else{ // 왼
Left(cur.x,cur.y);
}
}else if(arr[cur.x][cur.y] == 2){ // 2방향
if(direction_2(cur.x,cur.y) == 0){ // 양 옆
Left(cur.x,cur.y);
Right(cur.x,cur.y);
}else{
Up(cur.x,cur.y);
Down(cur.x,cur.y);
}
}else if(arr[cur.x][cur.y] == 3){ // 4방향
if(direction_3(cur.x,cur.y) == 0){ // 위,오른
Up(cur.x,cur.y);
Right(cur.x,cur.y);
}else if(direction_3(cur.x,cur.y) == 1){ // 오른, 아래
Right(cur.x,cur.y);
Down(cur.x,cur.y);
}else if(direction_3(cur.x,cur.y) == 2){ // 왼,아래
Left(cur.x,cur.y);
Down(cur.x,cur.y);
}else{ // 왼 , 위
Left(cur.x,cur.y);
Up(cur.x,cur.y);
}
}else if(arr[cur.x][cur.y] == 4){ // 4방향
if(direction_4(cur.x,cur.y) == 0){ // 위, 양옆
Up(cur.x,cur.y);
Left(cur.x,cur.y);
Right(cur.x,cur.y);
}else if(direction_4(cur.x,cur.y) == 1){ // 오른, 위아래
Right(cur.x,cur.y);
Up(cur.x,cur.y);
Down(cur.x,cur.y);
}else if(direction_4(cur.x,cur.y) == 2){ // 아래 양옆
Down(cur.x,cur.y);
Left(cur.x,cur.y);
Right(cur.x,cur.y);
}else{ // 왼 , 위아래
Left(cur.x,cur.y);
Up(cur.x,cur.y);
Down(cur.x,cur.y);
}
}
}
int ans = 0;
for(int i=0;i<n;i++) {
for (int j = 0; j < m; j++) {
if (!check[i][j]) {
ans++;
}
}
}
/*
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
System.out.print(check[i][j]+" ");
}
System.out.println();
}
*/
System.out.println(ans);
}
}
class Pos{
int x;
int y;
Pos(int x, int y){
this.x =x;
this.y =y;
}
}어려운점:
1,2,3,4,5 가 많아질 경우 그 만큼의 경우의 수를 고려할
for문이 필요한데 그걸 조절하는법은?
각 숫자를 큐에 넣어서 그 주변을 살핀다음에
가장 많이 뺼 수 있는 값을 구해서
다 뺴면 되지 않을까?
>> 그 외에 cctv를 고려할때 이미 본 부분을 처리할 방법 없음
큐를 사용해서 숫자 있는 부분의 좌표를 하나씩 저장 해둠
그 다음에 boolean 2차원 있는 것 (숫자랑 벽은 true로 해둠) 에서
for문으로 최대한 많이 true로 만들 수 있는 부분을 찾고 true로 만듬
이걸 큐에서 다 뽑아내면서 반복하도록함.
방향 탐색 후 가장 큰 값을 가지는 방향 리턴 -> 가장 큰 문제점
cctv 실행순서?
모든 cctv 경우에 대해 동시에 고려해야하는데
내 코드 같은 경우 cctv 각각의 경우를 고려하기에 틀린 부분이 나온다.
어떻게 해결해야할지..
위에 껄 싹 무시하고 그냥 모든 경우 고려하는게 맞는 답이였다..
너무 쉽게 살려고 하지 말기