백준 - 15683 감시 (Java)

<서론>

그림 1. 일단 푼 거 인증

이 문제를 풀었을 당시에 나는 dfs와 bfs에 대해 하나도 모르는 상태였다. 알고리즘 문제를 푼다는 행위 역시도 매우 매우 낯설었기 때문에 15683번인 감시를 푸는 일은 내게 굉장히 힘든 일이었다. 게다가 알고리즘 문제를 재귀로 풀 생각을 아예 못했었을 정도니... 아무튼 삼성 기출 문제라고 하길래 풀어보았다.

서론을 이런 식으로 쓰는 이유는.. 난 이 문제를 일반적인 dfs 풀이로 풀지 않았기때문이다. 나는 무려 8번의 for문을 사용해서 풀었다. 만약 이 문제가 막혀서 해결하고자 오신 분들이면 이 글을 추천하지 않는다. 만약 당신이 왕초보 코더가 간신히 푼 문제를 비웃고자 한다면 이 글을 계속 읽어도 좋다.

 

---

 

<본론>

** 요약

핵심 : 8중 for문 사용(최대 카메라 수 만큼), for문 순서는 카메라 역순(제일 밖 for문 : 8번 카메라, 제일 안 for문 : 1번카메라)

1. 기본적으로 4방향이기 때문에 for문 인덱스는 0~3 까지 확인, 카메라가 없는 경우는 0만 되게 설정(for문 1번은 돌아야하니)

2. for문 인덱스 번호를 방향으로 그 for문의 카메라 감시영역을 7로 바꿈(int 배열이라 7로 표현, changeToS 메서드)

3. 만약 그 번호 카메라가 존재한다면, 지금 상태 감시 상태 저장(나중에 원복할 때 사용할 예정, 굳이 for문마다 안해도 되는 기능 - 실수 )

4. 모든 카메라를 다 체크했다면, 전체 배열을 체크하면서 0의 개수 파악(countZero 메서드) -> 현재값보다 작으면 저장

5. 카메라 감시방향 리셋

완성 코드는 결론에 적겠다.

 

우선, 나도 처음에는 코드를 멋지고 간결하게 짜고 싶었다. 하지만 태어나서 이런 류의 문제는 처음이었고, 뭔가 오기가 생겨서 주변 도움은 하나도 받지 않은 상태로 문제를 해결하고 싶었다. 짜내고 짜내다가 내린 결론은 for문을 카메라 수만큼 사용하는 것이었다.

 

이런 극단적인 선택을 할 수 있었던 이유는 전체 경우의 수가 4^8 = 65,536 가지 뿐(카메라 8개, 확인하는 방향 4개)이다. 내가 컴공은 아니라 정확히는 모르지만, 저정도 경우의 수면 아무리 for문이 8중이라도 시간 초과는 나지 않을 것 같았다.

for문을 8개 만들고 나니, 안쓰는 포문에 대해서도 고민했어야 했다. 그래서 카메라 뒷번호일수록 바깥쪽 for문으로 설정했고, 카메라 개수인 cCnt에 따라서 for문의 반복 회수도 결정했다. 즉, 모든 카메라에 대해

 

for(aa1 = 1; a11<a1; a11++)

for(int aa1 = 1; aa1<a1; aa1++)

 

이런 식으로 설정했고 카메라가 4개라면 a1 ~ a4까지는 4, a5 ~ a8은 1로 설정해서 a4까지는 4번 돌고, 나머지는 한번만 돌게 설정했다. 그리고 각 카메라의 번호와 위치, 방향 정보를 보내서 감시영역을 7로 바꿔주는 메서드를 호출했다.

모든 카메라의 감시영역이 칠해지면 그 후 0을 세는 메서드를 사용해서 최소 사각지대를 구했다.

 

이렇게 코드를 짜서 제출했고, 답은 맞았지만 지금 코드에서 굉장히 비효율적인 부분이 있다. 8중 for문을 쓴 것이 아니라 다른 부분에서의 비효율이다.

현 프로세스는

1. 카메라의 감시 방향 결정(여기서는 for문의 인덱스)

2. 감시 방향대로 지도에 표시

3. 현재 방 상태 저장

4. 모든 카메라를 확인할 때까지 1~3 과정 반복

5. 사각지대 수 확인

6. 첫 번째 카메라 감시영역 표시 전으로 원복

7. ...

 

위와 같이 작성하였다. 즉 카메라 감시 방향이 정해지면 바로 칠하고 다음 카메라로 이동하는 것이 문제인 것이다.

그렇기 때문에 카메라 별로 감시 전과 후를 위한 2차 배열이 필요했다.

이를 개선한다면, 모든 카메라의 감시방향을 다 정한 후, 감시 영역 표시는 그 후에 한꺼번에 이루어 지는 것이 간편할 것이다.

그렇게 되면 원복용 2차 배열도 1개만 있으면 될 것이다.

답은 맞았지만, 이부분을 고려하지 못한 것은 무척이나 아쉽다.

 

---

 

<결론>

