백준 11967번 [불켜기](C++) -yes6686- 티스토리

 

백준 문제 풀이: 11967 (불켜기)

---

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

문제 설명:

N×N 크기의 방이 주어지고, 일부 방에는 스위치가 있어 다른 방의 불을 켤 수 있습니다.
(1, 1) 방에만 처음 불이 켜져 있고, 불이 켜져 있으면서 인접한 방만 이동할 수 있습니다.
목표는 불을 켤 수 있는 방의 수를 구하는 것입니다.

제약 조건:

• 스위치는 (x, y) 방에 위치하며, (a, b) 방의 불을 켤 수 있음.
• 불이 꺼진 방은 지나갈 수 없고, 불이 켜져 있어도 도달할 수 없는 방에는 갈 수 없음.

---

문제 해결 코드

// 불켜기 - BFS + 스위치 시뮬레이션
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int n, m, ans = 0;
int arr[101][101];             // 불 켜짐 여부
int visited[101][101];         // BFS 방문 여부
int activated[101][101];       // 스위치 작동 여부
vector<pair<int, int>> sw[101][101]; // 스위치 정보

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;

    while (!q.empty()) {
        auto [cx, cy] = q.front(); q.pop();

        // 아직 스위치를 안 켰다면 불을 켜기
        if (!activated[cx][cy]) {
            activated[cx][cy] = 1;
            for (auto [nx, ny] : sw[cx][cy]) {
                if (arr[nx][ny] == 0) {
                    arr[nx][ny] = 1;
                }
            }
        }

        // 4방향 인접한 방 탐색
        for (int d = 0; d < 4; d++) {
            int nx = cx + dx[d];
            int ny = cy + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (visited[nx][ny]) continue;
            if (arr[nx][ny] == 0) continue;
            visited[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
}

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

    cin >> n >> m;

    // 초기 방 (0,0) 불 켜짐
    arr[0][0] = 1;

    // 스위치 정보 입력
    for (int i = 0; i < m; i++) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        sw[x - 1][y - 1].emplace_back(a - 1, b - 1);
    }

    // 스위치 켜질 때마다 bfs 재시도
    while (true) {
        memset(visited, 0, sizeof(visited));
        int before = ans;
        bfs(0, 0); // (0,0)에서 탐색
        int lights = 0;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (arr[i][j]) lights++;

        if (lights == before) break; // 변화 없으면 종료
        ans = lights;
    }

    cout << ans << '\n';
}

---

코드 설명

스위치를 누르면 불이 켜지므로, 불 켜짐 상태가 변화할 때마다 BFS를 반복 수행합니다.

• 핵심 알고리즘: BFS + 반복 시뮬레이션
• 구현 세부사항:
  • arr[i][j]: 불이 켜져 있는 상태
  • sw[x][y]: (x,y) 방에 있는 스위치 → 불을 켤 방 리스트
  • BFS 내에서 새로 불이 켜지면 다음 반복에서 다시 탐색
• 시간 복잡도 분석:
  • BFS 반복 횟수: 최대 N²번
  • 1회 BFS당 O(N²)
  • 총 시간 복잡도: O(N² ⋅ N²) = O(N⁴), N ≤ 100 → 충분히 가능

---

결과

예시 입력:

3 6
1 1 1 2
1 1 2 1
1 2 1 3
1 3 1 1
2 1 2 2
2 2 2 3

예시 출력:

6

스위치 시뮬레이션을 반복하면서 불이 켜지는 방의 수를 계산합니다.

다른 최적화 방법이나 아이디어가 있다면 댓글로 함께 고민해보아요!