[Algorithm] Baekjoon 11967번 : 불켜기

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

11967번: 불켜기

struct Node
{
    int y;
    int x;
};
 
int n, m, a, b, c, d;
int arr[102][102] = { 0 };
vector<Node> lightInfo[101][101];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int lightCount = 0;
 
// 0은 불 켜져있지도 않고 그렇기 떄문에 방문한적도없음
// 1은 불은 켜져있는데 방문하진 않았음
// 2는 방문했던 곳. 그렇기때문에 당연히 불은 켜져있다.
 
void BFS()
{
 
    queue<Node> q;
    q.push({ 1,1 });
    arr[1][1] = 2;
    ++lightCount;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < lightInfo[curY][curX].size(); ++i)
        {
            int switchLightY = lightInfo[curY][curX][i].y;
            int switchLightX = lightInfo[curY][curX][i].x;
 
            if (arr[switchLightY][switchLightX] == 0) // 불 꺼져있으면
            {
                arr[switchLightY][switchLightX] = 1; // 불 킨다.
                ++lightCount; 
                
                // 방문가능한지 검사.
                bool check = false;
 
                for (int j = 0; j < 4; ++j)
                {
                    int nextY = switchLightY + dir[j][0];
                    int nextX = switchLightX + dir[j][1];
 
                    if (nextY < 1 || nextY > n) continue;
                    if (nextX < 1 || nextX > n) continue;
                    if (arr[nextY][nextX] < 2) continue; // 무조건 방문한적있어야됨.
 
                    check = true;
                }
 
                if (check) // 주변에 방문했었던 노드가 있어서 현재 스위치라이트를 방문할 수 있으면
                {
                    arr[switchLightY][switchLightX] = 2; // 방문표시
                    q.push({ switchLightY,switchLightX });
                }
            }
        }
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 1 || nextY > n) continue;
            if (nextX < 1 || nextX > n) continue;
            if (arr[nextY][nextX] != 1) continue; // 불은 켜져있되, 방문한적은 없어야됨.
 
            arr[nextY][nextX] = 2; // 방문표시
            q.push({ nextY,nextX });
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b >> c >> d;
 
        lightInfo[b][a].push_back({ d,c });
    }
 
    BFS();
 
    cout << lightCount;
}
 

문제를 잘 이해해야 쉽게 풀 수 있는 문제. 방에 불을 몇개나 켰는지를 리턴하는거지, 방에 들어간 횟수를 카운팅하는게 아니다. 

BFS문제에서는 어떠한 노드가 큐에 들어갔다는게 무슨 의미인지 기준을 잘잡고 코드를 짜야한다.

나같은 경우, 확실히 방문이 가능한 좌표노드를 큐에 넣는것을 기준으로 삼았다.

그렇기 때문에 처음 큐에 1,1을 넣을 수 있는 이유는, 문제조건이 반드시 1,1은 불이 켜져있고 1,1부터 시작한다는 조건이기 때문이다.

 

큐에서 노드를 꺼내면, 해당 노드에 있는 스위치를 무조건 전부 키고 카운팅한다. 켰다는 표시는 arr에 1로 표시한다.

이후 사실상 제일 중요한 검사를 한다.

스위치를 킨 좌표의 주변을 검사한다. 주변 좌표에 arr값이 2라고 표시된 곳이 있다면, 즉 이미 지나친 곳(방문한 곳)이 있다면 현재 검사중인 좌표또한 방문 가능한곳으로 판단한다. 바로 인접한곳에 방문을 했었기 때문에, 현재좌표 또한 방문이 가능하기 때문이다. 인접한 좌표(상하좌우) 중, 하나라도 방문했었던 노드가 있더라면 현재좌표 arr에 2로 표시하고 큐에 넣어준다.

 

그 다음 꺼낸 노드를 기준으로 상하좌우를 검사해서, 불이 켜져있으면 방문가능하기 때문에 arr에 방문표시 2를 해주고 큐에 넣어주면 된다.

 

골드 3?정도 부터의 BFS문제에서는 이런식으로 단순 상하좌우 탐색보다는 더 추가적인 행동을 바라는 것 같다.

한번이라도 코드를 이렇게 짠 경험이 있다면, 다음에 생각해내기가 훨씬 쉬워진다.