[백준/C++] 알고리즘 11967번 - 불 켜기

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 11967번 - 불 켜기를 풀어보도록 하겠습니다.

 

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

11967번: 불켜기

 

[문제 접근]

N이 작기 때문에 완전탐색이 가능합니다. 인접하고 불이 켜진 방으로 이동할 수 있다는 조건 하에 다차원 배열을 순회하기 때문에 BFS를 생각했습니다. 

 

[풀이 전략]

<실패1 요약>

1. 현재 방에서 원격으로 스위치를 불을 킵니다. 

2.현재 방에서 인접한 방이 불이 켜져있고, 방문하지 않았으면 q에 삽입합니다.

3. q에서 값을 꺼내와 1,2의 방식으로 순회를 반복했습니다.

 

문제점 - 현재 방에서 멀리 떨어진 불이 켜진 방을 순회할 수 없습니다. (그 불이 켜진 방의 인접한 부분은 이미 방문했던 곳임에도 불구하고)

 

<실패2>

1. 현재 방 기준,  원격으로 불 킬 수 있는 방들 중 인접한 지점에 불이 켜져있고 방문했던 방이 있으면 q에 삽입합니다.

 

문제점 -  원격으로 불 킬 수 있는 방 중에서 현재 방과 인접하지 않은 방을 먼저 확인할 경우 방문을 하지 못하는 사태가 발생합니다.

 

<성공>

실패1의 알고리즘과 실패2의 알고리즘을 결합했습니다.

1. 원격으로 불을 킨 방 중에 인접한 지점에 불이 켜져있고 방문했던 방이면 q에 삽입합니다. (실패 2의 알고리즘)

2. 현재 방에서 인접한 방이 불이 켜져있고 방문하지 않았으면 q에 삽입합니다.(실패 1의 알고리즘)

 

[코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;


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

int n , m ; 
int fir[101][101];  // -1 : 불꺼짐 , 0 : 불켜짐 , 1 : 불 켜진 곳 방문함.

vector<pair<int,int>> v[101][101]; // 0-indexed

queue<pair<int,int>> q ; 
int cnt ; 


bool findConnect(pair<int,int> cur){
       int x = cur.first;
        int y = cur.second;
     for(int k = 0 ; k < 4 ; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if(nx >= n || nx < 0 || ny >= n || ny < 0) continue;
                    if(fir[nx][ny] == 1) return 1 ;
            }
            return 0 ;
}

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

    //입력
    cin >> n >> m ; 
    for(int i = 0 ; i < m ; i++)
            {   int x ; int  y ; int a ; int b ;
                cin >> x >> y >> a >> b ;
                v[x-1][y-1].push_back({a-1,b-1});
            }

    for(int i = 0 ; i < n ; i++) fill(fir[i],fir[i]+n,-1);
    
    // 초기값
    fir[0][0] = 1 ; 
    cnt++;
    q.push({0,0});

    while (!q.empty())
    {
        auto cur = q.front() ; q.pop();
        int x = cur.first;
        int y = cur.second;
            // 현재 지점에서 원격스위치를 킬 수 있는 곳 체크하면서 인접해있으면 q에 삽입.
            for(auto c : v[x][y]){
                if(fir[c.first][c.second] < 0) {
                    cnt++;
                    fir[c.first][c.second] = 0 ;
                    if(findConnect(c)) {q.push({c.first,c.second});
                        fir[c.first][c.second] = 1 ;
                    
                    }
                    }
                 }
            // 현재 지점에서 인접한 지점들 중에 불이 켜져있고, 방문하지 않았으면 q에 삽입.
            for(int k = 0 ; k < 4 ; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if(nx >= n || nx < 0 || ny >= n || ny < 0) continue;
                    if(abs(fir[nx][ny]) == 1) continue;
                    fir[nx][ny] = 1;
                    q.push({nx,ny});
            }
            
    }
    cout <<cnt; 
}

 

[배울 점]

- 안 풀리는 문제는 코드 구현력문제라기보다는 모델링하는 부분, 즉 알고리즘을 알아내지 못한 것