백준 28471번 [W키가 빠진 성원이](C++) -yes6686- 티스토리

백준 문제 풀이: 28471 (W키가 빠진 성원이)

---

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

문제 설명:

주어진 n x n 격자판에서 성원이(W)를 시작점으로 삼아 **이동 가능한 영역**을 탐색하는 문제입니다. - **이동 규칙:** 성원이는 상하좌우 및 대각선 7방향으로 움직일 수 있습니다. - **장애물(#):** 성원이는 장애물을 통과할 수 없습니다. - **빈 칸(.):** 성원이가 이동 가능한 영역입니다. - 최종적으로 성원이가 도달할 수 있는 빈 칸의 개수를 구합니다.

---

문제 해결 코드

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

queue<pair<int, int>> q; // BFS 탐색 큐

// 성원이의 이동 방향 (7가지)
int dx[7] = { -1, -1, 0, 0, 1, -1, 1 };
int dy[7] = { -1, 1, -1, 1, -1, 0, 1 };

int arr[2001][2001];     // 격자 정보
int visited[2001][2001]; // 방문 여부
int n;                   // 격자 크기

int ans = 0; // 이동 가능한 빈 칸의 개수

// BFS를 이용한 영역 탐색
void bfs(int x, int y) {
    visited[x][y] = 1;
    q.push({x, y});

    while (!q.empty()) {
        int kx = q.front().first;
        int ky = q.front().second;
        q.pop();

        for (int i = 0; i < 7; i++) {
            int nx = kx + dx[i];
            int ny = ky + dy[i];

            // 범위를 벗어나면 continue
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

            // 이미 방문했거나, 장애물(#)이면 continue
            if (visited[nx][ny] == 1 || arr[nx][ny] == 1) continue;

            // 방문 가능한 빈 칸인 경우
            visited[nx][ny] = 1;
            ans++;
            q.push({nx, ny});
        }
    }
}

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

    cin >> n; // 격자 크기 입력
    int fi, fj; // 성원이의 시작점 좌표

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        for (int j = 0; j < s.size(); j++) {
            if (s[j] == '#') {
                arr[i][j] = 1; // 장애물
            } else if (s[j] == '.') {
                arr[i][j] = 0; // 빈 칸
            } else { 
                fi = i; // 성원이의 시작점 (W)
                fj = j;
                arr[i][j] = 2;
            }
        }
    }

    // BFS 탐색 시작
    bfs(fi, fj);

    cout << ans; // 이동 가능한 빈 칸의 개수 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• BFS(너비 우선 탐색): - 성원이의 시작점에서 BFS를 수행하여 인접한 빈 칸을 탐색합니다.
• 이동 방향: - 7가지 방향으로 이동이 가능합니다: 상하좌우 및 대각선 방향.
• 방문 처리: - 이미 방문한 칸이나 장애물(#)은 탐색에서 제외합니다.
• 범위 검사: - 격자판을 벗어나는 경우를 검사하여 탐색을 중단합니다.

시간 복잡도 분석

• 격자의 크기가 n x n이므로 최악의 경우 모든 칸을 탐색할 수 있습니다.
• BFS의 시간 복잡도는 **O(n²)**입니다.
• 입력과 탐색이 효율적으로 수행되므로 **n ≤ 2000**인 경우에도 충분히 빠르게 동작합니다.

---

결과

주어진 격자에서 성원이(W)가 도달할 수 있는 빈 칸의 개수를 출력합니다.

• 입력 예시:

  5  
  .....  
  ..#..  
  ..W..  
  ..#..  
  .....

• 출력 예시:

  13

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!