[백준, C++] 11967번 불켜기

문제

https://www.acmicpc.net/problem/11967

 

해설

일반적인 풀이 방식은 새로운 방에 불을 켤 때마다 BFS에서 방문 여부를 체크하는 vis배열을 모두 0으로 초기화한 후, 재탐색을 진행합니다.

이 풀이의 시간복잡도 O(N) = N^4일 것입니다. 

 

제가 구현한 방식의 시간복잡도 O(N) = N^2입니다. 즉, 위에서 언급한 새로운 방에 불을 켤 때마다 BFS에서 방문 여부를 체크하는 vis 배열을 초기화하는 과정을 진행하지 않습니다.

 

조건

BFS를 기반으로 구현하였습니다.

먼저 Queue에 삽입되는 좌표는 베시가 접근할 수 있는 방의 좌표입니다. 

 

해설에서 언급한 새로운 방에 불을 켤 때마다 BFS에서 방문 여부를 체크하는 vis배열을 모두 0으로 초기화하는 이유는 새로 불이 켜진 방이 이미 vis == 1 로 초기화된(베시가 지나간) 방과 인접할 수 있기 때문입니다.

이 과정을 생략하기 위해, 새롭게 불이 켜진 방이 vis==1로 초기화된(베시가 지나간)방과 인접한지 확인 후, 인접할 경우에 Queue에 삽입하는 방식을 선택했습니다.

이 때, 발생할 것으로 추정되는 예외와 발생하지 않는 이유는 다음과 같습니다.

• 배시가 갈 수 있는 방이지만, 아직 vis==1로 초기화되지 않은 경우에 Queue에 새로운 방이 삽입되지 않음
  => 배시가 갈 수 있는 방이지만, 아직 vis==1로 초기화되지 않았기 때문에 배시가 해당 방에 접근했을 때, 새로운 방에도 접근 가능

결론적으로 Queue에 좌표가 삽입되는 경우는 위의 경우와 일반적인 BFS 방식인 vis==0이고 불이 켜진 방의 경우로 2가지입니다.

 

정답 코드

#include <sstream>
#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>

using namespace std;

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

int N, M;
vector<vector<vector<pair<int, int> > > > lightSwitch;
vector<vector<int> > board;
vector<vector<int> > vis;
int answer;

void input() {
    cin >> N >> M;
    lightSwitch = vector(N, vector(N, vector<pair<int, int> >()));
    board = vector(N, vector(N, 0));
    vis = vector(N, vector(N, 0));
    answer = 1;

    int x, y, a, b;
    for (int i = 0; i < M; i++) {
        cin >> x >> y >> a >> b;
        lightSwitch[x - 1][y - 1].push_back({a - 1, b - 1});
    }
}

void solution() {
    board[0][0] = 1;
    vis[0][0] = 1;
    queue<pair<int, int> > q;
    q.push({0, 0});

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        for (int i = 0; i < lightSwitch[cur.first][cur.second].size(); i++) {
            pair<int, int> nextLightSwitch = lightSwitch[cur.first][cur.second][i];
            if (board[nextLightSwitch.first][nextLightSwitch.second] == 0) {
                board[nextLightSwitch.first][nextLightSwitch.second] = 1;
                answer++;

                for (int dir = 0; dir < 4; dir++) {
                    int nx = nextLightSwitch.first + dx[dir];
                    int ny = nextLightSwitch.second + dy[dir];

                    if (nx < 0 || ny < 0 || nx >= N || ny >= N)
                        continue;

                    if (board[nx][ny] == 1 && vis[nx][ny] == 1) {
                        q.push({nextLightSwitch.first, nextLightSwitch.second});
                        vis[nextLightSwitch.first][nextLightSwitch.second] = 1;
                    }
                }
            }
        }

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || ny < 0 || nx >= N || ny >= N)
                continue;

            if (board[nx][ny] == 1 && vis[nx][ny] == 0) {
                q.push({nx, ny});
                vis[nx][ny] = 1;
            }
        }
    }
}

void output() {
    cout << answer;
}

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


    input();

    solution();

    output();
}

 

 

이전에 풀었을 때와 비교해서 288ms -> 8ms 로 단축에 성공했습니다.