• 백준 1652번 누울 자리를 찾아라 :: 마이구미
    알고리즘 풀이/수학 2018. 8. 14. 13:57
    반응형

    이 글은 백준 알고리즘 문제 1652번 "누울 자리를 찾아라" 를 풀이한다.

    제출량이 많고, 정답 비율이 40% 인 문제.

    DFS, BFS 문제처럼 보이지만, 쉽게 해결할 수 있는 문제이다.

    본인에게는 다른 접근을 생각하는 자극을 준 문제이다.

    문제 링크 - https://www.acmicpc.net/problem/1652


    일 년 동안 세계일주를 하던 영식이는 여행을 하다 너무 피곤해서 근처에 있는 코레스코 콘도에서 하룻밤 잠을 자기로 하고 방을 잡았다.

    코레스코 콘도에 있는 방은 NxN의 정사각형모양으로 생겼다. 방 안에는 옮길 수 없는 짐들이 이것저것 많이 있어서 영식이의 누울 자리를 차지하고 있었다. 영식이는 이 열악한 환경에서 누울 수 있는 자리를 찾아야 한다. 영식이가 누울 수 있는 자리에는 조건이 있다. 똑바로 연속해서 2칸 이상의 빈 칸이 존재하면 그 곳에 몸을 양 옆으로 쭉 뻗으면서 누울 수 있다. 가로로 누울 수도 있고 세로로 누울 수도 있다. 누울 때는 무조건 몸을 쭉 뻗기 때문에 반드시 벽이나 짐에 닿게 된다. (중간에 어정쩡하게 눕는 경우가 없다.)

    만약 방의 구조가 위의 그림처럼 생겼다면, 가로로 누울 수 있는 자리는 5개이고, 세로로 누울 수 있는 자리는 4개 이다. 방의 크기 N과 방의 구조가 주어졌을 때, 가로로 누울 수 있는 자리와 세로로 누울 수 있는 자리의 수를 구하는 프로그램을 작성하시오.


    바둑판과 같은 이미지만 보면 왠지 DFS, BFS 를 써야할 것만 같다.

    본인 또한, 처음에는 그렇게 접근을 시작했다.

    하지만 생각이 깊어질수록, 단순한 문제라는걸 인지했다.


    1. 2칸 이상의 빈칸이 존재한다면, 누울 수 있다.
    2. 반드시 벽이나 짐에 닿게 된다.
    3. 중간에 어정쩡하게 눕는 경우가 없다.


    위 3가지만 이해한다면, 문제를 쉽게 해결할 수 있다.

    이 의미는 다음 이미지를 통해 쉽게 이해할 수 있다.


    1652번 누울 자리를 찾아라


    위 이미지는 가로를 기준으로 누울 자리를 표시한 그림이다.

    이를 통해 이해해야할 것은 다음과 같다. 


    • 2번째 가로에서 누울 자리가 1개뿐인 이유는 반드시 벽 또는 짐에 닿아야한다는 조건에 있기 때문이다.
    • 3번째 가로에서도 3칸을 모두 차지한 자리가 조건에 성립한다. 


    이것을 통해 단순히 가로 또는 세로를 기준으로 반복문을 통해 짐이나 벽을 만나기 전까지 카운터를 증가시키면 된다.

    짐이나 벽을 만났을 때, 카운터가 2 이상이라면, 누울 자리라고 판단하면 된다.


    int cnt = 0; int seat = 0; for (int i = 0; i < n; i++) { seat = 0; for (int j = 0; j < n; j++) { if (map[i][j] == '.') { ++seat; } else { // 짐일 경우 if (seat >= 2) { ++cnt; } seat = 0; } } // 벽일 경우 if (seat >= 2) { ++cnt; } }


    위와 같이 코드를 작성할 수 있다.

    조금 불편한 점은 가로와 세로를 위해 서로 따로 변수 및 진행을 해줘야한다는 것이다.

    코드를 간결하게 바꾸고 싶다면, 다음과 같이 할 수 있다.


    for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1; j++) { r += (map[i][j] == '.' && map[i][j + 1] == '.' && map[i][j + 2] == 'X') ? 1 : 0; c += (map[j][i] == '.' && map[j + 1][i] == '.' && map[j + 2][i] == 'X') ? 1 : 0; } }


    벽을 짐과 같이 동일하게 취급함으로써, 조건 연산자를 통해 코드를 줄였다.

    C 언어 계열이라면 논리 연산자를 통해 더 간결하게 나타낼 수 있다. (JAVA 도 가능하지만, 형변환이 유연하지 않다)


    for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1; j++) { r += map[i][j] == '.' && map[i][j + 1] == '.' && map[i][j + 2] ^ '.', c += map[j][i] == '.' && map[j + 1][i] == '.' && map[j + 2][i] ^ '.'; } }


    Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/math/1652.java


    private void solve() {
        int n = sc.nextInt();
        char[][] map = new char[101][101];
     
        for (int i = 0; i < n; i++) {
            String[] s = sc.next().split("");
            for (int j = 0; j < n; j++) {
                map[i][j] = s[j].charAt(0);
            }
            // 벽 또한 짐으로 판단
            map[i][n] = 'X';
            map[n][i] = 'X';
        }
     
        // (X or 벽) 판단
        int r = 0;
        int c = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                r += (map[i][j] == '.' && map[i][j + 1== '.' && map[i][j + 2== 'X') ? 0;
                c += (map[j][i] == '.' && map[j + 1][i] == '.' && map[j + 2][i] == 'X') ? 0;
            }
        }
     
        System.out.println(r + " " + c);
    }
    cs


    반응형

    댓글 0

Designed by Tistory.