[BOJ 백준] 11967번 불켜기

문제

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

11967번: 불켜기

접근

 베시는 불이 켜진 방으로만 갈 수 있고 방에서 다른 방의 불을 켤 수 있다. 이를 BFS로 풀다 보면 문제가 생기는데 테스트 케이스를 예로 보면 (1, 1)에서 출발하여 (1, 2)와 (1, 3)의 불을 켤 수 있다. 다음으로 (1, 2)를 방문하고 (1, 3)을 방문한다. (1, 3)에서 (2, 1)의 불을 켠다. 이때 (2, 1)도 (1, 1)을 통해 갈 수 있는 방이지만 (1, 1)은 이미 BFS를 통해 방문을 마친 상태이기 때문에 방문하지 못한다. 따라서 일반적인 BFS의 코드로는 (2, 1)의 방에 방문해서 (2, 2)의 불을 켜지 못하므로 제대로 된 답을 찾을 수 없다. 그래서 이럴 경우 방문했던 좌표를 다시 방문해주는 코드를 기존의 BFS의 코드에 추가해주기만 하면 된다.

코드

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

using namespace std;

int n, m, counter = 1, map[105][105], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1}; 
vector<pair<int,int>> v[105][105];

int main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        v[x][y].push_back({a, b});
    }

    queue<pair<int,int>> q;
    q.push({1, 1});
    map[1][1] = 2;

    while (!q.empty()){
        pair<int, int> f = q.front();
        q.pop();
        for (auto p : v[f.first][f.second]) {
            if (map[p.first][p.second])
                continue;
            for (int i = 0; i < 4; i++){
                int newx = p.first + dx[i];
                int newy = p.second + dy[i];
                if (map[newx][newy] == 2) {
                    q.push({newx, newy});
                    break;
                }
            }
            map[p.first][p.second] = 1;
            counter++;
        }

        for (int i = 0; i < 4; i++){
            int newx = f.first + dx[i];
            int newy = f.second + dy[i];
            if (map[newx][newy] == 1){
                map[newx][newy] = 2;
                q.push({newx,newy});
            }
        }
    }

    cout << counter;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study