아래에 무시무시하게 긴 코드가 있다. dfs, bfs도 그렇고 재귀 함수에 대해 매우 몰랐던 탓에 이렇게 무식한 코드가 나왔다. 이번 문제를 풀고 dfs와 bfs에 대해 공부를 해야겠다! 라는 마음도 생겼고, 무식하지만 그래도 나 혼자만의 힘으로 풀었다는 것에 뿌듯하기도 했다. 물론 이 한문제를 풀기위해 너무나 많은 시간을 쏟았지만 그래도 다 풀고, 맞았습니다! 를 보았을 땐 정말정말 기뻤다.

이 재미에 알고리즘 문제를 푸는 것 같다.

 

import java.util.Scanner;
 
public class Main {
    
    static int[][] room;
    static int[][] tempRoom;
    static int[][] testRoom;
    static int[][] cameraDir = new int[8][7];
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int height = sc.nextInt();
        int width = sc.nextInt();
        int cCnt = 0;
        int temp = 100;
        int[][] cam2Room = new int[height][width];
        int[][] cam3Room = new int[height][width];
        int[][] cam4Room = new int[height][width];
        int[][] cam5Room = new int[height][width];
        int[][] cam6Room = new int[height][width];
        int[][] cam7Room = new int[height][width];
        int[][] cam8Room = new int[height][width];
        
        room = new int[height][width];
        tempRoom = new int[height][width];
        testRoom = new int[height][width];
        
        for(int i=0; i<height; i++) {
            for(int j=0; j<width; j++) {
                room[i][j] = sc.nextInt();
                tempRoom[i][j] = room[i][j];
            }
        }
        
        for(int i=0; i<height; i++) {
            for(int j=0; j<width; j++) {
                if(room[i][j]!=0 && room[i][j]!=6) {
                    cameraDir[cCnt][4] = i;
                    cameraDir[cCnt][5] = j;
                    cameraDir[cCnt][6] = room[i][j];
                    cCnt++;
                }
            }
        }
        
        int a1 = cCnt>=1 ? 4 : 1;
        int a2 = cCnt>=2 ? 4 : 1;
        int a3 = cCnt>=3 ? 4 : 1;
        int a4 = cCnt>=4 ? 4 : 1;
        int a5 = cCnt>=5 ? 4 : 1;
        int a6 = cCnt>=6 ? 4 : 1;
        int a7 = cCnt>=7 ? 4 : 1;
        int a8 = cCnt>=8 ? 4 : 1;
        
        boolean rb2 = a2==4?true:false;
        boolean rb3 = a3==4?true:false;
        boolean rb4 = a4==4?true:false;
        boolean rb5 = a5==4?true:false;
        boolean rb6 = a6==4?true:false;
        boolean rb7 = a7==4?true:false;
        boolean rb8 = a8==4?true:false;
        
        for(int aa8=0; aa8<a8; aa8++) {
            changeZtoS(cameraDir[7][6], aa8, cameraDir[7][4], cameraDir[7][5]);
            if(a8>1) roomSave(cam8Room);
            for(int aa7=0; aa7<a7; aa7++) {
                changeZtoS(cameraDir[6][6], aa7, cameraDir[6][4], cameraDir[6][5]);
                if(a7>1) roomSave(cam7Room);
                for(int aa6=0; aa6<a6; aa6++) {
                    changeZtoS(cameraDir[5][6], aa6, cameraDir[5][4], cameraDir[5][5]);
                    if(a6>1) roomSave(cam6Room);
                    for(int aa5=0; aa5<a5; aa5++) {
                        changeZtoS(cameraDir[4][6], aa5, cameraDir[4][4], cameraDir[4][5]);
                        if(a5>1) roomSave(cam5Room);
                        for(int aa4=0; aa4<a4; aa4++) {
                            changeZtoS(cameraDir[3][6], aa4, cameraDir[3][4], cameraDir[3][5]);
                            if(a4>1) roomSave(cam4Room);
                            for(int aa3=0; aa3<a3; aa3++) {
                                changeZtoS(cameraDir[2][6], aa3, cameraDir[2][4], cameraDir[2][5]);
                                if(a3>1) roomSave(cam3Room);
                                for(int aa2=0; aa2<a2; aa2++) {
                                    changeZtoS(cameraDir[1][6], aa2, cameraDir[1][4], cameraDir[1][5]);
                                    if(a2>1) roomSave(cam2Room);
                                    for(int aa1=0; aa1<a1; aa1++) {
                                        changeZtoS(cameraDir[0][6], aa1, cameraDir[0][4], cameraDir[0][5]);
                                        int zero = countZero(height, width);
                                        if(temp > zero) {
                                            temp = zero;
                                            for(int i=0; i<height; i++) {
                                                for(int j=0; j<width; j++) {
                                                    testRoom[i][j] = tempRoom[i][j];
                                                }
                                            }
                                        }
                                        if(a1>1) roomReset(cam2Room, rb2);
                                    }
                                    if(a2>1) roomReset(cam3Room, rb3);
                                }
                                if(a3>1) roomReset(cam4Room, rb4);
                            }
                            if(a4>1) roomReset(cam5Room, rb5);
                        }
                        if(a5>1) roomReset(cam6Room, rb6);
                    }
                    if(a6>1) roomReset(cam7Room, rb7);
                }
                if(a7>1) roomReset(cam8Room, rb8);
            }
            if(a8>1) roomReset(null, false);
        }
        
