백준 1652번 누울 자리를 찾아라 :: 마이구미

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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') ? 1 : 0;
            c += (map[j][i] == '.' && map[j + 1][i] == '.' && map[j + 2][i] == 'X') ? 1 : 0;
        }
    }
 
    System.out.println(r + " " + c);
}