백준 11967 : 불켜기 C++

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

11967번: 불켜기

 

세상 비효율적으로 푼거같지만, 한방에 바로 통과해서 기분좋아서 오랫만에 풀이 정리

 

풀이

1. 일단 기본 map과 visited를 별개로 관리

 -> 왜냐하면 visited는 불켜짐과는 상관없이 bfs에만 사용하는 용

 

2. map을 새로운 struct로 관리

 -> 각 방에서 킬 수 있는 스위치들 vector로 관리

 -> 지금 불 켜짐 여부 ( 한번 켜지면 꺼질 일 없다.

 

3. 기본적으로 방 불은 이미 켜져있으면 더이상 껏다 키는 행위를 하지 않는다

 

4. 루프~~

 1) 항상 시작은 (1,1)

    -> 지금 위치에서 불 킬 수 있는놈 다 키고, bfs 시작

 

 2) 돌아다니면서, 각 칸에서 스위치를 사용해서 불 킬 수 있는 방 모두 불켜지

  -> 이미 불 켜져있으면 그냥 무시

 

 3) 지금 방 불 켜진 모든곳을 돌았는데, 추가로 불켠곳이 한군데도 없다면, 그대로 종료

 

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct room {
	int light = 0;
	vector<pair<int, int>> sw;
};

int d_r[4] = { 1,-1,0,0 };
int d_c[4] = { 0,0,1,-1 };

int visited[102][102] = { 0, };
room map[102][102];
int n, m;
int answer = 0;
int r, c;

// 각 방에는 불을 켜고 있는 스위치가 있다.
// 불이 켜져있는 곳으로만 움직일 수 있음
// 다 끝났을때 불 키기

int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int tmp1, tmp2, tmp3, tmp4;
		cin >> tmp1 >> tmp2 >> tmp3 >> tmp4;
		map[tmp1][tmp2].sw.push_back(make_pair(tmp3, tmp4));
	}
	r = 1;
	c = 1;
	//일단 지금 위치 불 키고
	answer = 1;

	while (true)
	{
		memset(visited, 0, sizeof(visited));
		visited[r][c] = 1;
		map[r][c].light = 1;

		// 지금 위치에서 bfs로 가능한 모든곳을 갈껀데
		// 갈때마다 그 칸에서 킬 수 있는 불 모두 다 킬꺼야
		queue<pair<int, int> > q;
		q.push(make_pair(r, c));

		for (int i = 0; i < map[r][c].sw.size(); i++)
		{
			//기존에 꺼져 있던 경우에만 다시 키기
			if (map[map[r][c].sw[i].first][map[r][c].sw[i].second].light == 0)
			{
				answer++;
				map[map[r][c].sw[i].first][map[r][c].sw[i].second].light = 1;
			}
		}

		int cnt = 0;
		while (!q.empty())
		{
			int s = q.size();
			for (int i = 0; i < s; i++)
			{
				int new_r = q.front().first;
				int new_c = q.front().second;
				q.pop();
				for (int j = 0; j < 4; j++)
				{
					int rr = new_r + d_r[j];
					int cc = new_c + d_c[j];

					if (rr <= 0 || cc <= 0 || rr > n || cc > n)
						continue;
					//불 꺼져있는 곳으로는 이동 못함
					if (map[rr][cc].light == 0)
						continue;
					if (visited[rr][cc] == 1)
						continue;

					visited[rr][cc] = 1;
					//불들 킬 수 있는거 다기
					for (int i = 0; i < map[rr][cc].sw.size(); i++)
					{
						//기존에 꺼져 있던 경우에만 다시 키기
						if (map[map[rr][cc].sw[i].first][map[rr][cc].sw[i].second].light == 0)
						{
							cnt++;
							map[map[rr][cc].sw[i].first][map[rr][cc].sw[i].second].light = 1;
						}
					}
					q.push(make_pair(rr, cc));
				}
 			}
		}

		if (cnt == 0)
			break;

		answer += cnt;
	}
	cout << answer << endl;

	return 0;
}