        System.out.println(temp);
        
        sc.close();
    }
    
    static void roomReset(int[][] arr, boolean isValid) {
        if(arr!=null && isValid) {
            for(int i=0;i<arr.length; i++) {
                for(int j=0;j<arr[0].length;j++) {
                    tempRoom[i][j] = arr[i][j];
                }
            }
        } else {
            for(int i=0;i<room.length; i++) {
                for(int j=0;j<room[0].length;j++) {
                    tempRoom[i][j] = room[i][j];
                }
            }
            
        }
    }
    
    static void roomSave(int[][] arr) {
        for(int i=0;i<arr.length; i++) {
            for(int j=0;j<arr[0].length;j++) {
                arr[i][j] = tempRoom[i][j];
            }
        }
    }
    
    
    static int countZero(int r, int c) {
        int countZero = 0;
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(tempRoom[i][j]==0) countZero++;
            }
        }
        
        return countZero;
    }
    
    static void changeZtoS(int cType, int dir, int curRow, int curCol) {
        switch(cType) {
            case 1:
                switch(dir) {
                    case 0:
                        for(int r=curRow; r>=0; r--) {
                            if(tempRoom[r][curCol]==6) break;
                            tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                        }
                        break;
                    case 1:
                        for(int r=curRow; r<room.length; r++) {
                            if(tempRoom[r][curCol]==6) break;
                            tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                        }
                        break;
                    case 2:
                        for(int c=curCol; c>=0; c--) {
                            if(tempRoom[curRow][c]==6) break;
                            tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                        }
                        break;
                    case 3:
                        for(int c=curCol; c<room[0].length; c++) {
                            if(tempRoom[curRow][c]==6) break;
                            tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                        }
                        break;
                }
                break;
            case 2:
                switch(dir) {
                    case 0:
                    case 1:
                        for(int r=curRow; r>=0; r--) {
                            if(tempRoom[r][curCol]==6) break;
                            tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                        }
                        for(int r=curRow; r<room.length; r++) {
                            if(tempRoom[r][curCol]==6) break;
                            tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                        }
                        break;
                    case 2:
                    case 3:
                        for(int c=curCol; c>=0; c--) {
                            if(tempRoom[curRow][c]==6) break;
                            tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                        }
                        for(int c=curCol; c<room[0].length; c++) {
                            if(tempRoom[curRow][c]==6) break;
                            tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                        }
                        break;
                }
                break;
            case 3:
                switch(dir) {
                case 0:
                    for(int r=curRow; r>=0; r--) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    for(int c=curCol; c>=0; c--) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    break;
                case 1:
                    for(int c=curCol; c>=0; c--) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    for(int r=curRow; r<room.length; r++) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    break;
                case 2:
                    for(int r=curRow; r<room.length; r++) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    for(int c=curCol; c<room[0].length; c++) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    break;
                case 3:
                    for(int c=curCol; c<room[0].length; c++) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    for(int r=curRow; r>=0; r--) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    break;
            }
                break;
            case 4:
                switch(dir) {
                case 0:
                    for(int c=curCol; c>=0; c--) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    for(int r=curRow; r>=0; r--) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    for(int c=curCol; c<room[0].length; c++) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    break;
                case 1:
                    for(int r=curRow; r<room.length; r++) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    for(int r=curRow; r>=0; r--) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    for(int c=curCol; c<room[0].length; c++) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    break;
                case 2:
                    for(int c=curCol; c>=0; c--) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    for(int r=curRow; r>=0; r--) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    for(int r=curRow; r<room.length; r++) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    break;
                case 3:
                    for(int c=curCol; c<room[0].length; c++) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    for(int r=curRow; r<room.length; r++) {
                        if(tempRoom[r][curCol]==6) break;
                        tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                    }
                    for(int c=curCol; c>=0; c--) {
                        if(tempRoom[curRow][c]==6) break;
                        tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                    }
                    break;
            }
                break;
            case 5:
                for(int r=curRow; r>=0; r--) { 
                    if(tempRoom[r][curCol]==6) break;
                    tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                }
                for(int c=curCol; c<room[0].length; c++) {
                    if(tempRoom[curRow][c]==6) break;
                    tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                }
                for(int r=curRow; r<room.length; r++) { 
                    if(tempRoom[r][curCol]==6) break;
                    tempRoom[r][curCol]=tempRoom[r][curCol]==0?7:tempRoom[r][curCol];
                }
                for(int c=curCol; c>=0; c--) { 
                    if(tempRoom[curRow][c]==6) break;
                    tempRoom[curRow][c]=tempRoom[curRow][c]==0?7:tempRoom[curRow][c];
                }
                break;
        }
    }
    
}