백준 2115번 [갤러리](C++) -yes6686- 티스토리

백준 문제 풀이: 2115 [갤러리]

---

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

문제 설명:

갤러리의 벽은 X(그림 있음)와 .(빈 공간)으로 표현됩니다. 갤러리를 벽에 붙이는 조건은 다음과 같습니다:

• 세로 방향으로 두 개의 X가 붙어 있을 때, 바로 오른쪽 두 칸이 비어 있어야 한다.
• 가로 방향으로 두 개의 X가 붙어 있을 때, 바로 아래 두 칸이 비어 있어야 한다.

위 조건을 만족하는 경우를 찾아 갤러리에 최대한 많은 그림을 붙이는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

int arr[1001][1001]; // 벽 정보 (X는 1, .는 0)
int rvisited[1001][1001]; // 세로 방향 방문 체크
int cvisited[1001][1001]; // 가로 방향 방문 체크

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n; // m: 행의 수, n: 열의 수
    cin >> m >> n;

    // 갤러리 벽 입력
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            if (s[j] == 'X') arr[i][j] = 1;
        }
    }

    int ans = 0; // 붙일 수 있는 갤러리 수

    // 세로 방향 검사
    for (int i = 1; i < m - 2; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (arr[i][j] == 1 && arr[i + 1][j] == 1) {
                if (arr[i][j + 1] == 0 && arr[i + 1][j + 1] == 0) {
                    if (rvisited[i][j] == 0 && rvisited[i + 1][j] == 0) {
                        rvisited[i][j] = 1;
                        rvisited[i + 1][j] = 1;
                        ans++;
                    }
                }
            } else if (arr[i][j] == 0 && arr[i + 1][j] == 0) {
                if (arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) {
                    if (rvisited[i][j] == 0 && rvisited[i + 1][j] == 0) {
                        rvisited[i][j] = 1;
                        rvisited[i + 1][j] = 1;
                        ans++;
                    }
                }
            }
        }
    }

    // 가로 방향 검사
    for (int i = 0; i < m - 1; i++) {
        for (int j = 1; j < n - 2; j++) {
            if (arr[i][j] == 1 && arr[i][j + 1] == 1) {
                if (arr[i + 1][j] == 0 && arr[i + 1][j + 1] == 0) {
                    if (cvisited[i][j] == 0 && cvisited[i][j + 1] == 0) {
                        cvisited[i][j] = 1;
                        cvisited[i][j + 1] = 1;
                        ans++;
                    }
                }
            } else if (arr[i][j] == 0 && arr[i][j + 1] == 0) {
                if (arr[i + 1][j] == 1 && arr[i + 1][j + 1] == 1) {
                    if (cvisited[i][j] == 0 && cvisited[i][j + 1] == 0) {
                        cvisited[i][j] = 1;
                        cvisited[i][j + 1] = 1;
                        ans++;
                    }
                }
            }
        }
    }

    cout << ans << '\n'; // 결과 출력
    return 0;
}

예제 입력:

5 5
X.X..
X.X.X
...X.
.X.X.
.X...

예제 출력:

2

---

코드 설명

• 핵심 알고리즘: 이중 반복문을 사용해 세로와 가로 방향으로 붙일 수 있는 갤러리를 검사합니다.
• 구현 세부사항:
  • 세로 방향: 두 X가 붙어 있고 오른쪽 두 칸이 비어 있는 경우를 찾습니다.
  • 가로 방향: 두 X가 붙어 있고 아래 두 칸이 비어 있는 경우를 찾습니다.
  • 각 방향마다 방문 체크 배열을 사용해 중복 계산을 방지합니다.
• 시간 복잡도: O(m ⋅ n), m은 행의 수, n은 열의 수입니다.

---

결과

세로와 가로 조건을 모두 만족하는 갤러리의 최대 개수를 정확히 계산하여 출력합니다. 문제는 2차원 배열 탐색과 조건 검사를 연습하기에 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!